Bidirectional data structure for this situation

Question

I study a small part of my game engine and wonder how to optimize some parts.

The situation is quite simple and looks like this:

• I have a Tile map (stored in a two-dimensional array) (~ 260 thousand tiles, but many more are assumed)
• I have an Item list, which is always at least and no more than a tile.
• A Tile can logically contain an infinite number of Item s
• During game execution, many Item constantly created, and they start with their own Tile
• Each Item continuously changes its Tile to one of its neighbors (up, right, down, left)

So far, each Item has a link to its actual Tile , and I just keep a list of items. Every time an Item moves to a neighboring element, I just update item->tile = .. and I'm fine. This works great, but it is unidirectional.

When expanding the engine, I realized that I have to find all the elements contained in the tile many times, and this effectively reduces performance (especially for some situations in which I have to find all the elements for a number of tiles, one by one).

This means that I would like to find a data structure suitable for searching all the elements of a particular Tile better than in O (n), but I would like to avoid the big overhead of “moving from one tile to another” (now it just assigns a pointer I would like to avoid many operations there, as it is quite common).

I am thinking of a custom data structure to take advantage of the fact that elements always move to an adjacent cell, but I am currently groping in the dark! Any advice would be appreciated, even complex or cryptic approaches. Unfortunately, I can't just lose my memory, so I need a good compromise.

I am developing it in C ++ with STL, but without Boost. (Yes, I know about multimap , it does not satisfy me, but I will try if I do not find anything better)

Answer 1

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

This compares the coordinates on the tile map with sets of item pointers indicating which items are on that tile. You do not need an entry for each coordinate, only those that actually have elements on them. Now, I know you said this:

but I would like to avoid a lot of overhead in the "transition from one tile to another" phase

And this method involves adding extra overhead at this stage. But did you actually try something like this and decide it was a problem?

Answer 2

For me, I would wrap std::vector in a matrix type (IE imposed 2d access on the 1st array), this gives you quick random access to any of your fragments (the implementation of the matrix is ​​trivial).

using

  vector_index=y_pos*y_size+x_pos; 

to index the size vector

  vector_size=y_size*x_size; 

Then each element can have std :: vector elements (if the number of elements that the tile has is very dynamic, maybe deque) again, this is random access containing very minimal overhead.

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

PS: if you want, you can have a matrix template.

Answer 3

If you really think that each tile store will cost you too much space, consider using quadrants to store items. This allows you to effectively get all the objects on the tile, but leaves the grid of tiles in place to move the item.