<!-- MHonArc v2.4.4 --> <!--X-Subject: Neighborhood watch --> <!--X-From-R13: pynjerapNphc.uc.pbz --> <!--X-Date: from scipio.globecomm.net [207.51.48.12] by in2.ibm.net id 867430822.58678-1 Fri Jun 27 17:00:22 1997 CUT --> <!--X-Message-Id: 199706271658.JAA01638#xsvr3,cup.hp.com --> <!--X-Content-Type: text/plain --> <!--X-Head-End--> <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"> <html> <head> <title>MUD-Dev message, Neighborhood watch</title> <!-- meta name="robots" content="noindex,nofollow" --> <link rev="made" href="mailto:clawrenc#cup,hp.com"> </head> <body background="/backgrounds/paperback.gif" bgcolor="#ffffff" text="#000000" link="#0000FF" alink="#FF0000" vlink="#006000"> <font size="+4" color="#804040"> <strong><em>MUD-Dev<br>mailing list archive</em></strong> </font> <br> [ <a href="../">Other Periods</a> | <a href="../../">Other mailing lists</a> | <a href="/search.php3">Search</a> ] <br clear=all><hr> <!--X-Body-Begin--> <!--X-User-Header--> <!--X-User-Header-End--> <!--X-TopPNI--> Date: [ <a href="msg01558.html">Previous</a> | <a href="msg01560.html">Next</a> ] Thread: [ <a href="msg01574.html">Previous</a> | <a href="msg01588.html">Next</a> ] Index: [ <A HREF="author.html#01559">Author</A> | <A HREF="#01559">Date</A> | <A HREF="thread.html#01559">Thread</A> ] <!--X-TopPNI-End--> <!--X-MsgBody--> <!--X-Subject-Header-Begin--> <H1>Neighborhood watch</H1> <HR> <!--X-Subject-Header-End--> <!--X-Head-of-Message--> <UL> <LI><em>To</em>: <A HREF="mailto:mud-dev#null,net">mud-dev#null,net</A></LI> <LI><em>Subject</em>: Neighborhood watch</LI> <LI><em>From</em>: <A HREF="mailto:clawrenc#cup,hp.com">clawrenc#cup,hp.com</A></LI> <LI><em>Date</em>: Thu, 26 Jun 97 10:25:11 -0700</LI> <LI><em>Reply-to</em>: <A HREF="mailto:claw#null,net">claw#null,net</A></LI> </UL> <!--X-Head-of-Message-End--> <!--X-Head-Body-Sep-Begin--> <HR> <!--X-Head-Body-Sep-End--> <!--X-Body-of-Message--> <PRE> 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#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... - 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#zennet,com --<cut>-- -- J C Lawrence Internet: claw#null,net (Contractor) Internet: coder#ibm,net ---------------(*) Internet: clawrenc#cup,hp.com ...Honorary Member Clan McFUD -- Teamer's Avenging Monolith... </PRE> <!--X-Body-of-Message-End--> <!--X-MsgBody-End--> <!--X-Follow-Ups--> <HR> <ul compact><li><strong>Follow-Ups</strong>: <ul> <li><strong><A NAME="01588" HREF="msg01588.html">Re: [MUD-Dev] Neighborhood watch</A></strong> <ul compact><li><em>From:</em> Nathan Yospe <yospe#hawaii,edu></li></ul> </UL></LI></UL> <!--X-Follow-Ups-End--> <!--X-References--> <!--X-References-End--> <!--X-BotPNI--> <UL> <LI>Prev by Date: <STRONG><A HREF="msg01558.html">Re: [MUD-Dev] Population container</A></STRONG> </LI> <LI>Next by Date: <STRONG><A HREF="msg01560.html">Re: [MUD-Dev] Mob AI</A></STRONG> </LI> <LI>Prev by thread: <STRONG><A HREF="msg01574.html">Re: [MUD-Dev] Levels and XP</A></STRONG> </LI> <LI>Next by thread: <STRONG><A HREF="msg01588.html">Re: [MUD-Dev] Neighborhood watch</A></STRONG> </LI> <LI>Index(es): <UL> <LI><A HREF="index.html#01559"><STRONG>Date</STRONG></A></LI> <LI><A HREF="thread.html#01559"><STRONG>Thread</STRONG></A></LI> </UL> </LI> </UL> <!--X-BotPNI-End--> <!--X-User-Footer--> <!--X-User-Footer-End--> <ul><li>Thread context: <BLOCKQUOTE><UL> <LI><STRONG>Re: [MUD-Dev] Level abstractions - Realism vs Game Issues</STRONG>, <EM>(continued)</EM> <ul compact> <LI><strong><A NAME="01620" HREF="msg01620.html">Re: [MUD-Dev] Level abstractions - Realism vs Game Issues</A></strong>, Jon A. Lambert <a href="mailto:jlsysinc#ix,netcom.com">jlsysinc#ix,netcom.com</a>, Tue 01 Jul 1997, 06:52 GMT </LI> </ul> </LI> <LI><strong><A NAME="01563" HREF="msg01563.html">Re: [MUD-Dev] Levels and XP</A></strong>, Huibai <a href="mailto:ashen#pixi,com">ashen#pixi,com</a>, Sat 28 Jun 1997, 10:28 GMT <UL> <LI><strong><A NAME="01567" HREF="msg01567.html">Re: [MUD-Dev] Levels and XP</A></strong>, Nathan Yospe <a href="mailto:yospe#hawaii,edu">yospe#hawaii,edu</a>, Sat 28 Jun 1997, 11:43 GMT </LI> <LI><strong><A NAME="01574" HREF="msg01574.html">Re: [MUD-Dev] Levels and XP</A></strong>, Matt Chatterley <a href="mailto:root#mpc,dyn.ml.org">root#mpc,dyn.ml.org</a>, Sat 28 Jun 1997, 16:53 GMT </LI> </UL> </LI> <LI><strong><A NAME="01559" HREF="msg01559.html">Neighborhood watch</A></strong>, clawrenc <a href="mailto:clawrenc#cup,hp.com">clawrenc#cup,hp.com</a>, Sat 28 Jun 1997, 00:00 GMT <UL> <LI><strong><A NAME="01588" HREF="msg01588.html">Re: [MUD-Dev] Neighborhood watch</A></strong>, Nathan Yospe <a href="mailto:yospe#hawaii,edu">yospe#hawaii,edu</a>, Mon 30 Jun 1997, 05:41 GMT </LI> </UL> </LI> <LI><strong><A NAME="01550" HREF="msg01550.html">try it out!</A></strong>, Chris Gray <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Fri 27 Jun 1997, 13:04 GMT <LI><strong><A NAME="01544" HREF="msg01544.html">[MUD-Dev] Mob AI</A></strong>, Brandon Cline <a href="mailto:brandon#merlin,sedona.net">brandon#merlin,sedona.net</a>, Fri 27 Jun 1997, 04:42 GMT <UL> <li><Possible follow-up(s)><br> <LI><strong><A NAME="01557" HREF="msg01557.html">Re: [MUD-Dev] Mob AI</A></strong>, Chris Gray <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Fri 27 Jun 1997, 21:48 GMT </LI> </UL> </LI> </UL></BLOCKQUOTE> </ul> <hr> <center> [ <a href="../">Other Periods</a> | <a href="../../">Other mailing lists</a> | <a href="/search.php3">Search</a> ] </center> <hr> </body> </html>