<!-- MHonArc v2.4.4 -->
<!--X-Subject: Re: Quadtrees? -->
<!--X-From-R13: ptNnzv-pt.UenlEntr.Sqzbagba.OP.QO (Quevf Uenl) -->
<!--X-Date: from babe.globecomm.net [207.51.48.8] by mx01.ca.us.ibm.net id 857144971.53435-1 Fri Feb 28 15:49:31 1997 -->
<!--X-Message-Id: 9702281358.7udn@ami-cg.GraySage.Edmonton.AB.CA -->
<!--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:cg#ami-cg,GraySage.Edmonton.AB.CA">
</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="msg00020.html">Previous</a>
| <a href="msg00022.html">Next</a>
]
Thread:
[ <a href="msg00019.html">Previous</a>
| <a href="msg00022.html">Next</a>
]
Index:
[ <A HREF="author.html#00021">Author</A>
| <A HREF="#00021">Date</A>
| <A HREF="thread.html#00021">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>: <A HREF="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</A> (Chris Gray)</LI>
<LI><em>Date</em>: Fri, 28 Feb 97 06:58:53 MST</LI>
</UL>
<!--X-Head-of-Message-End-->
<!--X-Head-Body-Sep-Begin-->
<HR>
<!--X-Head-Body-Sep-End-->
<!--X-Body-of-Message-->
<PRE>
:I am wondering why quadtrees would be so great for spatial representation
:as it is used in a mud. As you will remember, a quadtree subdivides a
:region into 4 subregions and makes quadtrees of those until the subregions
:are uniform, so that you only keep information about things that are
:different in a region (ok this desc stinks). But in a mud you need to do
:lots of spatial relation searches, like all the objects within a range of 3.
:Why not use a list of objects that is multi indexed on X and Y values?
I'm certainly no expert in this stuff, but it seems to me that quadtrees
aren't being advised for individual objects, but for properties, the
value of which is needed at every location within the grid. As in the
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.
Objects are a different matter. They are each individual, and possibly
unique. With objects, the concern is more "what objects are here?". An
indexed sparse array of some kind works for that. Another possibility is
to have a quadtree that essentially represents "something-is-here-ness",
and terminates in pointers to lists of objects as needed. Most locations
contain nothing, and so are not explicitly represented in the quadtree.
The trouble with this is that it requires that the quadtree go down to
the individual location in resolution, whereas for other properties, they
can often stop considerably before that point. Also, objects can be moved,
resulting in the need to be able to dynamically change the quadtree. I
vaguely recall that that is hard to do.
My thinking has been to use a 3D sparse array, which can contain objects
of differing sizes, hence visibilities. I'm pretty vague on how the details
would work, however. :-(
--
Chris Gray cg#ami-cg,GraySage.Edmonton.AB.CA
</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="msg00020.html">Re: Just a bit of musing</A></STRONG>
</LI>
<LI>Next by Date:
<STRONG><A HREF="msg00022.html">Re: Quadtrees?</A></STRONG>
</LI>
<LI>Prev by thread:
<STRONG><A HREF="msg00019.html">Re: Quadtrees?</A></STRONG>
</LI>
<LI>Next by thread:
<STRONG><A HREF="msg00022.html">Re: Quadtrees?</A></STRONG>
</LI>
<LI>Index(es):
<UL>
<LI><A HREF="index.html#00021"><STRONG>Date</STRONG></A></LI>
<LI><A HREF="thread.html#00021"><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: q-tree stuff</STRONG>, <EM>(continued)</EM>
<ul compact>
<LI><strong><A NAME="00070" HREF="msg00070.html">Re: q-tree stuff</A></strong>,
coder <a href="mailto:coder#ibm,net">coder#ibm,net</a>, Sat 08 Mar 1997, 11:54 GMT
</LI>
</ul>
</LI>
<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>
</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>