2D infinite grid data structure

Question

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)

• Pathfinding

  

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 ?

Edit 1:

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).

Answer 1

You could use a hashtable with a key which consists of both the x-coordinate and y-coordinate. Finding the tile at a specific coordinate is then a constant-time operation.

When you want to cache the "outline", you could store it in another hashtable. Whenever a node is added, follow this algorithm:

• the new node is removed from the "outline" hashtable
• for each neighbor of the new node:
  • when the neighbor is not in the main hashtable (aka is filled) add it to the "outline" hasthtable.

When the constant-time lookup speed in the hashtable is still a bottleneck during route-finding, you could also have each node maintain references to its four neighbors. Whenever you add a new node, get the neighbors from the hashtable and set up the references from new node to neighbors and from neighbors to new node.