q-tree stuff

[Chris Gray]

Thanks Todd! The picture came out fine on my Amiga, so it must have
worked on PC's, right? :-)

To summarize my understanding here (you never know, I could have missed
it altogether!), objects are stored in B-trees, in which the index is
the Morton code (or some other similar function) of the co-ordinates of
the object. Objects that are "nearby" in the co-ordinate space are
nearby in the B-tree, so searching for them is much faster than any kind of
linear scan of the whole set of objects. This works well in a setup where
there isn't a specific data structure for each location in the world, on
which to hang the object list, and on which to hang pointers to nearby
locations. Given a co-ordinate, it is fairly quick to find what would
be there, and keeping track of the B-tree search path lets you find the
nearest objects easily too.

I did a game system for CP/M, which was kinda like the old Ultima games.
I had "grids" representing tile-based surface maps, and "mazes" representing
the underground 3D view areas (line-drawing only - this *was* on a 1 Mhz
8080 with 64K RAM, including the graphics card). I had a global linked
list of all objects in the grid or maze, and simply did a linear scan,
checking the co-ordinates, in order to find things. This worked since I
was in a small world with only a few dozen objects (if that!), but it sure
wouldn't have worked in a big world with hundred's of objects.

To follow on to that, I'll mention how I did "special" things. I used
something like 6 bits to select the terrain for each location in a grid.
The terrain value gave me the tile, and the monster-set. One value said
"special". When I found that, I would search for that location in the
grid's list of special terrains. That gave me a new tile and/or monster
set. The Morton-indexed B-trees could be used for these terrain things in a
bigger world. The final tree entry could be a pointer to a database entry
giving detailed information for that special location. Similarly, for
3-D maze areas, the basic entry in the description array could give bits
describing the walls/floor/ceiling. "Special" entries could be used for
things like hidden doors, traps, monster triggers, etc. in a similar way.

If your "grids" get *very* big, so that having an array for them is not
practical, then you do as Todd said - just have quad-trees representing
the various properties that are needed to describe the location (terrain
type, monster sets, weather, temperature, etc.) You can layer the whole
thing - if you need smaller regions within your large world that are too
varied for efficient storage using quadtrees, then you can have a B-tree
entry for them that points to an array-based description, which in turn
can point at a few special single-location descriptions.

Note that in some cases you may be able to use a simple function on the
co-ordinates to calculate some properties, rather than having to store
it is a quadtree. Pseudo-random number generators, seeded by the co-ordinates,
are something I've always had in mind for this. I did it once in a little
CRT-based system (curses/termcap), and it worked OK, but not super.

--
Chris Gray   cg at ami-cg.GraySage.Edmonton.AB.CA