Quadtrees?

[S001GMU at nova.wright.edu]

>As far as objects go, their are various point-based structures that come to
>mind including the sparse matrix, K-D trees, and point-based quadtrees.
>Depending on how fancy you want to be, it's handy not only to ask "is there
>an object here?" but it is also handy to look for the nearest object from
>here.. let's you do things like bring critters to life only when folks
>approach (or leave), also let's you determine a range for how far folks can
>hear things that hum, see things that are lit, etc. The classic
>implementation is pointer-based, but for large implementations (and we
>expect to index several thousand items) there are linear implementations.
>Basically you implement a B-Tree and then use some space-filling curve
>(Peano, Hilbert et. al.) to index the tree's contents (your objects). The
>Peano or Morton curve is particularly nice 'cuz you can do algebra on it
>and the code also implicitly tells you the depth and quadrant of the
>corresponding pointer-based tree. The B-Tree behavior works well for a mud
>cuz usually huge chunks of your world aren't being played... so you just
>cache the active nodes/pages of the tree. Insertion and deletion can be
>expensive, but there are all sorts of ways to fudge things so you don't
>rebuild the tree every time. For rooms (walls etc.) the tree becomes
>read-only. Or am I going way overboard here?

do you know of any good books that I can read up on some of those algorithms
specifically the Peano, Hilbert or Morton curves you mentioned?

I'd say, instead of using a read only tree to handle objects that characters
can't move (like the walls of a room or something), just attach a weight and
structural integrity to the object, where the structural integrity shows how
much weight an object can take (counting it's own) before it collapses.  Just
set the weight fairly high (a few tons?  :) and the structural integrity to
the weight of the object (for fragile objects).  Lifting the object would
apply an unballanced force on the object, which for MUD purposes we can
probably get away with counting as weight.  That way, if someone did manage to
lift the wall, it'd probably fall apart all over them, unless they used some 
other means to increase it's structural integrity.  If you felt like it you
could actaully calculate the forces involved and get more detail out of it,
but for most purposes I think it'd be sufficient to just assume an object with
weight = structural integrtiy would fall apart when moved.

I think it'd make things much more interesting.  You could do things like have
corpses crumble just by being touched (to simulate incredible age), or walls
collapse on characters, etc.  

we've had discussions before about how to deal with areas where no players
happen to be hanging out...  I think we decided it'd depend on how much of a
simulation you want your mud to be.  :)

-Greg