<!-- 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>