2
\$\begingroup\$

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Quadruple linked-list \$\endgroup\$
    – MickLH
    May 3, 2016 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, 2016 at 13:00

1 Answer 1

1
\$\begingroup\$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .