How i'm going to make a multi-floored tile map?
GetRandomGame RPG development is slowly restarting.
The picture is here to help visualize what I mean, like in the Ultima serie, with mountain and multiple story building. Making a multi-floored map brings a tons of game-play possibilities, enhance the immersion and add credibility to the world. But this comes at a cost. It's like ten times the work to make simple things like walking around and seeing your character through structures. Since the last semester (and last time I worked on GetRandomGame), I'm wondering how I'm going to do that kind of map.
It seems pretty straightforward but I have a lot of features that complicate the process. Features like never loading a map in game (à la Minecraft), the procedural generation of the world as you're traveling through (still Minceraft-like), and being able to see the floors below you and/or yourself behind walls and mountains. The problem is how to efficiently store the map data for each floor and when to load it, when to save it and trash the data, and how much tiles to load at once while moving?
This post has become very long and technical, click read more for the detail information on the problem and to see the solutions I might take to overcome this challenge.
That said, I don't want a crappy but working solution since I'm doing it for learning sake. There are some alternatives that come in mind (please note that an Area of tiles contains, as of today, 17 by 17 tiles but may change in the future):
#1 - A 3D array (like chunks)
Really straightforward, each Area has a 3D array of 17 x 17 x NUMBER_OF_FLOORS which would be 1445 tiles for only a 5 story map.
way too much memory wasted
and a lot of initialization to do at each chunk load;
#2 - A 2D array of linked list or vector
An Area still is an array of 17 x 17 but instead of containing tiles, it contains a dynamic array of tiles. So each Area would be 289 dynamic arrays of tiles. So the number of loaded tiles is random and can grow fast if traveling up or down the floors. It may load about 1445 tiles if you travel through only 5 floors and it will keep all those in memory.
You only initialize what is created and useful;
What you don't see never get initialized/created;
Number of floor is dynamic.
May be harder to search through;
Definitely harder to save and to load;
to much tiles can be loaded at once without an easy way to clean the arrays;
makes a lot of arrays to manage (like 289 per floor per area).
#3 - Each Area object have a vector of tile chunks
Each Area have a single dimension array of 2D arrays. The first array being the size of the number of floor. So it needs to load at least the current floor (289 tiles), the floor below (another 289 tiles) and the upper floor (and that makes a total of 867 tiles).
When needed, you only load a new Area for the upper/below floor which is 289 tiles (17 x 17) each;
it need lesser arrays to work (the fixed number of 4 arrays per Area all the time).
Current floor number can't be negative (like for undergrounds);
Can be difficult to add an Area in the middle of two already loaded Areas.
#4 - Each Area is kind of an independent chunk from each other
Let the Region (a class that contains 65 x 65 pointers to Areas right now) manage all the Area like independent chunks, by loading and saving a single Areas at once so it make chunks of 289 tiles. Put the Area in like a map container and use the world coordinate as the key.
The single Area chunks may be manage like a resource by a standard manager template (Already have the template and it works well, but I can't guarantee it's fast enough);
Easy to search for an Area with a Map standard container;
Less expensive at initialization because you only load the Area you need, you don't need 65 x 65 NULL pointers;
Can handle infinite number of floor.
I don't know if the map container is best suited for the task;
Need to trash the old way of storing Area in the Region.
Let's make a little research on the subject.
While reading on the gamedev stack exchange site, I came across "'Zoning' up areas on a large tile map, as well as dungeons" and the answers and comments strongly suggest to ignore/skip the sparse data set storage solution and just ignore updating the tiles too far from the actors. This would significantly accelerate the development, so I'll keep this in mind when the time comes to save the world... data.
Now back to the map storage problem, I found another question and its answer is quite interesting. Instead of storing the whole map, store each region relative to the next one. In a case where maps are handmade, this is the perfect solution I guess, but in my case, it's not really what I want, but it open my eyes on other possibilities.
So finally, which solution should I take?
The #1 is out of the question, I've put it here but I knew that it was dumb. The #2 creates too much dynamic arrays and becomes cumbersome to use. The #3 isn't that bad, but still not sure and the best choice seems the #4. But after reading that it's not that bad to keep a lot of tile into memory, I might consider #3. Do you have an advice for me?
