7
\$\begingroup\$

I am currently developing a 3D roguelike game which will take place in a very large world. The world is generated by procedural algorithm supplied by external script in run time. To speed up rendering and minimalize memory requirenments I am dividing world into zones. A zone is a 2D rectangle of maximum size 1024 x 1024 (doesn't need to be a square), that holds dynamically allocated (via single new) array of Tile's. Tile is defined to be as small as possible, to minimalize use of memory. Only the zones visible to screen or in immediately neighbor are in memory, rest are loaded from harddisc file on the need to basis.

The problem I have is that map generator does not need to know about logical zone layout, so it can generate this kind of map (especially for higher Z-levels, like lofts in city): Map generated via generator

This would be waaaay too much memory waste to enclose it in 1024 x 1024 so, it's better to put it into smaller chuncks like this:

Final zones

So, finally the question: how can I convert data supplied by world generator script into actual world structure in memory?

What I've thought about so far:

  1. Script has a method SetTile(x, y, tileType), and the world is automatically recalculated every let's say 100 cells, so the zones are put as efficiency as possible. This will require LOTS of zone copying, moving, resizing, etc. - that's a really slow operation, but it will keep world layout in logical order, so for example it would be easier to implement methods like GetTile(x, y) in the script
  2. Script has a method SetTile(x, y, tileType) which temporary just store a Tile into std::vector and after everything is done, the world runs a second pass that's calculates zones. This is way faster, but has a drawback - since Tile are set in no particular order, it's really hard to have GetTile(x, y) method in the script. Perhaps there is a solution for that drawback, I am just not having any idea of - std::map is way too slow to be used here.
  3. If it cannot be done off screen, maybe the solution would be to expose zones into script and being created explicitly (I mean put into script API CreateZone() function and similar) - I don't want this, because scripts will be exposed to end users and I want to make them as robust as possible.
  4. Perhaps there is other solution? Maybe I can organize world generation in some other way (I still need scripts, but it may be a script that generates only part of the world and then connect)?

Additional things I just came up: the entire world can be too large to be put in the memory at once. So it twist the problem even further - I have to break world generation part (in script) into stages. Any suggestions?

As for technology: I am using C++ 03' without Boost and AngelScript as scripting language

\$\endgroup\$
2
  • \$\begingroup\$ 3D as in 3D viewed or 3D like Dwarf Fortress? \$\endgroup\$
    – DampeS8N
    Aug 20, 2013 at 14:49
  • \$\begingroup\$ @DampeS8N 3D like in Dwarf Fortress \$\endgroup\$
    – PiotrK
    Aug 22, 2013 at 7:36

2 Answers 2

4
\$\begingroup\$

The way that Dwarf Fortress and many other similar 3D roguelikes handle huge world maps is to break the map into chunks. Typically these are vertical slices of world map that are easy to stream in-out on the fly. Which is how Minecraft and Dwarf Fortress in Adventure Mode work.

In Fortress Mode, Dwarf Fortress allows you to select a block of chunks to play in. More chunks means slower play.

This generally solves the overall performance issues and trouble with loading an entire map at once, even for smaller maps. I would hold off on complex solutions until you actually have a problem. However, here are some options. It seems from your examples that you are going for an urban game. If that means skyscrapers that soar to hundreds of floors or more, that certainly could begin to cause performance issues, especially if those floors spread across multiple Z levels with maintenance spaces between floors like many tall buildings have.

In this case, there is no reason at all not to break the map into chunks horizontally as well. You can discard totally empty ones from the map. Or if your game will allow construction, just leave them empty (or filled with air, or whatever your game needs.)

Digression: Actually, a roguelike set in massively tall buildings that models air pressure could be really awesome...

\$\endgroup\$
1
  • \$\begingroup\$ Horizontal chunks! I've not though about them and they seem to work really well in my case. Thanks! \$\endgroup\$
    – PiotrK
    Aug 24, 2013 at 12:58
3
\$\begingroup\$

If I understand your question correctly, your main concern is storing / accessing the generated tiles. Good news: you don't have to reserve the empty space for all the tiles that are not generated yet. There are many ways of storing 'irregularly shaped' data structures.

For example, a possible solution is to build a list of pointers to the tiles you've already generated.

enter image description here

The list (grey box) has a dynamic size, starting at 0, and growing with each pointer (red circle) you put in it. So if you've only generated 3 tiles so far, you're going to have a list of 3 pointers. This way, you won't have to reserve the memory for millions of tiles in advance.

enter image description here

When searching for a specific tile, you iterate on the pointer list, and check the properties of the tile that the current pointer is pointing to. In C#, with a List representation for example, a search would look like this:

Tile GetTile(int x, int y)
{
   foreach (var tile in tileList)
   {
      if (tile.X == x && tile.Y == y) return tile;
   }
   return null;
}

There shouldn't be a scenario, where all the tiles are generated and loaded into the memory at the same time. As the player moves, just remove the pointers that you no longer need from the list (and their corresponding tiles from the memory). Make sure you have a small delay though, otherwise the memory operations could cause lags when the player's moving quickly in and out of a zone or tile.

\$\endgroup\$

You must log in to answer this question.

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