Bidirectional data structure for this situation

Question

I'm studying a little part of a my game engine and wondering how to optimize some parts.

The situation is quite simple and it is the following:

• I have a map of Tiles (stored in a bi-dimensional array) (~260k tiles, but assume many more)
• I have a list of Items which always are in at least and at most a tile
• A Tile can logically contain infinite amount of Items
• During game execution many Items are continuously created and they start from their own Tile
• Every Item continuously changes its Tile to one of the neighbors (up, right, down, left)

Up to now every Item has a reference to its actual Tile, and I just keep a list of items. Every time an Item moves to an adjacent tile I just update item->tile = .. and I'm fine. This works fine but it's unidirectional.

While extending the engine I realized that I have to find all items contained in a tile many times and this is effectively degrading the performance (especially for some situations, in which I have to find all items for a range of tiles, one by one).

This means I would like to find a data structure suitable to find all the items of a specific Tile better than in O(n), but I would like to avoid much overhead in the "moving from one tile to another" phase (now it's just assigning a pointer, I would like to avoid doing many operations there, since it's quite frequent).

I'm thinking about a custom data structure to exploit the fact that items always move to neighbor cell but I'm currently groping in the dark! Any advice would be appreciated, even tricky or cryptic approaches. Unfortunately I can't just waste memory so a good trade-off is needed to.

I'm developing it in C++ with STL but without Boost. (Yes, I do know about multimap, it doesn't satisfy me, but I'll try if I don't find anything better)

Answer 1

struct Coordinate { int x, y; };
map<Coordinate, set<Item*>> tile_items;

This maps coordinates on the tile map to sets of Item pointers indicating which items are on that tile. You wouldn't need an entry for every coordinate, only the ones that actually have items on them. Now, I know you said this:

but I would like to avoid much overhead in the "moving from one tile to another" phase

And this method would involve adding more overhead in that phase. But have you actually tried something like this yet and determined that it is a problem?