I'm currently developing a game, and I'm in a process of experimenting with various data structures to support my game model and simulation.
Here are some of the requirements:
- Grid structure where every node will have exactly 4 neighbors, if revealed.
- Infinite structure(max_int), with ability to dynamically add nodes
- Ability to find all neighbors of a specific node
- Ability to find all outer empty spots around existing nodes ( basically outline around graph)
This is an example of how it should look. Red node will be starting point. Depending on a player's direction of movement, other nodes will be revealed and inserted into a graph. Also there is no restriction to movement between nodes as long as they are neighbors.
Current structure looks like this:
- Node - containing [x,y] position in grid and data pointer, custom hash function for only [x,y]
- Grid - set containing all nodes.
Now, in my testing, with the structure above, the bottleneck for 250x250 grid is finding neighbors, which takes a lot of time. BFS and DFS traversing is also slow due to the process of finding neighbors.
What are your suggestions for this kind of data structure ?
Here are some of the ideas i was thinking about. Btw already using hash_set(unordered_set) for storing nodes. Maybe i should switch to unordered_map, that way i could directly search by providing only [x,y]
Node could keep pointers to all neighbors like a cache, when adding new nodes, i could update old nodes with new neighbors, this way node will have direct access to neighbors.
As suggested, by using small chunks, i could possibly waste memory, because in worst case scenario only one node could be explored in a single chunk.
I was definitely thinking about quad-tree, this way i could use it in two different aspects(model searching/updating and rendering).