[MUD-Dev] Re: X, Y & Z.

[J C Lawrence]

Note: Please keep your postings word wrapped to less than 80 columns
as indicates in the list rules at
http://www.kanga.nu/~petidomo/lists/mud-dev/#rules.

On Fri, 11 Sep 1998 18:01:17 +0100 
Scott Cade<scade at 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 at null.net
(Contractor)                               Internet: coder at ibm.net
---------(*)                     Internet: claw at under.engr.sgi.com
...Honourary Member of Clan McFud -- Teamer's Avenging Monolith...