nu.kanga.list.mud-dev

987: Re: [MUD-Dev] Neighborhood watch

On Sat, 28 Jun 1997 clawrenc@cup.hp.com wrote:

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

Case 1 - fixed unit coordinate systems... best handled by either a square
based system, such that

A B C  |  A has neighbors B, E, D. B has A, C, D, E, F. E has all the
D E F  |  rest. Transition occurs at the midpoint.
G E H  |


Or a hexagonal system, such that

 A B  |  A has neighbors B, D, C. D has all others as neighbors.
C D E |
 F G  |

The above can be stored in a square, of course.

A B C D E  |    A B C D E  |   A B   | This allows a bitshift to monitor
F G H I J  |   F G H I J   |  F G H  | transition from one node to the
K L M N O  |  K L M N O    |   L M   | next. Pointer arithmatic may not
P Q R S T  | P Q R S T     |         | be cool, but the GURU is too big

for any other option, so the above was my original design. This has
changed since.

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

Option 2... variable size... here we are assuming density as a reasonable
criteria for neighborhoods. Personally, I disagree, but I'll get to that
later. Accepting density, we have two options: fluid neighborhoods and
semistatic neghborhoods. The fluid neighborhood changes every time a new
object shows up, or leaves. The semistatic neighborhood is generated to
the mean neighborhood size at initialization, and each neighborhood
handles fissioning and requests for fusion (and possible refission) on the
basis of passing a threshhold. Example: Mean (optimal population) of 30
items. Maximum of 100, minimum of 10. The following neighborhoods
currently exist:

A  B C    D  E
  F    G      H
I    J        K
   L   M  N   O

Each has a population of 30, and occupies the space halfway to the nearest
neighbor in each direction. This is fine, until 21 each from A and B move
into F, as 29 new objects are generated in F. F fissions into two new
entities, and A and B each request mergence with F (not yet knowing about
the two new neighbors), and each other, and B from C as well. A and B
should negotiate to merge, if this is written properly, as they fall well
within range merged (eighteen.)

: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?

This assumes fixed size neighborhoods, which does not, from experience,
mix well with questionable existancce of neighborhoods. Now, I DO use a
similar concept for the GURU project, but...

  1 2 3 4 5 6 7 8 9 0
1  ..........
2  ..oooooo..
3  ..ooXXoo......
4  ..oooooooooo..
5  ......ooYYoo..
6      ..oooooo..
7      ..........
8

The above shows the range of a character's passive sensory capabilities.
The range of visability is the current node (fixed size) plus the
neighboring node (reduced priority) and the neighboring to that (minimum
priority) Within each region, filters are applied, and priority is ranked.
A character is only given detailed info on things over a certain priority,
and in textform, only a certain number of info units. Now... the concept
of the project is such that any two regions that intersect, as above, are
controlled by a single thread (sliced threads) and fusion and fission of
threads and regions is commonplace. This puts the burden of these
partitions on player units, rather than generic objects. A larger region
is allocated more resources. This seems, overall, more productive than
variable size neighborhoods.

: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?

Not really.

:--<cut>--
:
:>From: "Brandon J. Rickman" <ashes@pc4.zennet.com>
:>To: mud-dev@null.net
:>Subject: [MUD-Dev]  Room-based vs. coordinate-based
:
:alexo@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...

I am wary of this... I have already begun a series of optimizations to
allow linear or better collision detections, but I like the creation of
neighborhoods on the basis of design, rather than arbritrary concerns. (A
forest is a natural neighborhood, as is a glade within it... half a forest
is not.) This may be influenced by my concentric neighborhoods approach.

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

You are aware that I consider the trend toward complete seperation of
server and behavior a negative one. I suppose I am a minority on this one,
like the "levels" people on that issue, but there it is. I like having
support for what I consider fundamental constructs inherent in the server.
Locations, Physicality, and so forth... As such, I use my neighborhoods as
the center, and having Physical manifestations within them is not a
requirement. A physical object CANNOT, however, exist outside of a
location.

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

Or you take another tack... maintain the neighborhood, but create a
sub-locality or two within it. This is already used as an optimization for
collision detection in a number of games. (I can even see applications of
massing containers here...)

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

OK... it works well enough...

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

Right... similar to my filters, in effect. (Filters can control message
passing, and act as routers. They overload, simulating sensory overload,
if pushed.)

: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@zennet.com
:
:--<cut>--

This is good... I was missing this sort of hard core discussion.

   __    _   __  _   _   ,  ,  , ,  
  /_  / / ) /_  /_) / ) /| /| / /\            First Light of a Nova Dawn
 /   / / \ /_  /_) / \ /-|/ |/ /_/            Final Night of a World Gone
Nathan F. Yospe - University of Hawaii Dept of Physics - yospe@hawaii.edu