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

If you really think having each tile store it's items will cost you too much space, consider using a quadtree to store items then. This allows you to efficiently get all the items on a tile, but leaves your Tile grid in place for item movement.

Answer 2

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?

Answer 3

To me I would wrap a std::vector into a matrix type (IE impose 2d access on a 1d array) this give you fast random access to any of your tiles (implementing the matrix is trivial).

use

 vector_index=y_pos*y_size+x_pos;

to index a vector of size

 vector_size=y_size*x_size;

Then each item can have a std::vector of items (if the amount of items a tile has is very dynamic maybe a deque) again these are random access contains with very minimal overhead.

I would stay away from indirect containers for your use case.

PS: if you want you can have my matrix template.