Just a bit of musing

[coder at ibm.net]

On 27/02/97 at 08:17 AM, "Carter T Shock" <ctso at umiacs.umd.edu> said:
>I'll never understand why mud-folk have an overwhelming need to
>explicitly grid the world. That is, determine a minimum feature size (a
>room, a grid square, etc.) and then index one description for each cell
>in the grid.

Its simple and brain-cheap and thus attractive.  The problem I think is
not in "gridding the world", but in defining the world as a 2D/3D array,
as versus a sparse coordinate space.

>It seems to me that
>what you really have is a small-scale GIS, so why not use the techniques
>found in other GIS implementations?

For me, a major concern with literally taking a GIS approach (I used to
write 3rd party CAD applications for the MIcrostation market, so I have
some feel for the area) is that it enforces geometric consistancy. 
Realising I'm a rebel here, I think this is a Bad Thing.  I specifically
want to be able to easily represent mobius strips, Dr Who TARDIS'es
(bigger inside than out), and other such spatial violations.  To me they
make a bit part of the fun of designing/discovering the map of a world or
area.

What I've been playing with instead is a idea where there is a base
coodinate system, but where new (child/grandchild/etc) fully fledged
coodinate systems of equal or smaller resolution to the parent system can
be defined as occupying a given space withing its parent system.  

Transition from that point to a pure classic room based system shouldn't
be TOO hard.

>The digital nature of things means that there has to be at least an
>implicit gridding to the system. All that means is that there is some
>finite number of locations that any object may occupy. So we'll give
>everything a pair of coordinates. To keep it easy we'll go 2-D and use a
>pair of 16 bit values for about 4 billion distinct locations. Since we
>don't want to explicitly code descriptions for each of the 4 billion
>locations, we'll use some spatial data structure (point quadtrees come to
>mind) to index objects, critters, and players. It's small, relatively
>compact and let's you do neato things like determine the distance to
>another object, find the closest object etc.

I'd be much more tempted to use an R*-tree.  Most MUD calculations are
based on proximity, avilable reference, and similar.  Additionally noes
tend to very unevely distributed over the spatial matrix (busy city /empty
desert).  This makes a Quadtree comparitively expensive where large
sections would wastefully recurse down to define empty deserty, and others
would recurse very efficiently to define a highly detailed city.  At least
an R*-Tree allows a little more intelligent balancing.  

>Implement terrain features as thematic layers. Something simple like a
>region quadtree for each terrain type would do nicely. Again, they're
>small and efficient. ("one entry" in the region quadtree is the whole
>forest, rather than having to mark each individual location as
>forest/non-forest). No reason some terrain types can't overlap. Now when
>a person moves, you intersect their new location with the various themes.
>For each one that qualifies, you send a description. (i.e. if the
>player's location is coincident on a region in your forest theme, and the
>person is "outside", you add a line to any other descriptions sent that
>says "Yer in a forest". If they are "inside" skip the step.
>Interestingly, you can use this same kind of trick to let them look out a
>window)

Ignoring the logic problems of incompatable terrain types, apparently
inconsistant terrain (forests inside an aboreatum, lakes etc inside a
RAMA-style colony ship (or screw it, localised gravity distortions)) etc. 


>The idea extends to 3 dimensions as well, but computational overhead goes
>_way_ up. But, if you host your mud on a bruiser machine, no reason not
>to.

Yeah.  This is the one I want to minimise.

>Sorry for the long post,

Hehn.  Nahh, its great.  It helps keep the signal ration high.

--
J C Lawrence                               Internet: claw at null.net
----------(*)                              Internet: coder at ibm.net
...Honourary Member of Clan McFud -- Teamer's Avenging Monolith...