[MUD-Dev] Quad-trees/Oct-trees

[Michael Hohensee]

Dan Armstrong wrote:

> For storing objects I use a tree that is twenty levels high, based
> on the following pattern.  Each level in the tree, except for the
> last, holds four smaller pieces of the tree.  If any of those four
> are null, then there aren't any objects in the area covered by
> that piece.  The last level in the tree is either null if nothing
> is there, or points to the head object of a linked list of every
> item that is at that location.

Sounds like a quad tree, based on what little understanding I have of
these "formal" definitions. :)

You could probably modify this to work in three dimensions, by turning
it into an oct-tree (each level holds eight smaller pieces of the tree).

There's just one problem.  What do you do if some enterprising (read:
mischevious) player drops one object in each four (or eight) room
cluster?  That'd cause your tree to create over 2^38 entries in the tree
to deal with them.  Of course, there probably aren't that many objects
around, but even on a smaller scale, this looks like it could become
expensive. 

--
Michael Hohensee       michael at sparta.mainstream.net
http://www.geocities.com/SiliconValley/Heights/9025/
      Finger me for my PGP Public Key, or use: 
http://sparta.mainstream.net/michael/pgpkey.txt