The building of Caveman - part 6 - data structures

When i first got into programming as my major, my biggest fear was that I'd end up as a database programmer.
Turns out I became a gamedev. But i still have to do database programming. Sure, games are interactive
multimedia entertainment simulations, but underneath all that is - you guessed it - relational databases!
It turns out that a complex game can have a rather complex relational database system behind it.

Terminology:
database or list: a static array of structs, usually a one dimensional array.
record: a struct in an array
field: a variable in a struct.

In the game, most databases and lists are implemented as static arrays of structs. structs are referenced
via their array index. Maximum sizes required are known ahead of time, which allows the use of fast simple
static data structures. Many of the databases are relational, with some field (variable) in a record
(struct) being the array index of some other record (struct) in some other database (array of structs).
Some of the databases are nested, with one field in a record being an entire list. IE a variable in a
struct might be a whole array of structs. For example, each band member struct has a member varable which
is a list of active traps, implemented as an array of structs.

These are the data structures used by the game:

Asset databases:
First off, the generic databases for assets:
1. meshes - a VB and IB, numtris, and numverts.
2. textures - a d3d texture of some type
3. models - models simply refer to meshes and textures.
4. animations - a list of keyframes with limb orientations
5. animation players - a playback counter, plus model and animation references.
Caveman follows a mantra of one texture per mesh for speed. Models are made up of multiple meshes. An
entry in the models database references meshes in the mesh database, and textures in the texture database.
An entry in the animation players database references a model from the models database, and an animation
from the animations database. All asset databases are part of the generic Z game library used by Caveman.


Type databases:
1. actions - prerequisites, time required, chance of success, etc. prerequisites can include references to
skills and object types.
2. skills - prerequisites to learn, time required to learn, chance of learning success, etc. prerequisites
can include references to skills and object types.
3. object types - prerequisites to craft, weight, damage, cost, time to craft, chance to craft, etc.
prerequisites can include references to skills and object types.
4. animal types - hit points, turn rate, speed, etc. IE non-variable stats. animal types include a reference
to the models database, and references to the animations database.






single instance lists:
1. active bandmembers - an entity list for PCs. the player can tab between PCs at any time. Other PCs are
controlled by AI. each active bandmember has an inventory list, a list of active traps, a list of active
quests, and a list of active intoxicants. a bandmeber record has references to the following databases:
models (for body), meshes (for face and hair), textures (for skintone), and animations.
2. active animals - all NPC cavamen and animals (every non-PC entity). animals which are of type 2
(homo sapien) refer to an entry in the NPCs database where additional NPC specific data is stored.
animal records also refer to the animal types database, and the bandmembers list (for owners of pets).
3. active missiles - arrows, throwing rocks, etc. Smoke from fires may be implemented as a type of missile.
missile records refer to either the bandmember list or the active animals list (for owner), and also
refers to the object types database.
4. world objects - temporary shelters, storage pits, rafts, landmarks, dropped objects, etc. Basically
anything man-made except for huts. structs in this array reference the object types database.
5. active storage pits - a list of storage pits created by the player. refers to the world objects database
(a storage pit is a world object). includes an inventory list for each pit.
6. active rafts list - a list of active rafts. references the world objects database (a raft is a world
object).
7. NPCs - non bandmember cavemen. contains info on NPCs encountered by the player. references the
model, mesh, and texture databases. includes an inventory list for each NPC. NPCs at a CRH reference the
CRH list.
8. CRHs (caves, rockshelters, and huts) - a list of all the caves, rockshelters, and huts in the game -
83,000 of them! each entry has an inventory list (paged from disk). CRHs occupied by animals refer to
the animal types database. There is also a player's version of the CRH list, that only contains info
about CRHs the player has discovered.
9. player cave list - a list of those CRHs controlled by the player. references the CRH list. basically
an index of player controlled CRHs for use with the CRH database.



single instance matrixes (2d arrays of ints):
1. numconvos - tracks the number of conversations this day between band members and NPCs
2. relations - tracks relations amongst bandmembers, and between bandmembers and NPCs.



multiple instance lists:
1. inventory lists - list of objects carried, stored, or for trade. entires in the list refer to the
object types database. each bandmember, storage pit, NPC, and cave/rockshelter/hut occupied by
friendlies has an inventory list as one variable in their struct declarations.
2. Trap lists - a list of the status of active traps set by a band member. refers to the world objects
list (the trap is a world object). each band memeber record includes a trap list field (variable).
3. Active quest lists - a list of active quests. references the animal types database. each band member
struct has an active quest list.
4. Active intoxicants lists - a list of intoxicants currently affecting a band member. references the
object types database. each bandmember struct has an active intoxicants list.



handy structs used in the game:
i find that sometimes its handy to have a sturct to pass info around.
1. location - the world map is a 500x500 grid of map squares. each map square is 5 miles across.
a location is specifed by its map square indices (mx,mz) and by its d3d location in that map
square (x,y,z). a scale of 1 d3d unit = 1 foot is used. a location struct is a handy way to store
both the map sqaure and location of an object.
2. requirementsrec - a list of parts, tools, and skills required to do something. used by skills,
object types, and actions.
3. Zdrawinfo - all the info to draw a mesh, static model, animated model, 2d billboard, or 3d billboard.
used everyhwere to pass drawing info around.
4. objectrec2 - an inventory list entry: active, object type, quantity, quality, location. Used for
inventory and world object lists.





world map data structures:
1. the world map - a 2d array of structs. the world map is 500x500 map squares in size. a map square is
5 miles across. a location is specified by its map sqaure indices (mx,mz), and its d3d location in the
map square (x,y,z). a scale of 1 d3d unit = 1 foot is used. a maps sqaure struct contains info for
elevation, vegetation coverage, water, resources, etc. there is also a player's version of the world map
that only contians data for explored areas.
2. the local map - basically a 2d array of ints, used as booleans, explored/unexplored. This is used as
a "bitmap mask" to cover over unexplored sections of a map square when viewing the local map.
3. cavern maps - a 2d array of ints. values indicate walls, open space, encouter points, exits, etc.
4. plant maps - i needed a way to tell it where to draw plants, rocks, trees, etc. generating a bunch of
level maps was out of the question - too big for memory. what i came up with was what i call a "pattern
map". its a sparse matrix list of objects (trees, rocks, plants, etc). when drawing the scene, this
pattern map is tiled across the ground. Maps are large enough that no repetition is within visible range.
the game uses 4 such pattern maps - each one different - to place rocks, trees, berry bushes, etc.
4. wood grass map - another pattern map, for undergrowth in woods.
5. ground texture map - a 2d array of ints. caveman uses ground texture tile sets of 4 textures each. the
ground texture map contains random values 0 through 3, indicating which tile in the set to use for
texturing a ground quad. Agian, this "pattern map" is large enough so repetition is not within visible
range.
6. generic pattern map - as development progressed, i found myself needing a pattern map from time to time.
so i decided to create a generic one that i could write functions for that would return whatever i needed.
the geneic pattern map is a 100x100 array of random ints 0 through 100. functions are then written to
return values as needed. example: return the scale of a plant at x,z: map x,z to 0-99,0-99, and return
some permutation of the value in the generic pattern map at that location. Uses of the generic pattern
map include control of model, texture, scale, rotation, and offset of tall grass plants, and as the
basis for a double interpolated height map for canyons.




terrain chunks:
originally, the game drew the scene by brute force, drawing the ground one quad at a time, or with a dynamic
buffer, and iterating thorough the various pattern maps drawing tress and rocks etc, all the while checking
for collisions with man made objects (dont draw plants inside a hut!). Scene composition simply took too
long this way. So i stared at the lowest level and let that define how the code should work and how the
data should be organized. basically, what directx wants is an ordered list of renderables, sorted on
texture, then mesh, then near to far (for non-alpha). instead of generating the list of renderables each
frame, i decided to divide the terrain into chunks 300x300 d3d units (feet) in size. a chunk consists of
an unordered list of all renderables in the 300x300 area (in zdrawinfo structs), and a 3D index: a list of
textures, and for each texture, a list of meshes, and for each mesh, a list of instances which are indexes
into the list of renderables for the chunk. chuncks are genrated as needed and then stored in a cache with
LRU discard. to draw a chunk, the index is used to traverse the list of renderables in correct drawing order.
for each renderable, a frustum cull check is preformed, and if it passes, its added to the render queue.





the render queue:
the 3d indexed renerables list from chunks worked out so well that i redesigned the render queue in the Z
game library to use a 3d index. originally it was a simple list that got sorted just before drawing. Now,
as a renderable is added to the queue, its also added to the 3d index, in what is essentially a bucket
sort type of thing.




And that's pretty much it for the data structures. If i had to do it all over gain, i'd use more of a
composition type approach, and give animals and bandmebers a location struct for example. that way i
could write one piece of code to work with a location instead of one to work with bandmembers and one
for animals. As i go along, i try to do this with new code i write.

Note that almost everything is stored in ram. local maps use a cache and are paged to and from disk as
needed. Cavern maps are generated as needed, saved when you leave a cavern, and loaded when you
re-enter a cavern.


Part 5:
https://www.gamedev.net/blog/1730/entry-2260302-the-building-of-caveman-part-5-general-code-organization/