<!-- MHonArc v2.4.4 -->
<!--X-Subject: Re: [MUD-Dev] Position sorting -->
<!--X-From-R13: pbqreNvoz.arg -->
<!--X-Date: Sat, 28 Feb 1998 05:04:31 +0000 -->
<!--X-Message-Id: 199802280504.FAA137516#out2,ibm.net -->
<!--X-Content-Type: text/plain -->
<!--X-Reference: 199802221311.GAA12050#user1,inficad.com -->
<!--X-Head-End-->
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html>
<head>
<title>MUD-Dev message, Re: [MUD-Dev] Position sorting</title>
<!-- meta name="robots" content="noindex,nofollow" -->
<link rev="made" href="mailto:coder#ibm,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="msg00642.html">Previous</a>
| <a href="msg00644.html">Next</a>
]
Thread:
[ <a href="msg00553.html">Previous</a>
| <a href="msg00548.html">Next</a>
]
Index:
[ <A HREF="author.html#00643">Author</A>
| <A HREF="#00643">Date</A>
| <A HREF="thread.html#00643">Thread</A>
]
<!--X-TopPNI-End-->
<!--X-MsgBody-->
<!--X-Subject-Header-Begin-->
<H1>Re: [MUD-Dev] Position sorting</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] Position sorting</LI>
<LI><em>From</em>: <A HREF="mailto:coder#ibm,net">coder#ibm,net</A></LI>
<LI><em>Date</em>: Fri, 27 Feb 98 20:50:42 -0800</LI>
<LI><em>Reply-to</em>: <A HREF="mailto:coder#ibm,net">coder#ibm,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>
On 22/02/98 at 10:07 AM, Adam Wiggins <nightfall#user1,inficad.com> said:
>A while back (I can't remember how long, maybe a year or so) someone
>posted the basics for an algorithm which involved interpolating the bits
>of an object's coordinates in game space in order to generate a sorting
>key.
"Morton Codes" as described by Carter T Shock -- alas, no longer on the
list.
>Recently something came up that made me think of that, and I wanted
>to reread the message, but it seems that I either never saved it or lost
>it during the system moves I've made since then.
>So...could someone dredge it up out of their archives and
>post it, or just explain it once again for me? I'd
>be much obliged...
--<cut>--
Date: Mon, 21 Apr 1997 08:18:29 PST8PDT
Reply-To: mud-dev#null,net
From: "Carter T Shock" <ctso#umiacs,umd.edu>
To: <mud-dev#null,net>
Subject: [MUD-Dev] Re: Quadtrees?
> do you know of any good books that I can read up on some of those
algorithms
> specifically the Peano, Hilbert or Morton curves you mentioned?
>
"The Design and Analysis of Spatial Data Structures" by Samet (Addison
Wesley) is a great primer on this stuff and spatial data structures in
general. However, save 30 bux...
Peano and Morton are two names for the same thing. A space filling curve
is one that can cover all the points in a grid without ever crossing over
itself. Hilbert is kinda odd and computationally a bit nasty to work with,
but Morton is easy.
In a nutshell: interleave the bits.
Given a coordinate [3,5] represented with 4 bits each you have: X = 0011
Y = 0101
Morton is: 00011011 or 00100111
0 0 1 1
0 1 0 1
00011011
Your choice as to whether to start with the X or Y bit as most
significant. Here's the sweet part... because the most significant bits of
the code represent the most significant bits of the two coordinates you
can use it as a sorting key. Codes that are numerically close are also
spatially close. There's also a direct correspondence between the code and
quadrants/depth in quadtrees but I'm not swift enough with ASCII graphics
to draw it here. I can do a picture and send it via MIME if ya want. Also
as mentioned, you can do algebra on them. Need to offset the coordinates
by an X,Y? make a code for the offset and add/subtract it in.
You can also do range searching by masking off low-order bits. Finally,
this is why using B-Tree type stuff works.. the keys in the tree are just
the interleaved codes. It's one of those things that once discovered you
bonk yourself on the head and say "why didn't I think of that?"
-Todd
--<cut>--
--
J C Lawrence Internet: claw#null,net
----------(*) Internet: coder#ibm,net
...Honourary Member of Clan McFud -- Teamer's Avenging Monolith...
</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="00553" HREF="msg00553.html">Position sorting</A></STRONG>
<UL><LI><EM>From:</EM> Adam Wiggins <nightfall#user1,inficad.com></LI></UL></LI>
</UL></LI></UL>
<!--X-References-End-->
<!--X-BotPNI-->
<UL>
<LI>Prev by Date:
<STRONG><A HREF="msg00642.html">Re: [MUD-Dev] Version Control (was: DBs and Events)</A></STRONG>
</LI>
<LI>Next by Date:
<STRONG><A HREF="msg00644.html">Re: [MUD-Dev] Re: MUD Development Digest</A></STRONG>
</LI>
<LI>Prev by thread:
<STRONG><A HREF="msg00553.html">Position sorting</A></STRONG>
</LI>
<LI>Next by thread:
<STRONG><A HREF="msg00548.html">Re: [MUD-Dev] byte-code anyone?</A></STRONG>
</LI>
<LI>Index(es):
<UL>
<LI><A HREF="index.html#00643"><STRONG>Date</STRONG></A></LI>
<LI><A HREF="thread.html#00643"><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] 3D engines for MUDs (was: The MLI Project)</STRONG>, <EM>(continued)</EM>
<ul compact>
<ul compact>
<ul compact>
<ul compact>
<ul compact>
<ul compact>
<LI><strong><A NAME="00788" HREF="msg00788.html">Re: [MUD-Dev] 3D engines for MUDs (was: The MLI Project)</A></strong>,
Michael Hohensee <a href="mailto:michael#mainstream,net">michael#mainstream,net</a>, Fri 20 Mar 1998, 13:26 GMT
</LI>
<LI><strong><A NAME="00796" HREF="msg00796.html">Re: [MUD-Dev] 3D engines for MUDs (was: The MLI Project)</A></strong>,
Michael Hohensee <a href="mailto:michael#mainstream,net">michael#mainstream,net</a>, Fri 20 Mar 1998, 21:15 GMT
</LI>
<LI><strong><A NAME="00798" HREF="msg00798.html">Re: [MUD-Dev] 3D engines for MUDs (was: The MLI Project)</A></strong>,
Michael Hohensee <a href="mailto:michael#sparta,mainstream.net">michael#sparta,mainstream.net</a>, Fri 20 Mar 1998, 21:47 GMT
</LI>
</ul>
</ul>
</ul>
</ul>
</ul>
</ul>
</LI>
<LI><strong><A NAME="00553" HREF="msg00553.html">Position sorting</A></strong>,
Adam Wiggins <a href="mailto:nightfall#user1,inficad.com">nightfall#user1,inficad.com</a>, Sun 22 Feb 1998, 13:17 GMT
<UL>
<LI><strong><A NAME="00643" HREF="msg00643.html">Re: [MUD-Dev] Position sorting</A></strong>,
coder <a href="mailto:coder#ibm,net">coder#ibm,net</a>, Sat 28 Feb 1998, 05:04 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="00548" HREF="msg00548.html">Re: [MUD-Dev] byte-code anyone?</A></strong>,
Chris Gray <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Sat 21 Feb 1998, 07:01 GMT
<LI><strong><A NAME="00540" HREF="msg00540.html">Re: [MUD-Dev] Back on the list</A></strong>,
Chris Gray <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Fri 20 Feb 1998, 16:16 GMT
<LI><strong><A NAME="00533" HREF="msg00533.html">Back on the list</A></strong>,
Niklas Elmqvist <a href="mailto:d97elm#dtek,chalmers.se">d97elm#dtek,chalmers.se</a>, Fri 20 Feb 1998, 08:38 GMT
<UL>
<LI><strong><A NAME="00564" HREF="msg00564.html">Re: [MUD-Dev] Back on the list</A></strong>,
coder <a href="mailto:coder#ibm,net">coder#ibm,net</a>, Mon 23 Feb 1998, 19:13 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>
