Changing key of HashMap from child method

Question

I'm working on a 2D sandbox game that implements tiles in piston. The basic structure of this is an App struct, which stores a world: World struct, which has a tiles: HashMap property of Box<Tile>s, with the key being an X-Y position of where the tile is.

To render this, I loop through the coordinates of every tile space on the screen and if there is a tile in the hashmap with those co-ordinates, I call tile.render(&context, &mut gl);.

I now need to implement a Tile.update() method which will be called each update, however this method would need to have the ability to modify the co-ordinates of the block which means modifying the key of the tile itself in the hashmap, but I can't pass the hashmap to the tile.update() function since accessing the tile would borrow the hashmap.

How do I accomplish this in the least hacky/most elegant way possible? Is there a better method I should be using to store the tiles that will allow this to work? Changing the co-ordinates from outside the Tile.update() method is not possible.

This is pretty much what I'm trying to do. I know why it won't work, I'm just not sure how to get around it:

use std::collections::HashMap;
use std::boxed::Box;

pub trait Tile {
    fn new(x: i32, y: i32) -> Self where Self: Sized;
    fn render(&self, camera_x: i32, camera_y: i32);
    fn update(&mut self, app: &mut App);
}

pub struct DirtTile {
    pub x: i32,
    pub y: i32,
}

impl Tile for DirtTile {
    fn new(x: i32, y: i32) -> DirtTile {
        return DirtTile { x: x, y: y };
    }

    fn render(&self, camera_x: i32, camera_y: i32) {
        // render
    }

    fn update(&mut self, app: &mut App) {
        let world = app.world;

        // update pos
        let new_pos = [self.x + 1, self.y];
        if world.tiles.get(&new_pos).is_none() {
            world.tiles.remove(&[self.x, self.y]);
            world.tiles.insert(new_pos, Box::new(*self));
            self.x = new_pos[0];
            self.y = new_pos[1];
        }
    }
}

pub struct World {
    tiles: HashMap<[i32; 2], Box<Tile>>,
}

pub struct App {
    world: World,
}

fn main() {
    let mut app = App { world: World { tiles: HashMap::new() } };

    app.world.tiles.insert([0, 0], Box::new(DirtTile::new(0, 0)));

    for (xy, tile) in &app.world.tiles {
        tile.update(&mut app);
    }
}

Playground

Answer 1

You can't modify the key of a HashMap directly. From the HashMap documentation:

It is a logic error for a key to be modified in such a way that the key's hash, as determined by the Hash trait, or its equality, as determined by the Eq trait, changes while it is in the map.

There you have to remove and reinsert the Tile, which you already try to do. You can't, however, remove and reinsert while you still borrow the object. In the update method the Tile object is borrowed via &self. So you have to do it outside of this method.

Sadly, you also can't remove and reinsert while iterating through the HashMap since it would invalidate the iterator. One possibility would be to collect all modified objects in a Vec while iterating through the map and insert those into the map afterwards.

---

However, consider using a different data structure. It's difficult to reason about that without knowing how many tiles you will have, how often they change position and so on. You could separate your world into chunks, like e.g. Minecraft does, with each chunk spanning some quadratic area of size N x N. Each chunk could save it's Tiles in a Vec of size N^2 then. But again: impossible to say what data structure would suit you best with the information given. Also: such question wouldn't fit SO.

Some additional remarks:

• You could use a tuple (i32, i32) instead of [i32; 2] which would let you destructure it like so: for ((x, y), tile) in &app.world.tiles.
• You don't need to put every Tile into a Box: the HashMap already owns the objects; boxing them would only introduce one additional layer of indirection. Consider using a different design that allows you to store many objects "inline". The Box introduces another layer of indirection -- something moderns CPUs don't like at all. A great read about this topic is this section of the game-programming-patterns book.

Answer 2

Consider how

let new_pos = [self.x + 1, self.y];
if world.tiles.get(&new_pos).is_none() {
    world.tiles.remove(&[self.x, self.y]);
    world.tiles.insert(new_pos, Box::new(*self));
    self.x = new_pos[0];
    self.y = new_pos[1];
}

Moves tiles right when they are able, but at the same time you're iterating over your HashMap. This means you might do this:

• Get value at position [0, 0], reinsert at [1, 0].
• Get value at position [1, 0], reinsert at [2, 0].
• Get value at position [2, 0], reinsert at [3, 0].
• ...etc.

...or you might not. This is shared mutation, and this is why Rust says no.

The typical way to do this is to collect values into a new allocation. Here's an example.

use std::boxed::Box;
use std::collections::HashMap;
use std::fmt;

pub type TileMap = HashMap<(i32, i32), Box<Tile>>;

pub trait Tile: fmt::Debug {
    fn new(x: i32, y: i32) -> Self where Self: Sized;
    fn update_into(&self, app: &App, new_tiles: &mut TileMap);
}

#[derive(Copy, Clone, Debug)]
pub struct DirtTile {
    pub x: i32,
    pub y: i32
}

impl Tile for DirtTile {
    fn new(x: i32, y: i32) -> DirtTile {
        return DirtTile { x: x, y: y };
    }

    fn update_into(&self, app: &App, new_tiles: &mut TileMap) {
        let world = &app.world;

        let new_pos = (self.x + 1, self.y);
        if world.tiles.get(&new_pos).is_none() {
            new_tiles.insert(new_pos, Box::new(DirtTile::new(self.x + 1, self.y)));
        }
        else {
            new_tiles.insert((self.x, self.y), Box::new(*self));
        }
    }
}

pub struct World {
    tiles: TileMap,
}

pub struct App {
    world: World,
}

fn main() {
    let mut app = App { world: World { tiles: HashMap::new() } };

    app.world.tiles.insert((0, 0), Box::new(DirtTile::new(0, 0)));

    let mut new_tiles = HashMap::new();
    for (_, tile) in &app.world.tiles {
        tile.update_into(&app, &mut new_tiles);
    }
    app.world.tiles = new_tiles;

    println!("{:?}", app.world.tiles);
}

That said, your use of dynamic dispatch is probably not optimal. Consider an enum instead if possible, maybe like this.