Quadtrees?

[Chris Gray]

:I am wondering why quadtrees would be so great for spatial representation
:as it is used in a mud. As you will remember, a quadtree subdivides a
:region into 4 subregions and makes quadtrees of those until the subregions
:are uniform, so that you only keep information about things that are
:different in a region (ok this desc stinks). But in a mud you need to do
:lots of spatial relation searches, like all the objects within a range of 3.
:Why not use a list of objects that is multi indexed on X and Y values?

I'm certainly no expert in this stuff, but it seems to me that quadtrees
aren't being advised for individual objects, but for properties, the
value of which is needed at every location within the grid. As in the
previous example, you could use one quadtree for 'forest-ness', another
for 'mountain-ness", etc. This allows you to automatically generate the
description/picture/representation of a location in the grid, based on
traversing the small quadtree to get the property value.

Objects are a different matter. They are each individual, and possibly
unique. With objects, the concern is more "what objects are here?". An
indexed sparse array of some kind works for that. Another possibility is
to have a quadtree that essentially represents "something-is-here-ness",
and terminates in pointers to lists of objects as needed. Most locations
contain nothing, and so are not explicitly represented in the quadtree.
The trouble with this is that it requires that the quadtree go down to
the individual location in resolution, whereas for other properties, they
can often stop considerably before that point. Also, objects can be moved,
resulting in the need to be able to dynamically change the quadtree. I
vaguely recall that that is hard to do.

My thinking has been to use a 3D sparse array, which can contain objects
of differing sizes, hence visibilities. I'm pretty vague on how the details
would work, however. :-(

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