1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thank you very much. I can see this work. Right now I am developing something simpler and will see how that works, but i will keep the quedtree you mentioned and the way you implemented it in my mind. \$\endgroup\$ – RIJIK May 23 '18 at 11:45
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ The Problem with lists is, that it cvannot be accessed via coordinates either. Just iteration. It would then be no different the what i have now. In fact right now what i have is just a interlinked twodimensional list. I have thought of binary Search Trees, however those would perform even worse because the locations i will ask of are all rather close. So an Array it is. The only question is, How do I make an array that changes its size? The only thing that comes to mind is the c++ vector which has the problem of having to rewrite all data when adding new elements \$\endgroup\$ – RIJIK May 22 '18 at 9:03
  • \$\begingroup\$ The C++ vector reallocates for each addition of an element, but in the end it's just pointers, so it's not that much overhead. In java you have ArrayList for a faster List, in C++ you should have something similar, that gets accessed with an index and has dynamic size. \$\endgroup\$ – Paul Boursin May 22 '18 at 18:23
  • \$\begingroup\$ Otherwise you could implement your own quadtree, which could be the best option in your case. I can explain how to implement it and why it would be good in your case, in another answer, soon. \$\endgroup\$ – Paul Boursin May 22 '18 at 18:34

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.