<!-- MHonArc v2.4.4 --> <!--X-Subject: Re: Quadtrees? --> <!--X-From-R13: "Qnegre F Eubpx" <pgfbNhzvnpf.hzq.rqh> --> <!--X-Date: from major.globecomm.net [207.51.48.5] by mx01.ny.us.ibm.net id 857147198.113360-1 Fri Feb 28 16:26:38 1997 --> <!--X-Message-Id: 199702281626.LAA21890#rosebud,umiacs.umd.edu --> <!--X-Content-Type: text/plain --> <!--X-Head-End--> <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"> <html> <head> <title>MUD-Dev message, Re: Quadtrees?</title> <!-- meta name="robots" content="noindex,nofollow" --> <link rev="made" href="mailto:ctso#umiacs,umd.edu"> </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="msg00021.html">Previous</a> | <a href="msg00023.html">Next</a> ] Thread: [ <a href="msg00021.html">Previous</a> | <a href="msg00023.html">Next</a> ] Index: [ <A HREF="author.html#00022">Author</A> | <A HREF="#00022">Date</A> | <A HREF="thread.html#00022">Thread</A> ] <!--X-TopPNI-End--> <!--X-MsgBody--> <!--X-Subject-Header-Begin--> <H1>Re: Quadtrees?</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>: Re: Quadtrees?</LI> <LI><em>From</em>: "Carter T Shock" <<A HREF="mailto:ctso#umiacs,umd.edu">ctso#umiacs,umd.edu</A>></LI> <LI><em>Date</em>: Fri, 28 Feb 1997 11:25:57 -0500</LI> </UL> <!--X-Head-of-Message-End--> <!--X-Head-Body-Sep-Begin--> <HR> <!--X-Head-Body-Sep-End--> <!--X-Body-of-Message--> <PRE> > previous example, you could use one quadtree for 'forest-ness', another > for 'mountain-ness", etc. This allows you to automatically generate the > description/picture/representation of a location in the grid, based on > traversing the small quadtree to get the property value. exactly > > Objects are a different matter. They are each individual, and possibly > unique. With objects, the concern is more "what objects are here?". An Two points: 1) Quadtrees are not the be-all and end-all of spatial data structures. Just what came to mind as I wrote. 2) Quadtrees come in lots of flavors. The "forest-ness" et. al. would most likely be done as a region quadtree. It just works out that these are handy structures for binary spatial tests. Any region is either forest or it ain't. The particularly nice thing about these structures (versus other representations) is the ability to perform efficient spatial joins. Recall that you can use these puppies for more than simple terrain. If you support clans you can describe a clan's "zone of influence", you can do no magic, lawful, silent, safe, etc. areas. The spatial join property is more of an implemetor's bonus. It lets you ask questions like "show me all of the areas that are forest but no-magic" so you can tune those spots where (ferinstance) druid spells will fail. As far as objects go, their are various point-based structures that come to mind including the sparse matrix, K-D trees, and point-based quadtrees. Depending on how fancy you want to be, it's handy not only to ask "is there an object here?" but it is also handy to look for the nearest object from here.. let's you do things like bring critters to life only when folks approach (or leave), also let's you determine a range for how far folks can hear things that hum, see things that are lit, etc. The classic implementation is pointer-based, but for large implementations (and we expect to index several thousand items) there are linear implementations. Basically you implement a B-Tree and then use some space-filling curve (Peano, Hilbert et. al.) to index the tree's contents (your objects). The Peano or Morton curve is particularly nice 'cuz you can do algebra on it and the code also implicitly tells you the depth and quadrant of the corresponding pointer-based tree. The B-Tree behavior works well for a mud cuz usually huge chunks of your world aren't being played... so you just cache the active nodes/pages of the tree. Insertion and deletion can be expensive, but there are all sorts of ways to fudge things so you don't rebuild the tree every time. For rooms (walls etc.) the tree becomes read-only. Or am I going way overboard here? -Todd </PRE> <!--X-Body-of-Message-End--> <!--X-MsgBody-End--> <!--X-Follow-Ups--> <HR> <!--X-Follow-Ups-End--> <!--X-References--> <!--X-References-End--> <!--X-BotPNI--> <UL> <LI>Prev by Date: <STRONG><A HREF="msg00021.html">Re: Quadtrees?</A></STRONG> </LI> <LI>Next by Date: <STRONG><A HREF="msg00023.html">Re: Quadtrees?</A></STRONG> </LI> <LI>Prev by thread: <STRONG><A HREF="msg00021.html">Re: Quadtrees?</A></STRONG> </LI> <LI>Next by thread: <STRONG><A HREF="msg00023.html">Re: Quadtrees?</A></STRONG> </LI> <LI>Index(es): <UL> <LI><A HREF="index.html#00022"><STRONG>Date</STRONG></A></LI> <LI><A HREF="thread.html#00022"><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><A NAME="00033" HREF="msg00033.html">Linear Quadtrees</A></strong>, Carter T Shock <a href="mailto:ctso#umiacs,umd.edu">ctso#umiacs,umd.edu</a>, Sun 02 Mar 1997, 20:35 GMT <LI><strong><A NAME="00018" HREF="msg00018.html">Quadtrees?</A></strong>, Wout Mertens <a href="mailto:Wout.Mertens#rug,ac.be">Wout.Mertens#rug,ac.be</a>, Fri 28 Feb 1997, 10:54 GMT <UL> <LI><strong><A NAME="00019" HREF="msg00019.html">Re: Quadtrees?</A></strong>, coder <a href="mailto:coder#ibm,net">coder#ibm,net</a>, Fri 28 Feb 1997, 17:33 GMT </LI> </UL> <UL> <li><Possible follow-up(s)><br> <LI><strong><A NAME="00021" HREF="msg00021.html">Re: Quadtrees?</A></strong>, Chris Gray <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Fri 28 Feb 1997, 23:49 GMT </LI> <LI><strong><A NAME="00022" HREF="msg00022.html">Re: Quadtrees?</A></strong>, Carter T Shock <a href="mailto:ctso#umiacs,umd.edu">ctso#umiacs,umd.edu</a>, Sat 01 Mar 1997, 00:26 GMT </LI> <LI><strong><A NAME="00023" HREF="msg00023.html">Re: Quadtrees?</A></strong>, S001GMU <a href="mailto:S001GMU#nova,wright.edu">S001GMU#nova,wright.edu</a>, Sat 01 Mar 1997, 04:11 GMT </LI> <LI><strong><A NAME="00025" HREF="msg00025.html">Re: Quadtrees?</A></strong>, Carter T Shock <a href="mailto:ctso#umiacs,umd.edu">ctso#umiacs,umd.edu</a>, Sat 01 Mar 1997, 05:12 GMT </LI> <LI><strong><A NAME="00026" HREF="msg00026.html">Re: Quadtrees?</A></strong>, S001GMU <a href="mailto:S001GMU#nova,wright.edu">S001GMU#nova,wright.edu</a>, Sat 01 Mar 1997, 05:38 GMT </LI> <LI><strong><A NAME="00030" HREF="msg00030.html">Re: Quadtrees?</A></strong>, Chris Gray <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Sat 01 Mar 1997, 17:34 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>