Neighborhood watch

[clawrenc at cup.hp.com]

Some time ago I promised a summary of the neighborhoods concept.  I've
encluded the original post from Brandon on the subject below.

The basic concept of a neighborhood as discussed and defined by
Brandon is very simple.  Its possibly easist to think of with a model:

  Take a piece of graph paper.

  This is your "MUD World".  The graph on the paper represents the
coordinate space of your world.

  Randomly draw dots at the various line intersections on the graph
paper.

  These dots represent your objects in your MUD world.  Their
coordinates on the graph paper represents their coordinate positions
in the MUD world.

  The problem is to allow simple fast processing by a server of those
dot locations and represented objects with minimal overhead.

The neighborhood model:

  Get a sack full of coins.  Something about 1cm or 2cm in diameter
will fine.  

  Your job is to place those coins on the graph paper so that every
single dot is covered by a coin.

  Your job is also to attempt to minimise the number of coins used.

  The area covered by each coin represents a neighborhood.  

  Sometimes the coins are going to end up overlapping.  Any dot/object
that lies underneath multiple coins "belongs" to all of those
neighborhoods.

Neighborhood challenge:

  To keep system processing of neighborhoods simple and efficient,
next require that no coin may cover more than X dots (say 3 for now).   


  Of a sudden selection of coin placement becomes tough.  In certain
cases it can become impossible.

    eg. Consider the case where every single intersection on the graph
paper has a dot.  If your coins are (say) five units of the graph
paper granularity in diameter, there is no way to put a coin down
there and only have it cover 3 dots.  

One solution is to allow the diameter of coins/neighborhoods to vary. 
In very dense areas the diameter of the neighborhoods would be small,
but they would all be "full" of objects.  In very sparse areas the
diameter of the neighborhoods would be similarly large, and many would
be only sparsely populated.  Note: Due to the fact that circles can't
tesselete to cover an area (or spheres a volume), the cicles will
often end up overlapping in the familiar hex pattern.

Varying the diameter in this way makes the task of "deciding where to
place the coins" all the more difficult.  Further as your objects can
actually move about the world, a once sparsely populated neighborhood
can easily turn into an incredibly heavily populated neighborhood when
say a character carrying a very large inventory enters a room, or
approaches another character with a similarly large inventory.

Most of the discussion which has occurred on this neighborhood concept
has centered about two points how to propagate an event across
neighborhoods?

The obvious answer is for an event to propogate to the neighborhood it
occurs in, and from there to all neighborhoods it intersects until it
reaches a neighborhood which is out of range.  This works quite well
for the simple case:

  #############
  ##aaaaaaaaa##
  ##aaaaaaaaa##
  ##aaaaaaaaa##  # is a neighborhhod.
  ##aaaaaaaaa##  E is where the event originated.
  ##aaaaEaaaa##  a are the neighborhoods the event propagated to.
  ##aaaaaaaaa##
  ##aaaaaaaaa##
  ##aaaaaaaaa##
  ##aaaaaaaaa##
  #############

The problem is that this requires a very regular arrangement of
neighborhoods (cf quad-tree, oct-tree).  Given the random placement of
dots on the original graph paper as above, the resultant placement of
neighborhoods will also be random.  Additionally there is not
necessity for any part of the graph paper not containing any objects
to actually be a part of any neighborhood.

Now, given the same event, consider the case of:

  #############
  ##aaaaa  xx##
  ##aaaaa  xx##
  ##aaaaa  xx##  # is a neighborhhod.
  ##aaaaa  xx##  E is where the event originated.
  ##aaaaE  xx##  a are the neighborhoods the event propagated to.
  ##   aa  xx##    propagated to.
  ##       xx##  x are neighborhoods the event DIDN'T propagate to.
  ##xxxxxxxxx##  and the whitespace areas contain NO neighborhoods.
  ##xxxxxxxxx##
  #############

The problem here is that the efvent can't reach the 'x' neighborhoods
as they don't intersect any neighborhoods which are within range of
the event, __BUT__ they themselves are within range of the event.  The
lack of the "joining" neighborhood prevents them from receiving the
event.  THink this this isn't a problem?

Consider the case of a volcanoe in the middle of the desert.  The
desert is pretty uniformly featureless and so contains very few
objects, and thus almost no neighborhoods.  The volcanoe erupts. 
Boom!  Everybody and everything within hundreds of mile should both
hear and see this eruption.  Problem: The players in a small group
near the volcanoe all lie within a small island of neighborhoods which
are not connected to anything.  That small group of neighorhoods
intersects *nothing* else.  They never see the volcano go "Boom!".

Questions?

--<cut>--

>From: "Brandon J. Rickman" <ashes at pc4.zennet.com>
>To: mud-dev at null.net
>Subject: [MUD-Dev]  Room-based vs. coordinate-based

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

--<cut>--

--
J C Lawrence                           Internet: claw at null.net
(Contractor)                           Internet: coder at ibm.net
---------------(*)               Internet: clawrenc at cup.hp.com
...Honorary Member Clan McFUD -- Teamer's Avenging Monolith...