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

[Shawn Halpenny]

Michael Hohensee wrote:

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

What you need is a method of consistently generating what sits in between
the castle and the rock (the vagaries of my solution are below).

This sounds a bit like what I'm attempting.  Each MUD object (mob, player,
item, room) stores its own 3-space coordinates and in this there's a
certain, uhm, geometrical-flexibility.  From a previous post:

--cut--

I admit to copping out here, since I'm adopting a scheme where I have
a room-based system mapped onto a coordinate-based system.  This gives
me an obscene number of possible "rooms", though most of them will, of
course, be empty.  The remainder (those that make up the really
interesting parts of the world) are actually created by someone.  The
upshot is that a room exists at a single 3-space coordinate (there's
the cop out :-) ), which rather consistently violates a number of   
geometrical sensibilities.  However, it does obviate the implicit
requirement (a requirement in my mind, anyway) that I have to do what
would amount to elementary ray-tracing for simple things like showing
a character what's in the room she's standing in.  It's not as slick
as a completely coordinate-based approach, but it means less
headaches, particularly where object visibility is concerned.  It is
much easier to just let objects exist in a room and not worry about
precisely where they are.

--cut--

That said, things like true coordinate-based close (and ranged)
combat, precise object placement relative to other objects, and what
not are not viable with my system as it stands (not a complaint of
mine, since I'm not terribly interested in those to the degree that
would warrant a complete coordinate system--I'm waffling on that one
however.  I'm not entirely beyond the point of rethinking this and
using a completely coordinate-based system with much finer
granularity).  This is an issue of granularity.  Since each of my
rooms sits at a point in 3-space, there's no meaning to "step back
from Bubba as he swings his sword", since you technically haven't
changed your location.

I maintain a mapping of object locations to rooms (since each room
contains all other objects inside it) and any coordinates that are
not in that mapping supply a default, generic description based on
terrain type, etc.  The terrain types are yet another map (actually a
large set of bounding regions where the interiors of each describes a
uniform terrain), and locating any point within that set will return
a single terrain type that is used in the absence of a real room
object at that point.  Non-room objects can, of course, exist outside
of room objects, and they are handled in the same fashion.  The check
for real or virtual room is always done before any other
object-placement checking is performed.

These are the basics of my room model so far, anyway.  More details as the
thread warrants :)

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

If you're aiming for a very large world (including all the space in which
you don't have an actual room), arrays and linked lists in and of
themselves are pretty much out.

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

I've never really liked hashing, preferring some sort of tree for data
access if the potential for a _lot_ of sortable objects exists (certainly
the case for a large MUD database).

Lately, I've been looking at some of the LEDA data types, since there are
some that look very adaptable to what I'm doing above.

Pointers:

Collection of Spatial Data Structures
    http://www.cs.kuleuven.ac.be/~rudim/spatial/spatial.html

LEDA
    http://www.cs.sunysb.edu/~algorith/implement/LEDA/implement.shtml

Directory of Computational Geometry Software
    http://www.geom.umn.edu/software/cglist/

--
Shawn Halpenny

"Turn slowly for maximum vend."
                        - Me