<!-- MHonArc v2.4.4 -->
<!--X-Subject: [MUD-Dev] Re: X, Y & Z. -->
<!--X-From-R13: X Q Znjerapr <pynjNhaqre.rate.ftv.pbz> -->
<!--X-Date: Fri, 11 Sep 1998 10:42:01 -0700 -->
<!--X-Message-Id: 199809111741.KAA01108#under,engr.sgi.com -->
<!--X-Content-Type: text/plain -->
<!--X-Reference: E3E295CA3643D211B9890800097A1EAD1CC4@ARBORETUM1 -->
<!--X-Head-End-->
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html>
<head>
<title>MUD-Dev message, [MUD-Dev] Re: X, Y & Z.</title>
<!-- meta name="robots" content="noindex,nofollow" -->
<link rev="made" href="mailto:claw#under,engr.sgi.com">
</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="msg01015.html">Previous</a>
| <a href="msg01017.html">Next</a>
]
Thread:
[ <a href="msg01015.html">Previous</a>
| <a href="msg01020.html">Next</a>
]
Index:
[ <A HREF="author.html#01016">Author</A>
| <A HREF="#01016">Date</A>
| <A HREF="thread.html#01016">Thread</A>
]
<!--X-TopPNI-End-->
<!--X-MsgBody-->
<!--X-Subject-Header-Begin-->
<H1>[MUD-Dev] Re: X, Y & Z.</H1>
<HR>
<!--X-Subject-Header-End-->
<!--X-Head-of-Message-->
<UL>
<LI><em>To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI>
<LI><em>Subject</em>: [MUD-Dev] Re: X, Y & Z. </LI>
<LI><em>From</em>: J C Lawrence <<A HREF="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</A>></LI>
<LI><em>Date</em>: Fri, 11 Sep 1998 10:41:55 -0700</LI>
<LI><em>Reply-To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI>
</UL>
<!--X-Head-of-Message-End-->
<!--X-Head-Body-Sep-Begin-->
<HR>
<!--X-Head-Body-Sep-End-->
<!--X-Body-of-Message-->
<PRE>
Note: Please keep your postings word wrapped to less than 80 columns
as indicates in the list rules at
<A HREF="http://www.kanga.nu/~petidomo/lists/mud-dev/#rules">http://www.kanga.nu/~petidomo/lists/mud-dev/#rules</A>.
On Fri, 11 Sep 1998 18:01:17 +0100
Scott Cade<scade#protocol,co.uk> wrote:
> Coo... my first post after being a lurker here for quite a while :)
> I'm after a formula for producing a single unique number, given any
> combination of 3 large other numbers (all unsigned long integers) -
> those being X,Y & Z grid coordinates. I can do this easily using
> just X & Y, and given defined WORLD_WIDTH & WORLD_HEIGHT values, but
> the extra Z coordinate has got me stumped.
What you are looking for in essence are Morton codes. They have been
discussed a few times on the list previously (see the archives).
However you are also working off some flawed assumptions. You cannot
generate a 64 bit value (for instance) which is a guaranteed a unique
product of three 32 bit values (for instance). This is for the same
reason that repetitively compressing files does not endlessly decrease
their size, ultimately to one bit (or byte), or to look at very simply:
A 32 bit integer can (surprise!) have values in the range of 0 to
((2^32)-1).
Similarly a 64 bit integer can have values in the range of 0 to
((2^64)-1).
Three 32 bit values in concert can have (((2^32)-1)^3) unique
combinations of values (ie permutations).
Your problem is that (((2^32)-1)^3) is significantly larger than
((2^64)-1).
<<Or in the compression world (which is a good match as it too is
built on concepts of entropy), if you could compress all files down to
one byte, and one byte can store any value between 0 and 255
inclusive, that would mean that there are only 255 different possibly
files in the universe. (This is also why BTW compressing some files
results in their being larger than they were "uncompressed")>>
Morton codes address this general problem of coordinate reduction by
generating values which are proportional but not guaranteed unique.
Multiple coordinate sets can and will generate the same morton codes,
but simple hash bucket searching or similar globbing techniques from
there can find the correct item across the reduced working set. The
advantage of using morton codes in this manner is that they reduce the
set of possible matches quickly and cheaply, thus allowing only the
small set of matching morton value objects to be expensively matched
for exact coordinate equivalence.
--
J C Lawrence Internet: claw#null,net
(Contractor) Internet: coder#ibm,net
---------(*) Internet: claw#under,engr.sgi.com
...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="01015" HREF="msg01015.html">[MUD-Dev] X, Y & Z.</A></STRONG>
<UL><LI><EM>From:</EM> Scott Cade <scade#protocol,co.uk></LI></UL></LI>
</UL></LI></UL>
<!--X-References-End-->
<!--X-BotPNI-->
<UL>
<LI>Prev by Date:
<STRONG><A HREF="msg01015.html">[MUD-Dev] X, Y & Z.</A></STRONG>
</LI>
<LI>Next by Date:
<STRONG><A HREF="msg01017.html">[MUD-Dev] Re: Socket-Script: Socket-capabable script language and matching library</A></STRONG>
</LI>
<LI>Prev by thread:
<STRONG><A HREF="msg01015.html">[MUD-Dev] X, Y & Z.</A></STRONG>
</LI>
<LI>Next by thread:
<STRONG><A HREF="msg01020.html">[MUD-Dev] Re: X, Y & Z.</A></STRONG>
</LI>
<LI>Index(es):
<UL>
<LI><A HREF="index.html#01016"><STRONG>Date</STRONG></A></LI>
<LI><A HREF="thread.html#01016"><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="01029" HREF="msg01029.html">[MUD-Dev] Re: Off-topic! Re: Windows->Linux TCP/IP stack performance problems</A></strong>,
J C Lawrence <a href="mailto:claw#kanga,nu">claw#kanga,nu</a>, Sat 12 Sep 1998, 16:55 GMT
<LI><strong><A NAME="01023" HREF="msg01023.html">[MUD-Dev] An accidental experiment with language</A></strong>,
Damion Schubert <a href="mailto:zjiria#texas,net">zjiria#texas,net</a>, Sat 12 Sep 1998, 05:35 GMT
<LI><strong><A NAME="01021" HREF="msg01021.html">[MUD-Dev] Equipment fit revisited</A></strong>,
Andy Cink <a href="mailto:ranthor#earthlink,net">ranthor#earthlink,net</a>, Sat 12 Sep 1998, 00:00 GMT
<LI><strong><A NAME="01015" HREF="msg01015.html">[MUD-Dev] X, Y & Z.</A></strong>,
Scott Cade <a href="mailto:scade#protocol,co.uk">scade#protocol,co.uk</a>, Fri 11 Sep 1998, 17:22 GMT
<UL>
<LI><strong><A NAME="01016" HREF="msg01016.html">[MUD-Dev] Re: X, Y & Z.</A></strong>,
J C Lawrence <a href="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</a>, Fri 11 Sep 1998, 17:42 GMT
</LI>
<LI><strong><A NAME="01020" HREF="msg01020.html">[MUD-Dev] Re: X, Y & Z.</A></strong>,
Ben Greear <a href="mailto:greear#cyberhighway,net">greear#cyberhighway,net</a>, Fri 11 Sep 1998, 22:53 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="01012" HREF="msg01012.html">[MUD-Dev] Re: Windows->Linux TCP/IP stack performance problems</A></strong>,
Chris Gray <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Fri 11 Sep 1998, 02:42 GMT
<UL>
<li><Possible follow-up(s)><br>
<LI><strong><A NAME="01044" HREF="msg01044.html">[MUD-Dev] Re: Windows->Linux TCP/IP stack performance problems</A></strong>,
Alex Stewart <a href="mailto:riche#crl,com">riche#crl,com</a>, Mon 14 Sep 1998, 17:10 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="01009" HREF="msg01009.html">[MUD-Dev] Windows->Linux TCP/IP stack performance problems</A></strong>,
J C Lawrence <a href="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</a>, Thu 10 Sep 1998, 22:34 GMT
</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>