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

[Michael Hohensee]

Cynbe ru Taren wrote:
> 
> | 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.

Hmm.  Good idea.  I was kinda turning green whilst trying to code my
hashtable to insert rooms into the right spot..

One problem..  How do you deal with "filler" entries?  In a spatial
oriented hashtable, one would just toss one entry which tells the
program that the locations ahead of it are of type X and go on for
length Y.  While objects are real easy to find in the system you
propose, it seems unclear as to where to place the filler entries. (we
can't place them individually in each "empty" area, or else we might as
well have a matrix)



> 
> | 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

The system as it stands is as follows (in C++)

World is represented on a hashtable of Wld_Entry classes (structs, to
the C++ impared)

class Wld_Entry {
int terrain;
Base_Obj *room;
int how_far;
Wld_Entry *Xnext;
Wld_Entry *Xprev;
Wld_Entry *Ynext;
Wld_Entry *Yprev;
Wld_Entry *Znext;
Wld_Entry *Zprev;
int X;
int Y;
int Z;
};

Each Wld_Entry can either represent an "empty" zone, (ie tell the
program that there are no specific rooms created for "how_far" units in
the +X direction, and that they all have terrain type "terrain"), or it
can contain a room.  (The room, of course, can be any other sort of
object as well.)

When we need to insert a room into the hashtable (when a player or other
object wanders into an "empty" zone, or during boot-up) we call the
function: insert_at_location(Wld_Entry *obj, int x, int y, int z);
This function hashes each co-ordinate value, and travels down the table
till it gets to the correct spot.  It also checks to see if any filler
statements are going have to be modified to keep up with this new
arrangement.  We remove objects from their locations with
remove_from_location(......);

The problem is (and it hasn't been coded yet) that it is very ugly to
code, from what little I've started.


--
Michael Hohensee       michael at sparta.mainstream.net
http://www.geocities.com/SiliconValley/Heights/9025/
      Finger me for my PGP Public Key, or use: 
http://sparta.mainstream.net/michael/pgpkey.txt