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

[Dan Armstrong]

On Thursday, August 07, Michael Hohensee wrote:

> 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. 

This enterprising player would first need to find that many objects.  The
most available source of many objects would have to be coins.  They
could walk around dropping one coin about every four or five steps, but
I see this as a self remedying problem.

If they chose to try and drop enough objects to fill the world, and
succeeded, it would take about nine trillion bytes of ram, just to point
to the objects.  Considering that an array takes four trillion, and doesn't
include an easy way of finding the position of a given object without
storing its coordinates, I don't feel too bad about this method.

Any way I look at it, it seems expensive.  I'm just trying to compress
the empty space the best I can without excessive loss in speed and
keep the game small enough for today's computers to handle.

Dan Armstrong