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

    enter image description here

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

  • 1
    \$\begingroup\$ Quadruple linked-list \$\endgroup\$
    – MickLH
    May 3 '16 at 12:25
  • \$\begingroup\$ I'd combine nodes into small fixed-size (possibly 16x16) 2D arrays (chunks). For small maps (like your 250x250) quad-linked-list of chunks should work, for huge maps I'd use a variations of quad-tree, in which each region contains a 2D array of pointers (something like 4x4 or 8x8) to it's subregions; obivously, bottom-level regions contain pointers to chunks instead of subregions. \$\endgroup\$ May 3 '16 at 13:00

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.

  • \$\begingroup\$ Yep, this is one of the possible solutions i had in mind. I'll have to try it. \$\endgroup\$
    – copied
    May 3 '16 at 13:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.