Map structure

For simplicity's sake, the Death Dawn map structure is essentially identical to that of GTA 1. I.e., the map is formed from a series of cubes arranged in a 3D grid. Cubes can have a sloping top surface (either north-south or east-west slope) to allow for bridges, etc., and the five visible sides of the cube can be given textures. Each cube has a content type (earth, air, water, etc.), and additional flags allow for the specification of thin walls on some of the edges (to allow for fences, thin bridges, etc.)

The nominal map size of a GTA 1 map was 256x256x6 cubes, where the side of each cube is about 4M long. Assuming 24 bytes per cube, that would consume around 9MB of RAM. However there is a certain amount of redundancy in the map structure - many stacks are identical to many other stacks. GTA 1 utilised this redundancy to shrink the map structure to 256*256*4=256KB per map plus 24*6*numstacks stack definitions. Death Dawn takes this redundancy one step further, by taking advantage of the redundancy in cubes as well as the redundancy in stacks. Furthermore, the game isn't constrained to the 6 blocks per stack limit of GTA 1; stacks can contain as many blocks as the designer wishes, and the base of the stack can be at any height the designer wishes (assuming that height is a multiple of the block height).

Specifics

Death Dawn uses the same approximate measurement units as GTA 1; i.e. each cube (known as a block in the source code) has sides approximately 4M in length. In terms of map coordinates, 1 unit is 1 block. Positive X is east, positive Y is south, and positive Z is up. The main map structure contains the width and the height of the map (measured in blocks), and an array of columns - where each column has a base height (which is a multiple of 1 block to ease implementation), and a pointer to a stack. Each stack has a number of elements; element 0 is the lowest, and h-1 is the highest. Each element in the stack is a pointer to a block definition. Each block has five pointers to tile textures (or null for no texture), a 32bit bitflag field, and two edge heights (for the heights of the sloping edges of the block, if any). These heights range from 0 to 1, making them offsets from the base of the block.

The map generation code and functions are structured in such a way that (if used correctly) there will only ever be one definition for each unique block, and one for each unique stack. However there is currently no method for pruning unused blocks and stacks from the allocation lists without wiping the entire map structure.

The memory footprint for a map currently stands at:

I.e. for a 256x256 map with 512 unique blocks, 1024 unique columns, and an average of 2 blocks per column, the memory requirement is a mere 552KB.

Locality

In addition to the map layout, another structure is used to keep track of which objects are where. Each 4x4 grid of map columns has its own loclist, i.e. a list of peds, cars, and objects which have their origins inside that 4x4 grid. These loclists are used for rendering, collision detection, etc. In order to keep the lists consistent, it is important to use the correct functions when moving objects through the world - cars_teleport() and peds_teleport(). At the present time, objects have no external teleport function, as there is no code external to objects.c that moves objects.

Map zones

Map zones have several purposes:

This means that each zone has the following properties:

Zonedef files

Zonedef files dictate the ped, car, and building spawn criteria for the map zones of a level. Specifically, they contain the following information:

One important thing to realize about zonedef files is that they don't tie a definition down to a particular faction. By using INCLUDE directives, data for multiple factions can easily be merged together to create hybrid areas of the map where two or more factions spawn and interact.

TODO:
CODE: MED: Add stuff to allow pruning of unused blocks and stacks. Just iterate everything and flag it as it's used? Or add a 'use count' to each entry? (trickier to maintain etc.)
CODE: LONG: Mission script funcs for collision detection, LOS, etc.
MUST-CODE: MED: Add 'hover road' content type, which acts like air to everything except hover cars
DOCS: UNKNOWN: Change zone list to use an R-tree? Will provide much better performance than current linked list
???
Profit!