[MUD-Dev] Room-based vs. coordinate-based

[Brandon J. Rickman]

alexo at bigfoot.com (Alex Oren) wrote:
>Shawn wrote:
>}[... containers ...]

>The desert of desolation stretches from (500,200) to (900,500).
>Bubba is in the desert (620,342).
>Boffo is in the desert (621,343).
>Wesley is in the desert (888,472).
>Humperdink arrives (from the north, obviously), his position is now (621,342).

>If the (huge) desert is defined as one room, who gets the message? Why?
>If there was no explicitly defined room, who gets the message? Why?

>[The expected answer is: Bubba and Boffo]

To briefly cast aside the [more combat-oriented] concerns of coordinate
systems...

I think containers (or neighborhoods as my mathematical background would have
me call them) are key to providing an interesting location oriented mud.  It
would seem to be relatively easy to create static neighborhoods (room-based
muds are merely an extreme example of this), so the challenge is to allow
for dynamically constructable and scalable neighborhoods that are also
reasonably efficient.  Whatever we do, it couldn't possibly be worse than the
n^2 of normal collision detection...

- a not-so-rigorous implementation -

For any collection of N objects in space we want to create a collection of 
<N neighborhoods each containing 1 to k (hmm, sqrt(N)?) objects.  So we find
two sufficiently distant objects and create neighborhoods for them.   Then we
expand those neighborhoods to include whatever nearby objects there are.
Now we pick any of the homeless objects and create a new neighborhood for them,
including nearby objects, &c.  *Each object will be in at least one 
neighborhood, but may be in several.*  This is where we break from the 
very very very very very bad practice of MOO, where object containment was
built into the server.  (One might say that this allowed for a certain amount
of optimization on the server's part, which hints that any new implementation
might also benefit from being hard coded into the server.  I couldn't say if
this would make any sense with a distributed database...)

So now we have <N neighborhoods scattered on a plane (or line, space, n-space,
whatever).  An object propagating an event only has to propagate in its 
neighborhoods (*) (which at worst would be _all_ of them).  The movement of
objects is a special case where we check the object's distance to all the
neighborhoods and determine where to add or remove the object.

((*) It may also need to propagate in neighboring neighborhoods...)

To create a room we define the persistant neighborhood(s) that exist even when
they are empty (eh, perhaps they actually contain themselves?).  But if we get
too many objects in the same room we have the same collision detection problem
we started with, so we want to split up the room into a few sub-neighborhoods.

- An easy example -

Bubba, Boffo, and Wesley are in the desert as above.  Bubba and Boffo are
in the same set.  Wesley has his own set.  Humperdink "enters" (from hyper
north, since he wasn't "in" the space before...) and, after 2 checks (which
is less than 3) he ends up joining the Bubba/Boffo neighborhood.

(n.b. neighborhoods aren't particularly interesting or even efficient with
small/trivial examples.)

Boffo doesn't like Humperdink (he wears too much CK1) so he wanders off to 
the northeast towards Wesley.  The Bubba/Boffo/Humperdink neighborhood
expands as needed.  About halfway between the two neighborhoods,
Boffo finds himself equally distant from Bubba/Humberdink and Wesley.  He
gets added to Wesley's neighborhood.

Now if something horrible were to happen to Boffo at this point, the other
three characters would witness it because the event would propagate to their
neighborhoods.

- Shoehorn and the magic hat -

Shoehorn and a dozen other characters are in a room.  Shoehorn takes off his
magic hat and puts out a rabbit.  Then he pulls out another rabbit.  And
another.  Dozens and dozens of rabbits.

We start with one neighborhood, [Shoehorn, 1, 2, 3, .. 12].  If we limit the
maximum number of object in a set to 13, then adding a rabbit will require us
to split this neighborhood into two (or more) sets.  Eight characters are
standing near Shoehorn (hm, some bad graphics might be useful here, oh well)
and the other four, plus 7 and 8, are near a corner.

After trick #1:
#1[Shoehorn, 1, 2, 3, 4, 5, 6, 7, 8, rabbit1] - #2[7, 8, 9, 10, 11, 12]

Only the folks in Shoehorn's group see the next three tricks...

After trick #4:
#1[Shoehorn, 1-8, rabbit1-rabbit4] - #2[7-12]

Things start to get a little crazy, rabbits are hopping everywhere...

After trick #5:
#1[Shoehorn, 1, 2, 3, 4, rabbit2, rabbit3, rabbit5] -
#2[4, 5, 6, 7, rabbit1, rabbit3] -
#3[7, 8, 9, 10, 11, rabbit4] -
#4[11, 12]

Character 7 starts attacking rabbit1.  Everyone in set #3 can see the
attack clearly.  The folks in set #3 can see that 7 is attacking
_something_.  Otherwise the room is too crowded for everyone to see
everything that is going on.  

Well, I've spent too much time on this message.  Some extensions might deal
with differently sized objects, or a clever method for splitting up the
neightborhoods.

Note that these neighborhood arrangements are for VR purposes equivalent:

[1, 2] - [1, 3] - [2, 3, 4]
[1, 2, 3] - [2, 4] - [3, 4]
[1, 2, 3] - [2, 3, 4]

but not: [1, 2] - [1, 3] - [2, 4] - [3, 4]
because 2 and 3 must share a neighborhood somewhere.

- Brandon Rickman
ashes at zennet.com