2009
06.28

World Storage

Data is represented with C++ structures, which you may easily translate in any other language.

The world and its minimap

As said before, at its higher level, the world is a 50×50 array of integers representing the altitude of the regions. Each region use a single byte to store its altitude (0-255). To generate the high level detail of the region, we use a random seed deduced from the world random seed and the region coordinates :
`regionSeed = worldSeed * (regionX * 256*256 + regionY)`
So for now, the only data we need to build the world is :
```class World { int32 seed; uint8 regions[50][50]; } ```

Regions surrounding the player

To draw the high level map from the player current position, we need to generate the player current region and all 8 surrounding regions. Each region is interpolated to a 100×100 map representing the level 0 of the region. The first floors of buildings will be stored in the level 1 of the region. The caves and sewers start at the level -1 going underground to the negative levels.

Each level is stored in a map. Since all regions do not have the same levels (some may have deep underground caves, some other may rather have big cities with buildings with lots of levels), each region contains a list of maps, each map representing a level :
```class World { int32 seed; Region regions[50][50]; } class Region { bool generated; uint8 altitude; List< Map *> maps; } class Map { int8 level; Cell cells[100][100]; } ```

To know if a given (x,y,z) position in the world exist, we find the region from the x,y coordinates
`Region *r = &world.regions[ x / 50 ] [ y / 50 ];`
then we look for a map at level z. If such a map exists, we can get the cell at x,y,z position.

Memory concerns

With deep enough caves (say 10 levels), a region can contain 100 x 100 x 10 = 100 000 cells. Depending on the cell size, this may take a certain amount of memory. To keep memory usage low, we only have in memory the 9 surrounding regions. When the player enter a new region, we generate the new one and free the old one. All the generation must rely only on the world seed so that we generate the same region each time the player enters it.

Storing the whole 100×100 map for each level of the region may use a lot of memory with empty cells. The worst case is a single building with a floor at level 1. On the following picture, the green rectangle represent the whole region, the blue rectangle the cells not empty at level 1, the white rectangle, the allocated map for level 1.

Level 1 optimization : cropped map

On way to reduce empty cell allocation would be to crop the level 1 map by suppressing all surrounding empty rows and columns. For the single building case, we would get :

```class Map { int8 level; int8 x,y,w,h; // map offset and dimension Cell **cells; // dynamically allocated array } ```

In this case we get an optimum level 1 map, but there are lots of cases where the crop algorithm is far from efficient. The worst ‘pathological’ case is the following :

With one building at each opposite corners of the region, we fall back to allocating the whole 100×100 map for level1.

Level 2 optimization : fragmented map

Now we allocate a dedicated minimap for each building that has cells on level 1. Thus, there will never be a single empty cell on our level 1 map :

The data structure is the same as the level1 but now we can have several maps with the same level value.
But when we add more buildings we end with a lot of minimaps for the level 1. Lots of minimaps mean poor performances on the World::getCell(x,y,z) function. We may have to loop through the whole list of minimap to find a single cell which we cannot afford since this function is used anywhere in the engine (field of view, lighting, …).

Level 3 optimization : ‘smart merger’

When we ask the engine to add a minimap at a certain level, we may first search for other minimaps in the same level that are ‘pretty close’ to our new minimap. If we find one, instead of creating a new minimap, we merge the two minimaps into a bigger one. ‘pretty close’ may have lots of meanings. We could for example merge two minimaps M1 and M2 if the number of empty cells in the resulting minimap M3 is less than surface(M1) + surface(M2) (thus we don’t merge minimaps if the result has more than 50% of empty cells). With a good ‘pretty close’ heuristic, we could get for the previous example :

Instead of 12 minimaps, we have only 5 without wasting too much memory in empty cell allocation.

Level 4 optimization : replace list by bsp

If we really want a good speed/memory ratio, we can replace the list of minimap by a binary space partition tree in the fragmentation or the merger algorithm. A BSP tree will allow to look for a cell without looping through the whole list of minimap by recursively splitting the region into smaller sub-regions.
```class Region { bool generated; uint8 altitude; BspTree< Map *> maps; } ```

You can find a good starting point about BSP trees on wikipedia :

http://en.wikipedia.org/wiki/Binary_space_partitioning