<!-- MHonArc v2.4.4 --> <!--X-Subject: [MUD-Dev] Re: Nested Coordinate spaces. --> <!--X-From-R13: X Q Znjerapr <pynjNhaqre.rate.ftv.pbz> --> <!--X-Date: Tue, 30 Jun 1998 16:36:45 -0700 --> <!--X-Message-Id: 199806302321.QAA00705#under,engr.sgi.com --> <!--X-Content-Type: text/plain --> <!--X-Reference: 358FC655.FC72B39D#caip,rutgers.edu --> <!--X-Head-End--> <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"> <html> <head> <title>MUD-Dev message, [MUD-Dev] Re: Nested Coordinate spaces.</title> <!-- meta name="robots" content="noindex,nofollow" --> <link rev="made" href="mailto:claw#under,engr.sgi.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="msg01276.html">Previous</a> | <a href="msg01278.html">Next</a> ] Thread: [ <a href="msg01195.html">Previous</a> | <a href="msg00931.html">Next</a> ] Index: [ <A HREF="author.html#01277">Author</A> | <A HREF="#01277">Date</A> | <A HREF="thread.html#01277">Thread</A> ] <!--X-TopPNI-End--> <!--X-MsgBody--> <!--X-Subject-Header-Begin--> <H1>[MUD-Dev] Re: Nested Coordinate spaces.</H1> <HR> <!--X-Subject-Header-End--> <!--X-Head-of-Message--> <UL> <LI><em>To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI> <LI><em>Subject</em>: [MUD-Dev] Re: Nested Coordinate spaces. </LI> <LI><em>From</em>: J C Lawrence <<A HREF="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</A>></LI> <LI><em>Date</em>: Tue, 30 Jun 1998 16:21:38 -0700</LI> <LI><em>Reply-To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI> </UL> <!--X-Head-of-Message-End--> <!--X-Head-Body-Sep-Begin--> <HR> <!--X-Head-Body-Sep-End--> <!--X-Body-of-Message--> <PRE> On Tue, 23 Jun 1998 11:14:30 -0400 Elis Pomales<pomales#caip,rutgers.edu> wrote: > I've been thinking of using a b-trees with morton coded keys for my > objects (one tree per "area") and a quad tree (or several) for area > information (again per "area"). Though the biggest problem I > currently see, for this and for the R*-Tree is in how you store the > actual players? I mean players move around, thus requiring a delete > and an insert... Sooo is this ideal? Am I thinking along the wrong > track? I like R*Trees but have yet to find enough info on em (am > trying to get a good book and spatial representations.) I don't have time to check right now, but IIRC the Stony Brook Algorithms site covered the area fairly well. I really like the neighborhood concept, and have been thinking seriously about looking at it again in my Linux port. The fact that neighborhoods integrate so well (sorta) with R*-Tree helps (think of them as rectangles generated from the bottom up as versus top-down). Currently I take a very expensive approach for the context for mobile objects: I create a semi-private not-really-a-rectangle for them and remove objects when I notice that they are out of range (ie I don't go looking, reactive rather than proactive). Its not really a rectangle in that I'm very unaggressive about removing objects from the rectangle which are out of range -- instead I remove them when and if I notice them being out of range. Similarly its semi-private in that sloppy rectangles are sticky and will attempt to share themselves (ie a small crowd of players maintains only one sloppy rectangle which is shared across all characters, rather than one rectangle per player). This of course creates two types of rectangles: those that are accurate, and those that we hope are accurate. Only (potentially) rapidly moving objects maintain hopeful rectangles (actually they are created upon rapid movement and then are eventually torn down upon too little movement (slow enough movement and full query/rectangle generation is cheaper)). Rectangles are built based on queries. An incoming query first looks for a rectangle which fits the query within fairly sloppy tolerances (ie a larger enclosing rectangle that isn't too much larger). If it find one, then it uses that rectangle as its reply -- after all the processing code has to qualify objects anyway, and so can handle the (hopefully slight) extra load of the objects enclosed by the space between the borders of the wished-for rectangle and the returned rectangle. +-----------------------+ |\ | | Returned rectangle | | | | +----------------+ | | |\ | | | | Queried | | | | rectangle | | | | | | | | | | | | | | | +----------------+ | | | +-----------------------+ The pessimal case of course is: +-----------------------+ |\ | | Returned rectangle | | | | +----------------+## | | |\ |## | | | Queried |## | | | rectangle |## | | | |## | | | |## | | | |## | | +----------------+## | | #################### | | #################### | +-----------------------+ Where the #'s represent very high object concentrations *just* outside the desired rectangle's borders. While I don't attempt to handle this currently (I was hoping to think of a decent detection algorithm for this case so that I could then kick in other more expensive intelligence only when needed -- I just haven't thought of a decent detection method yet). If a decent matching rectangle for the query can't be found, then I generate a new rectangle. Theoretically rectangles are maintained on a sort of LRU cache basis. This means that each rectangle retains two stats: a last accessed value (ie this rectangle was the answer to a query), and a last referenced value (ie this rectangle was used as a resource to answer a query (eg as an enclosing or component rectangle in generating a new rectangle)), and I then tear down rectangles as they fall out of use. Note that I don't go looking for stale rectangles however. I merely note them in other more typical processing, and throw them onto a queue for a background thread to tear down at low priority. -- J C Lawrence Internet: claw#null,net (Contractor) Internet: coder#ibm,net ---------(*) Internet: claw#under,engr.sgi.com ...Honourary Member of Clan McFud -- Teamer's Avenging Monolith... </PRE> <!--X-Body-of-Message-End--> <!--X-MsgBody-End--> <!--X-Follow-Ups--> <HR> <!--X-Follow-Ups-End--> <!--X-References--> <UL><LI><STRONG>References</STRONG>: <UL> <LI><STRONG><A NAME="01177" HREF="msg01177.html">[MUD-Dev] Re: Nested Coordinate spaces.</A></STRONG> <UL><LI><EM>From:</EM> Elis Pomales <pomales#caip,rutgers.edu></LI></UL></LI> </UL></LI></UL> <!--X-References-End--> <!--X-BotPNI--> <UL> <LI>Prev by Date: <STRONG><A HREF="msg01276.html">[MUD-Dev] Re: WIRED: Kilers have more fun</A></STRONG> </LI> <LI>Next by Date: <STRONG><A HREF="msg01278.html">[MUD-Dev] Re: darkness/visibility</A></STRONG> </LI> <LI>Prev by thread: <STRONG><A HREF="msg01195.html">[MUD-Dev] Re: Nested Coordinate spaces.</A></STRONG> </LI> <LI>Next by thread: <STRONG><A HREF="msg00931.html">[MUD-Dev] Re: MUDZilla -- commercial server base</A></STRONG> </LI> <LI>Index(es): <UL> <LI><A HREF="index.html#01277"><STRONG>Date</STRONG></A></LI> <LI><A HREF="thread.html#01277"><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>[MUD-Dev] Re: Nested Coordinate spaces.</STRONG>, <EM>(continued)</EM> <ul compact> <LI><strong><A NAME="01140" HREF="msg01140.html">[MUD-Dev] Re: Nested Coordinate spaces.</A></strong>, J C Lawrence <a href="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</a>, Fri 19 Jun 1998, 17:22 GMT <UL> <LI><strong><A NAME="01144" HREF="msg01144.html">[MUD-Dev] Re: Nested Coordinate spaces.</A></strong>, Nathan F Yospe <a href="mailto:yospe#hawaii,edu">yospe#hawaii,edu</a>, Fri 19 Jun 1998, 18:50 GMT <UL> <LI><strong><A NAME="01177" HREF="msg01177.html">[MUD-Dev] Re: Nested Coordinate spaces.</A></strong>, Elis Pomales <a href="mailto:pomales#caip,rutgers.edu">pomales#caip,rutgers.edu</a>, Tue 23 Jun 1998, 15:23 GMT <UL> <LI><strong><A NAME="01195" HREF="msg01195.html">[MUD-Dev] Re: Nested Coordinate spaces.</A></strong>, Michael Hohensee <a href="mailto:michael#sparta,mainstream.net">michael#sparta,mainstream.net</a>, Wed 24 Jun 1998, 23:39 GMT </LI> <LI><strong><A NAME="01277" HREF="msg01277.html">[MUD-Dev] Re: Nested Coordinate spaces.</A></strong>, J C Lawrence <a href="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</a>, Tue 30 Jun 1998, 23:36 GMT </LI> </UL> </LI> </UL> </LI> </UL> </LI> </ul> </LI> <LI><strong><A NAME="00931" HREF="msg00931.html">[MUD-Dev] Re: MUDZilla -- commercial server base</A></strong>, John Bertoglio <a href="mailto:alexb#internetcds,com">alexb#internetcds,com</a>, Wed 10 Jun 1998, 03:34 GMT <UL> <LI><strong><A NAME="01141" HREF="msg01141.html">[MUD-Dev] Re: MUDZilla -- commercial server base</A></strong>, J C Lawrence <a href="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</a>, Fri 19 Jun 1998, 17:40 GMT </LI> </UL> </LI> <LI><strong><A NAME="00928" HREF="msg00928.html">[MUD-Dev] LDAP server as ...</A></strong>, Vadim Tkachenko <a href="mailto:vt#freehold,crocodile.org">vt#freehold,crocodile.org</a>, Wed 10 Jun 1998, 02:15 GMT <UL> <LI><strong><A NAME="01134" HREF="msg01134.html">[MUD-Dev] Re: LDAP server as ...</A></strong>, J C Lawrence <a href="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</a>, Fri 19 Jun 1998, 02:03 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>