<!-- MHonArc v2.4.4 -->
<!--X-Subject: Re: [MUD-Dev] Quad-trees/Oct-trees -->
<!--X-From-R13: [vpunry Vburafrr <zvpunryNfcnegn.znvafgernz.arg> -->
<!--X-Date: Fri, 08 Aug 1997 14:41:40 +0000 -->
<!--X-Message-Id: 33EB2F53.6BA3917C#sparta,mainstream.net -->
<!--X-Content-Type: text/plain -->
<!--X-Reference: 199708080243.QAA24348#mail,pixi.com -->
<!--X-Head-End-->
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html>
<head>
<title>MUD-Dev message, Re: [MUD-Dev] Quad-trees/Oct-trees</title>
<!-- meta name="robots" content="noindex,nofollow" -->
<link rev="made" href="mailto:michael#sparta,mainstream.net">
</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="msg00428.html">Previous</a>
| <a href="msg00430.html">Next</a>
]
Thread:
[ <a href="msg00426.html">Previous</a>
| <a href="msg00527.html">Next</a>
]
Index:
[ <A HREF="author.html#00429">Author</A>
| <A HREF="#00429">Date</A>
| <A HREF="thread.html#00429">Thread</A>
]
<!--X-TopPNI-End-->
<!--X-MsgBody-->
<!--X-Subject-Header-Begin-->
<H1>Re: [MUD-Dev] Quad-trees/Oct-trees</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: [MUD-Dev] Quad-trees/Oct-trees</LI>
<LI><em>From</em>: Michael Hohensee <<A HREF="mailto:michael#sparta,mainstream.net">michael#sparta,mainstream.net</A>></LI>
<LI><em>Date</em>: Fri, 08 Aug 1997 10:38:11 -0400</LI>
<LI><em>Sender</em>: <A HREF="mailto:michael#sparta,mainstream.net">michael#sparta,mainstream.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>
Dan Armstrong wrote:
> For storing objects I use a tree that is twenty levels high, based
> on the following pattern. Each level in the tree, except for the
> last, holds four smaller pieces of the tree. If any of those four
> are null, then there aren't any objects in the area covered by
> that piece. The last level in the tree is either null if nothing
> is there, or points to the head object of a linked list of every
> item that is at that location.
Sounds like a quad tree, based on what little understanding I have of
these "formal" definitions. :)
You could probably modify this to work in three dimensions, by turning
it into an oct-tree (each level holds eight smaller pieces of the tree).
There's just one problem. What do you do if some enterprising (read:
mischevious) player drops one object in each four (or eight) room
cluster? That'd cause your tree to create over 2^38 entries in the tree
to deal with them. Of course, there probably aren't that many objects
around, but even on a smaller scale, this looks like it could become
expensive.
--
Michael Hohensee michael#sparta,mainstream.net
<A HREF="http://www.geocities.com/SiliconValley/Heights/9025/">http://www.geocities.com/SiliconValley/Heights/9025/</A>
Finger me for my PGP Public Key, or use:
<A HREF="http://sparta.mainstream.net/michael/pgpkey.txt">http://sparta.mainstream.net/michael/pgpkey.txt</A>
</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="00426" HREF="msg00426.html">Introduction</A></STRONG>
<UL><LI><EM>From:</EM> "Dan Armstrong" <orion#pixi,com></LI></UL></LI>
</UL></LI></UL>
<!--X-References-End-->
<!--X-BotPNI-->
<UL>
<LI>Prev by Date:
<STRONG><A HREF="msg00428.html">Mud Languages (Introesque)</A></STRONG>
</LI>
<LI>Next by Date:
<STRONG><A HREF="msg00430.html">Re: [MUD-Dev] Mud Languages</A></STRONG>
</LI>
<LI>Prev by thread:
<STRONG><A HREF="msg00426.html">Introduction</A></STRONG>
</LI>
<LI>Next by thread:
<STRONG><A HREF="msg00527.html">Re: [MUD-Dev] Introduction</A></STRONG>
</LI>
<LI>Index(es):
<UL>
<LI><A HREF="index.html#00429"><STRONG>Date</STRONG></A></LI>
<LI><A HREF="thread.html#00429"><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="00428" HREF="msg00428.html">Mud Languages (Introesque)</A></strong>,
##Make Nylander <a href="mailto:thenewt#use,usit.net">thenewt#use,usit.net</a>, Fri 08 Aug 1997, 12:43 GMT
<UL>
<li><Possible follow-up(s)><br>
<LI><strong><A NAME="00432" HREF="msg00432.html">Re: Mud Languages (Introesque)</A></strong>,
##Make Nylander <a href="mailto:thenewt#use,usit.net">thenewt#use,usit.net</a>, Fri 08 Aug 1997, 18:55 GMT
<UL>
<LI><strong><A NAME="00440" HREF="msg00440.html">Re: [MUD-Dev] Re: Mud Languages (Introesque)</A></strong>,
Nathan Yospe <a href="mailto:yospe#hawaii,edu">yospe#hawaii,edu</a>, Sat 09 Aug 1997, 01:35 GMT
</LI>
</UL>
</LI>
</UL>
</LI>
<LI><strong><A NAME="00426" HREF="msg00426.html">Introduction</A></strong>,
Dan Armstrong <a href="mailto:orion#pixi,com">orion#pixi,com</a>, Fri 08 Aug 1997, 02:43 GMT
<UL>
<LI><strong><A NAME="00429" HREF="msg00429.html">Re: [MUD-Dev] Quad-trees/Oct-trees</A></strong>,
Michael Hohensee <a href="mailto:michael#sparta,mainstream.net">michael#sparta,mainstream.net</a>, Fri 08 Aug 1997, 14:41 GMT
</LI>
<LI><strong><A NAME="00527" HREF="msg00527.html">Re: [MUD-Dev] Introduction</A></strong>,
clawrenc <a href="mailto:clawrenc#cup,hp.com">clawrenc#cup,hp.com</a>, Thu 14 Aug 1997, 00:00 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="00424" HREF="msg00424.html">Re: [MUD-Dev] Mud Languages</A></strong>,
Chris Gray <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Thu 07 Aug 1997, 17:19 GMT
<UL>
<LI><strong><A NAME="00427" HREF="msg00427.html">Re: [MUD-Dev] Mud Languages</A></strong>,
Nathan Yospe <a href="mailto:yospe#hawaii,edu">yospe#hawaii,edu</a>, Fri 08 Aug 1997, 04:24 GMT
</LI>
<LI><strong><A NAME="00433" HREF="msg00433.html">Re: [MUD-Dev] Mud Languages</A></strong>,
Greg Munt <a href="mailto:greg#uni-corn,demon.co.uk">greg#uni-corn,demon.co.uk</a>, Fri 08 Aug 1997, 19:18 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>