An idea was suggested to me – using octree for storing map data in OpenGBH. It seems like quite an interesting idea, since OpenGBH maps are usually full of nil space (blocks not filled in any way), they are not limited in size (so they must be stored in some sort of chunks).
To be more exact, map would be stored as quadtree and octree. The division into quadtree is for dividing city into major blocks, each of the blocks containing a whole map portion. Division into octree divides those portions into sets of blocks, and finally into separate distinct blocks. But not ending there division can go further and create ability to subdivide map blocks into smaller ones for more complex architecture and level geometry.
Quadtree divison starts from the root node – this node (like all others) is rectangular in size, and it’s big enough to fit the entire map. For example for GTA2 city it would be a 256x256x32 node (assuming city can be up to 32 blocks high – which is an incredibly high limit actually).
The root node divides into smaller ones, all of which have the same height (all dimensions are in game “blocks”):
256x256x32 128x128x32 64x64x32 32x32x32
After this division into octree starts – every node divides into 8 other nodes, until it reaches size of a single block:
32x32x32 16x16x16 8x8x8 4x4x4 2x2x2 1x1x1
After this subdivision of each separate block starts – it’s possible to divide blocks into very small pieces, there is a lower limit though (about 0.03% of size of a whole block). Actually this works the same way for larger blocks – it’s possible to define one big 4x4x4 block.
This should make uncompressed map take less space in RAM than an equivalent 3D array (possibly division schematic should be revised, maybe there’s a more optimal way to divide map.. not sure right now though).
This should allow the whole level to be built in a very flexible way. Each block (or part of a block) can be one of the predefined slope geometries – meaning you can make some unusual constructions never possible in GTA2.