<!-- MHonArc v2.4.4 -->
<!--X-Subject: Re: [MUD-Dev] Room-based vs. coordinate-based -->
<!--X-From-R13: fvybivpNfepr.ue ([vebfyni Evybivp) -->
<!--X-Date: from fabius.globecomm.net [207.51.48.6] by in10.ibm.net id 866211167.38624-1 Fri Jun 13 14:12:47 1997 CUT -->
<!--X-Message-Id: 199706131412.QAA29450#regoc,srce.hr -->
<!--X-Content-Type: text/plain -->
<!--X-Reference: 3.0.2.32.19970612125348.00a28374#mail,tenetwork.com -->
<!--X-Head-End-->
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html>
<head>
<title>MUD-Dev message, Re: [MUD-Dev] Room-based vs. coordinate-based</title>
<!-- meta name="robots" content="noindex,nofollow" -->
<link rev="made" href="mailto:silovic#srce,hr">
</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="msg01319.html">Previous</a>
| <a href="msg01321.html">Next</a>
]
Thread:
[ <a href="msg01316.html">Previous</a>
| <a href="msg01322.html">Next</a>
]
Index:
[ <A HREF="author.html#01320">Author</A>
| <A HREF="#01320">Date</A>
| <A HREF="thread.html#01320">Thread</A>
]
<!--X-TopPNI-End-->
<!--X-MsgBody-->
<!--X-Subject-Header-Begin-->
<H1>Re: [MUD-Dev] Room-based vs. coordinate-based</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] Room-based vs. coordinate-based</LI>
<LI><em>From</em>: <A HREF="mailto:silovic#srce,hr">silovic#srce,hr</A> (Miroslav Silovic)</LI>
<LI><em>Date</em>: Fri, 13 Jun 1997 16:12:41 +0200 (MET DST)</LI>
</UL>
<!--X-Head-of-Message-End-->
<!--X-Head-Body-Sep-Begin-->
<HR>
<!--X-Head-Body-Sep-End-->
<!--X-Body-of-Message-->
<PRE>
> At 09:24 AM 6/12/97 PST8PDT, you wrote:
> >I'm working on R-tree based rooms (but I suspect I'll have to move my
> >current R-tree implementation into the driver, since it's both complex
> >and critical).
>
> Interesting. Care to define an R-Tree, miro? The data structure for some
> reason is pulling up a blank for me.
>
Okay, it's similar to B-tree, and it's similar to what CJL is talking
about right now. It's a ballanced tree where all leafs are on the same
depth, and each of the upper nodes has between 2 and N children (good
number is N=5).
Each node has an associated rectangle, and rectangle associated with a
non-leaf node contains rectangles of its children. Now to add a node to
a tree, you go through the node's children, calculate the size increase
for each rectangle, and pick one with minimal volume (although this
part can be optimized - volume doesn't always work best). Then you
recursively add to the tree. Now, adding to a tree can return two nodes,
and if that happened, you list them both in your children list, and if
you got above N, split in two and return both. Finally, on top of the
tree, construct a new root if needed.
Deletion involves recursive merging of the nodes - if you're masochistic
enough, but you can simply delete empty subtree, and it'll still work
reasonably well.
The good point of this structure is that it can be dynamically updated
as leaves get deleted and inserted, and that dynamic update will only
examine a small percentage of all objects (if the number of objects is
sufficiently large).
Miro
</PRE>
<!--X-Body-of-Message-End-->
<!--X-MsgBody-End-->
<!--X-Follow-Ups-->
<HR>
<ul compact><li><strong>Follow-Ups</strong>:
<ul>
<li><strong><A NAME="01322" HREF="msg01322.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>
<ul compact><li><em>From:</em> Jeff Kesselman <jeffk#tenetwork,com></li></ul>
</UL></LI></UL>
<!--X-Follow-Ups-End-->
<!--X-References-->
<UL><LI><STRONG>References</STRONG>:
<UL>
<LI><STRONG><A NAME="01312" HREF="msg01312.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></STRONG>
<UL><LI><EM>From:</EM> Jeff Kesselman <jeffk#tenetwork,com></LI></UL></LI>
</UL></LI></UL>
<!--X-References-End-->
<!--X-BotPNI-->
<UL>
<LI>Prev by Date:
<STRONG><A HREF="msg01319.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></STRONG>
</LI>
<LI>Next by Date:
<STRONG><A HREF="msg01321.html">Room-based vs. coordinate-based</A></STRONG>
</LI>
<LI>Prev by thread:
<STRONG><A HREF="msg01316.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></STRONG>
</LI>
<LI>Next by thread:
<STRONG><A HREF="msg01322.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></STRONG>
</LI>
<LI>Index(es):
<UL>
<LI><A HREF="index.html#01320"><STRONG>Date</STRONG></A></LI>
<LI><A HREF="thread.html#01320"><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: [MUD-Dev] Room-based vs. coordinate-based</STRONG>, <EM>(continued)</EM>
<ul compact>
<ul compact>
<LI><strong><A NAME="01287" HREF="msg01287.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>,
coder <a href="mailto:coder#ibm,net">coder#ibm,net</a>, Wed 11 Jun 1997, 12:24 GMT
<UL>
<LI><strong><A NAME="01307" HREF="msg01307.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>,
Miroslav Silovic <a href="mailto:silovic#srce,hr">silovic#srce,hr</a>, Thu 12 Jun 1997, 15:19 GMT
<UL>
<LI><strong><A NAME="01312" HREF="msg01312.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>,
Jeff Kesselman <a href="mailto:jeffk#tenetwork,com">jeffk#tenetwork,com</a>, Fri 13 Jun 1997, 02:51 GMT
<UL>
<LI><strong><A NAME="01316" HREF="msg01316.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>,
coder <a href="mailto:coder#ibm,net">coder#ibm,net</a>, Fri 13 Jun 1997, 11:37 GMT
</LI>
<LI><strong><A NAME="01320" HREF="msg01320.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>,
Miroslav Silovic <a href="mailto:silovic#srce,hr">silovic#srce,hr</a>, Fri 13 Jun 1997, 21:12 GMT
<UL>
<LI><strong><A NAME="01322" HREF="msg01322.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>,
Jeff Kesselman <a href="mailto:jeffk#tenetwork,com">jeffk#tenetwork,com</a>, Sat 14 Jun 1997, 01:12 GMT
</LI>
</UL>
</LI>
</UL>
</LI>
</UL>
</LI>
</UL>
</LI>
</ul>
<LI><strong><A NAME="01300" HREF="msg01300.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>,
Brandon J. Rickman <a href="mailto:ashes#pc4,zennet.com">ashes#pc4,zennet.com</a>, Thu 12 Jun 1997, 08:54 GMT
<UL>
<LI><strong><A NAME="01310" HREF="msg01310.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>,
clawrenc <a href="mailto:clawrenc#cup,hp.com">clawrenc#cup,hp.com</a>, Fri 13 Jun 1997, 01:44 GMT
<UL>
<LI><strong><A NAME="01318" HREF="msg01318.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>,
Marian Griffith <a href="mailto:gryphon#iaehv,nl">gryphon#iaehv,nl</a>, Fri 13 Jun 1997, 13:28 GMT
</LI>
</UL>
</LI>
</UL>
</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>