[MUD-Dev] Position sorting

[coder at ibm.net]

On 22/02/98 at 10:07 AM, Adam Wiggins <nightfall at 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 at null.net
From:  "Carter T Shock" <ctso at umiacs.umd.edu>
To:  <mud-dev at 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 at null.net
----------(*)                              Internet: coder at ibm.net
...Honourary Member of Clan McFud -- Teamer's Avenging Monolith...