Sparse Arrays and co-ordinate based worlds

[Michael Hohensee]

This topic was discussed earlier, but I missed the beginning of it, and
so was lost trying to read the end.  I also suppose that the other
people who popped in recently miught have something to say in the
matter, or at least find it interesting...

I've been sitting around for a while, thinking about how nice it would
be to have rooms arranged as if they were each entries in a vast matrix.
That is, the Throne Room of Castle Aghhh is at *world[104][42][2], etc.
This means that I can take any path I choose to the Throne Room, as long
as there aren't any walls in the way.  Further, I don't have to worry
about wandering to places that don't currently exist as "written" rooms,
since I will get some generated description based upon the type of room
I enter.  (time to wipe the drool off our chins).

Unfortunately, this kind of array is very large and memory consuming. 
So memory consuming that my compiler chokes on any program with an array
of dimensions, say: [1000][1000][100].  Now we all know that it is very
unlikely that we would ever get 100000000 objects of any sort in play at
once, but we could imagine (stretching a little) a builder lining 1000
rooms in a row.  Such a builder should of course be shot on sight.  But
it'd be nice to be *able* to do it, should the need arise...

Ok, we can't use arrays outright, because they waste memory.  (I
haven't, as the subject of the message suggests, read anything about
"sparse arrays", so bear with me)  I figured that instead, each object
could contain its own co-ordinates, and be placed, in order, upon a
linked list with every other object in the world.  In the gaps in
between objects (ie: The big rock is 5 rooms/units away from Castle
Aghh), a filler link would be located, which says that the 5 rooms in
between it and the next object are grassland.

The only downside to this is that it is time-intensive to use the system
as an array.  Since you get the contents of a room by going down the
list until you hit the proper co-ordinates.  This, I suppose, is the old
trade of memory for performance and vice versa scenerio.

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
a room at [100][23][5], you only look in the list which contains objects
from [100][20][0] to [110][30][10], avoiding going over the room at
[90][23][5] and its friends.

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

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