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:
- map_w*map_h*8 bytes for the base layout
- 4*numstacks+4*totalblocks bytes for the stack definitions
- 32*numblocks for the block definitions
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:
- They provide names for areas of the map; these names are displayed to the player, to help him know where he is, and are used as parts of mission text to direct the player to locations
- Each zone dictates what faction controls it, what types of peds and cars spawn there, etc.
- During map generation, they are used to dictate what building styles are contained within
- Zones can also be created and used by the mission script as area triggers
This means that each zone has the following properties:
- Zone ID number (for mission script references)
- Textual name
- 3D bounding box
- onenter, onexit trigger functions (called whenever a ped or car leaves/enters the zone)
- Owning faction(s) flags?
- Zonedef reference (see below)
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:
- Ped types that will spawn within the zone. Each type listed also has three probabilities - for walking, driving, and being a passenger (riding)
- Car types that will spawn within the zone. Each type listed also has a probability. The occupants of the car (if any) will be chosen from a combination of the ped list for the zone, and the ped list for the car type - a ped will only be placed in a car if he has a driving (or riding) probability for the zone and for the car type.
- Building types that will spawn within the zone.
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!