From: bobp@hal.com (Bob Pendelton)
Newsgroups: sci.virtual-worlds
Subject: SCI: The joys of hashing
Date: 12 Aug 92 20:26:02 GMT
Article-I.D.: u.1992Aug14.095754.14440
Organization: HaL Computer Systems, Inc.
Originator: hlab@milton.u.washington.edu



One of the best ways to reduce n*n*n... type problems to tractable
forms is to keep around information that lets you make reasonable
decisions.

A useful thing for an object to keep around is a list of all the other
objects near it. Such a list could be used for many things.

Assuming such a list exists and it includes in it's entries the visual
description of an object then you can use the list to render what
you're currently looking at. And, you could use it to detect which
objects you are likely to hit while moving. 

But searching such a list is an O(n) operation by itself. So, we need
to represent the list in a form that can be searched faster.

One thing we could do is use the x, y, and z of an object coordinates
as subscripts into a 3 dimensional array and store a list of all the
things that reside at a given location at the corresponding location in
the array. Of course the array gets a bit large if you do that...

Ok, before you use the coordinates shift them right N bits. This has
the effect of mapping many coordinates to one entry in the array. Shift
them right 1 bit and you're mapping each location in the array to a
2x2x2 volume. Shift them right 2 bits and you're mapping each entry in
the array to a 4x4x4 volume of space. You get the idea.

Shifting is just a fast way to divide by a power of two. If you want
your entries to map to a volume that isn't a power of 2 on each side
then you have to use a divide instead of a shift. That's ok if you have
a fast divider. It's been my experience that shifting is usually faster
than dividing so I habitually use shifts. A matter of taste and style,
not really important to the ideas in this posting.

Ok, so mapping many locations to one entry in the array reduces the
size of the array. But, if you're using, say 32 bit integers as
coordinates you still can wind up with a pretty big array unless each
entry maps to a very large volume.

Your average object doesn't need to keep track of every other object in
the universe. So, it can restrict the size of the array it needs by not
keeping track of objects that are too far away. But, computing
distances can be very expensive. In 3 space distance is sqrt((x1 -
x2)^2 + (y1 - y2)^2 + (z1 - z2)^2). Square roots are expensive.
Multiplies can also be expensive. You can get rid of the square root by
doing a range test based on distance^2. But you still have to do the
multiplies and adds.

An alternative is something like:

mask & ((x1 - x2 + offsetX) | (y1 - y2 + offsetY) | (z1 - z2 + offsetZ))

Where the mask is something like 0xffff0000 so that you're picking out
high order bits. If the result is 0 the coordinate is in range and if
it's non-zero the coordinate is out of range. The more 1s in the mask
the shorter the range you're looking at. This is likely to be faster
than a test that involves multiplies and is definitely faster than one
that involves square roots.

The following code illustrates how this works:

long x1, y1, z1;
long x2, y2, z2;

unsigned long mask;
unsigned long test;

unsigned long range = 64;
unsigned long offset = 32;

main()
{
    int i;
    
    x1 = 20;
    y1 = 20;
    z1 = 20;

    x2 = -100;
    y2 = -100;
    z2 = -100;

    mask = ~(range - 1);
    printf("mask = %lX\n", mask);
    
    for (i=1; i < 200; i++)
    {
        test = mask & ((x2 - x1 + offset) |
                       (y2 - y1 + offset) |
                       (z2 - z1 + offset));
        printf("x = %li y = %li z = %li test = %lX\n", x2, y2, z2, test);
        x2 += 1;
        y2 += 1;
        z2 += 1;
    }
}

Even with a range restriction it's pretty obvious that most of the
space in my cubicle, or even the game room of my house (where I'm
writing this) is mostly empty space with a lots of objects clustered in
small areas.

But we know how to deal with sparse arrays. We use hash tables.

The right shift operation used for mapping volumes to table entries
throws away low order bits of the coordinates. The range test described
above makes sure there are no high order bits to worry about. The
result is a (hopefully) small set of bits out of the middle of each
coordinate. Concatenating these bits together gives a pretty good start
for a hash index. The concatenated value modulo the table size is a
good hash index.

The following code shows how this works:

long
hash(long x, long y, long z, int shift, int width, long mask)
{
    long bucket;

    bucket = mask & (x >> shift);
    bucket <<= width;
    bucket |= mask & (y >> shift);
    bucket <<= width;
    bucket |= mask & (z >> shift);
    
    return bucket;
}

main()
{
    long x1, y1, z1;
    unsigned long test;
    int i;

    x1 = 0;
    y1 = 0;
    z1 = 0;


    for (i=1; i < 200; i++)
    {
        test = hash(x1, y1, z1, 4, 4, 0xf);
        printf("x = %li y = %li z = %li test = %lX\n", x1, y1, z1, test);
        x1 += 1;
        y1 += 3;
        z1 += 5;
    }
}

With a table like this you can find out if there is anything in a given
volume by hashing the coordinates for the center the volume and
checking the corresponding hash bucket.

If an object wants to move, it can quickly find out what objects are
likely to be affected by it's motion.  When an object decides to try
to move instead of having to send messages to every object in the
universe, it only has to send messages to the objects that are
directly in it's path and close enough that they might be hit.

If you know that some objects in the local area are moving you can
generate predictive entries for those objects and keep them around
until they expire so you can predict possible collisions and be reday
to deal with them should they occur. Also you can spend more time
working on places where collisions are likely. This should give better
simulation of physical interactions.

The same thing happens with vision. The object that is "seeing" can
pick out all the objects in the general direction it is looking and
render only the objects it can see. No only that, but it can break them
up into groups that cannot interfere with each other and render them in
parallel (assuming more than one CPU is available) and use a painters
sort to merge them all together into a final image.

There are also interesting tricks you can do by hashing on polar
coordinates. By hashing just on the angles you can get a table indexed
by the direction of an object. By using the distance as well you can
get a table that can be indexed to give you direction and distance
directly.

I haven't thought about polar coordinate hashing as much as I've
thought about rectangular hashing. But, it looks like it could be very
useful.

3D hash tables also provide a basis for fast message routing. A message
router can keep around several hash tables that cover different ranges
at different granularities. 

Let's say someone is looking in my window. When I move a movement
message is passed to all the nearby objects that might be affected by
it. The message is also passed to the local router. The router checks
for things like windows and doors that want to get messages. Things
like windows and doors can register a desire to receive messages they
might not get otherwise.

The window can use a hash table to decide which objects outside the
window might be able to see inside the window and pass the message
along to them or the routers they deal with.

I can imagine each router containing several different hash tables. A
local table that keeps track, in fairly high detail, of all the objects
in the local area. Anther table that keeps track of the surrounding
area but at a much lower level of detail. (At the lower level of detail
you may really only need to know that something exists in a volume and
how many of them there are.) In fact, higher level routers may only
keep track of the "locations" of other routers. And so on, each table
covering a larger area at a lower level of detail.

-- 
Bob Pendleton             | As an engineer I hate to hear:
bobp@hal.com              |   1) You've earned an "I told you so."
Speaking only for myself. |   2) Our customers don't do that.
                   <<< Odin, after the well of Mimir. >>>