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):
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:
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:
- 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 likeGetTile(x, y)
in the script - 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 haveGetTile(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. - 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. - 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