How do i retrieve individual Tile Information from a tilebased procedural World fast?

Question

I am concerned about performance with my current setup; as I want to expand on it i need to figure out if I might need to change it.

Current Setup:
The Game/Prototype is similar to Dwarf Fortress or Rimworld. The world i have is tile based and procedural. It is made up of chunks(16x16). All chunks are connected not via coordinates but via pointers (chunk on the east, chunk in the north, chunk in the south and so on). Each chunk segment (or block/ tile) holds an entity(which can be the player, the human or a plant).
Lets say one Entity (for a example a human) walks towards the edge of the chunk and wants to know what is the tile next to him. Then i will have to look at min 8 tiles next to him. Due to the chunks only being accessible through neighbors, I have to always check wether the position relative to the entity is in a new chunk and how many chunks i have to iterate through to get to the position asked for. It is quiet the hassle and i can imagine it becomes a big performance problem once i want to do pathfinding.

Now some Questions:
How do games like Factorio handle this type of data gathering. In an Array i could easily figure out where to look. How do i retrieve individual Tile Information from a tilebased procedural World fast? Should i use coordinates or relative Positions(like i do now)?

Answer 1

I suggest using a quadtree, which is composed of nodes that contains four pointers to nodes. It's basically a binary tree for 2D, like an octree is for 3D. With it you divide your terrain into squares (chunks) that are grouped up in nodes of four chunks, that are themselves grouped up into nodes, etc. Then you write recursive algorithms to go through your tree. The advantage is whenever you want to add a chunk, you just attach it to the appropriate node, at the appropriate place, and if it doesn't exist, create a bigger node and add it, so on.

More precisely, you can have a node class that is the base type of each pointer. Then you have the "branch" class and "leaf" class that inherit of node. The branch class has four pointer to nodes. The leaf class is just a chunk. It's up to you to design the algorithms, and what a node has in information, but here's pseudocode for one recursive algorithm :

Chunk findChunk(x,y) {
   if(x<nodeX) {
    if(y<nodeY) {
      return topRightNode.findChunk(x,y);
    } else {
      return bottomRightNode.findChunk(x,y);
    }
  } else {...}
}

Of course, this requires more, such as findChunk function in chunk, that always returns itself, and a null check before calling each findChunk, because if the pointer is null, that means the chunk you are looking for doesn't exist, and must be created.

There is a lot more to know, the best is to Google about it and try it out.

Answer 2

I do not know how games do this, but I think you should abandon that data structure. A coordinate system that gets a pointer to a chunk when given coordinates would be simpler and much faster to get a point from anywhere. This means an array of pointers, and as you said it is easy to find where to look. You could use a dynamic size list with pointers to generate chunks on the go. I think you shouldn't worry too much about performance yet, don't make it too complex or specific, as you might end up having to write something much too complicated for a case you didn't foresee.

Answer 3

Why not use a Dictionary, where the key is a tuple that holds int x and int y values and the other entry is a pointer or reference to your tile?