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

[clawrenc at cup.hp.com]

In <33E7345C.3C59ECBA at sparta.mainstream.net>, on 08/05/97 
   at 08:20 AM, Michael Hohensee <michael at sparta.mainstream.net> said:

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

No, it wouldn't be viable as soon as the number of objects got large.

You need to look into the various space representing data structures
such as R-Trees, R*-trees, V-Trees, H-Trees, quad/oct-trees, etc.  I'd
suggest getting various books on the area (no specific
recommendations) and thoroughly browsing the LEDA and Stony Brook
sites as well as digging thru the list of available C++ libraries as
posted to comp.lang.c++ (or was it comp.std.c++?).  There are a lot of
different possible structures to use, eah with its own benefits and
uses.

Note from my own such survey, still ongoing: A key consideration for
me is the ease and expense of generating a list of all objects within
a defined range of a coordinate, *and* the expense/difficulty of
generating a similar list of ranged objects which meet a standarised
criteria.

--
J C Lawrence                           Internet: claw at null.net
(Contractor)                           Internet: coder at ibm.net
---------------(*)               Internet: clawrenc at cup.hp.com
...Honorary Member Clan McFUD -- Teamer's Avenging Monolith...