Tile based game logic structure

[dani.pardo]

So, I'm writing a game, as a hobby, and I'm trying to come up with an easy way to handle the logic of collisions.
It's a tile based game, very simple, simple enough not to require any ECS I think.

So I have a GameState, which has a "map" field, where map is a Vec of tiles. Each tile has some internal data like velocity, points, location, etc..

The problem I've been struggling for weeks now is the following function:

pub fn handle_move_tiles(level: &mut GameState) {

Where level is the game state: I need it to be mutable in order to change the score, for example.
What this function needs to do is:

1-Iterate over all tiles in the map, which, as said, is a Vec (self.level.map)
2-Check for collisions in any of the 8 possible adjacent tiles
3-If a collision has been detected, I'd like to invoke a method on the colliding tile,
passing it the list of tiles it collies with:

impl Tile {

 pub fn handle_collision(&mut self, neighbors: Vec<&Tile>){}
 ..
}

I've tried implementing this logic in several ways, but the borrow checker always yells at me.

This is the last version so far:

pub fn handle_move_tiles(level: &mut GameState) {

   // A a list of collisions, where the 1st element is the one that collides
   // and the 2nd element is the list of tiles it collides with
   //
   // pub fn get_collisions(&self) 
   let collisions: Vec<usize, Vec<&Tile>) = level.get_collisions();   <---------------
   for collision in &collisions {                                                    |
                                                                                     |
        // Cannot borrow level.map as mutable because its also borrowed as inmutable |
        let collider = level.map.get_mut(collision.0).unwrap();               -------|
        collider.handle_collision(&collision.1);
    }
}

The question is.. how should I approach this problem? Is it doable without Rc and/or Cells?

[quinedot]

I assume you're returning tuples of the form (usize, Vec<&Tile>) precisely because you can't return (&mut Tile, Vec<&Tile>). If the universe only held two colliding tiles, for example, the return from get_collisions would presumably be something like

vec![
  (&mut level.map[0], vec![ &level.map[1] ]),
  (&mut level.map[1], vec![ &level.map[0] ]),
]

And this clearly contains both mutable and shared references to the same Tiles. So you can work around this by returning an index instead of a &mut Tile in each tuple... but as soon as you try to turn the index back into a mutable reference, you're going to have the same problems.

One approach would be to return Vec<(usize, Vec<usize>)> and to later turn each tuple into (&mut Tile, Vec<&Tile>) within the loop. It can be a bit round-about to safely convince the compiler that the mutable reference into the Vec doesn't overlap with the shared references.

Another approach may be a function that takes a &mut [Tile] and an index and produces a (&mut Tile, Vec<&Tile>) of collisions specific to a single tile, instead of computing all collisions in a single function. It would involve similar slice splitting.

[dani.pardo]

Mm.. thanks. I think it's a neat trick, but a trick after all, to work around the borrow checker, isn't it?
There must be an easier solution, otherwise, in a couple of months, when I get back to the same code, It won't be easy to gasp why I was generating those slices in the first place (unless I comment it properly, of course

In fact, this is a bit like minesweeper: Given a two-dimensional array of cells (represented as a Vec), write a function that mutates each cell so that it contains how many surrounding cells are bombs. I think I'll try that first, and get back to this game afterwards.

[quinedot]

@dani.pardo

I think it's a neat trick, but a trick after all, to work around the borrow checker, isn't it?

It's one way to avoid violating the exclusive reference constraints of Rust, and without runtime checking, as requested. You'll have to achieve that somehow. "Working around the borrow checker" implies it was wrong about something; I don't feel that this applies to the code you provided as I'm pretty sure you are, in fact, violating the constraints.

(Arguably being a work around does apply to the method used to get exclusive references into only part of a Vec; rustc can reason much better about struct field accesses than it can Vec offsets. On the other hand, it would need to special-case Vec for it to be otherwise. split_at_mut is a tool provided for programmers to safely code the same result.)

[dani.pardo]

It is a nice trick indeed. What I meant is that, is there any other approaches to solve this problem?
For example: Another approach thtat I came up with was to have a function next_map(), which means how the map should look at the next frame. This function returns a tuple: (usize, usize, Tile), where the first element is x (column in the map), the second element is y (row in the map), and the Tile is the tile that should be in there. So I could do something like this:

let changes: Vec<(usize, usize, Tile)> = level.next_map(&level.map);

for change in &changes {
    let t: &mut Tile = level
        .map
        .get_mut(change.1 * level.dimensions.0 + change.0)
        .unwrap();

    t.position = change.2.position;
    t.velocity = change.2.velocity;

I might try to dive deeper on this last aproach, as It only lacks the delegation on what do do after a collision to the tile that collides.

[scottmcm]

@dani.pardo

how should I approach this problem?

One standard approach (which I learned from reading some rustc code) is to have the iteration step produce what are conceptually "update messages" -- maybe they'd look something like struct CollisionDetected { tileIndex: usize, otherTileIndexes: Vec<usize> }.

That way the first pass is only reading, so it won't hit any borrow checker complaints. Convenietly, that also means that you could easily parallelise it, if you wanted. Then you can do a second pass applying those messages to the gamestate. (Could even structure that apply step as a method on the message type, if you wanted.) As another nice property, that forces you to never update before the other things have read. (Think, for example, of the easy Game of Life bug of marking a tile as "alive now" before getting to one of its neighbours.)

That's a good tradeoff in any place where there's alot more "looking" to be done than "updating", which I think is often the case.

If not, then the functional-language fn(GameState) -> GameState approach can work better. Depends how you want to structure things.