Re: [MUD-Dev] Sparse Arrays and co-ordinate based worlds

[Cynbe ru Taren <cynbe#laurel,actlab.utexas.edu>]

| Ok, next improvement.  Instead of having one linked list, break it up
| into a few hundred lists with a hashtable.  That way, when you look for
| from [100][20][0] to [110][30][10], avoiding going over the room at
|[90][23][5] and its friends.

Bingo, except there's no reason to use spatial clustering like
that for your hash function:  Won't help you and is quite likely
to hurt you.  Just mangle key (three integers, in this case) into
a pretty arbitrary hashcode to scatter your entries over the table.
Adding them is a quick hack, using something like MD5 will give
you a betterhash which may or may not be worth the coding and run
time.  Keep the table empty enough that most of your lists are
one long or empty.

| Would such a system be viable?  Could any improvements be made to it?

Well, you're effectively basing your system on a coarse integer
coordinate system.  If the idea works at all, I'd predict on past
experience that you'll wind up cursing them eventually and recoding
to use float coordinates.  If you wind up doing anything involving
needing to know object orientation, you will then eventually wind
up cursing -that- and representing object coordinate info using
4x4 homogeneous transform matrices... or wishing you could but being
unable to because of installed codebase (e.g., the NASA Panel library
wound up that way).  There's still no particular problem hashing
three or sixteen floats into a hashcode and looking them up, if you're
just needing exact matches.  (Need to watch precision problems a
bit, depending on what your're doing.)  If you can't settle for
exact matches, then you're back to R-trees, which have already
been covered here. :0