[MUD-Dev] Spatial datastructures and their application (Was R e: Hilbert Curves)

[Lo]

> From: 	Christopher Allen
> Sent: 	05 November 1999 03:13
> 
> A faster alternative is to do a Hilbert search to find those objects that
> are within 100x100 points around the player. This delivers a list of
> potential visible objects in a rectangle around the player. This typically
> is a relatively small list, say of a dozen objects.

> You can then sort that list by actual linear distance, modified by height
> and possibly the intervening terrain. Then only tell the player about
those
> that might be visible. If you wanted to add some more complication, you
> could even have slightly different descriptions depending on the
visibility
> and distance. These functions do not take that much time.

> The result: "You see a house not too far to the north, an unusual rock
> outcropping far to the west, and the top of tower beyond the horizon to
the
> southeast."

That still sounds like a lot of computations for each and every look.

Here's another half-baked idea from Ling's Fantastic Brain (tm).  (Don't
argue with that description)

Assuming a sexy description generator is available, describe the world with
primitives, such as oblongs, spheres and cylinders.  Builders arrange these
primitives and give them attributes then bind a bunch together in a
rectangle (as in r-tree rectangle).  The builder then marks some attributes
on the rectangle (eg: building, mountain, tree, or whatever) and attaches
this to a bigger rectangle which describes the terrain the children
rectangles are in (eg: park).  This proceeds up the tree with each parent
holding attributes that encompasses the children (eg: town, borough, county,
country, continent, planet, etc).  Rectangles are allowed to grossly
overlap, don't see why not.  The description generator works top-down by one
step, that is, descriptions are composed from the immediate kids of this
rectangle, no further.

Prominent features are propagated up the tree with attenuation, so a
particularly bright beacon on the rooftop of a skyscraper will affect the
description of the rooftop which in turn affects the skyscraper's
description which in turn affects the city's description.  This should be
done in a semi-lazy manner.  For each new effect that can propagate in any
medium, the affected parent rectangles should be marked as requiring a
description update.

Observers should grab descriptions depending upon their relative location.
The immediate parent rectangle should give a clue as to where the character
is (eg: in a park, city, room, under a desk).  Next, adjacent rectangles at
the same level are grabbed (room next door), followed by rectangles from
higher up the tree further out (church opposite, Rockies in the background).

Admittedly, the r-tree is not really an r-tree since it breaks the rules for
number of branches per node.

My reasons for this odd arrangement include: distant landmarks might have a
chance of appearing in the description, eg: distant cities will appear
exactly as so, not a sporadic spam of buildings; it seems sensible; and I
have no idea what I'm doing.

Disadvantage of this system is obvious, I've assumed the descriptions will
be the same for each and every character.  This can be adjusted by
propagating attributes instead of completed descriptions, observers can then
generate their own descriptions.  In fact, this would probably be workable
if attributes were sent to the client which then generate the description.

Another disadvantage is that this is theoretical and I have not and will not
implement it.

Ling



_______________________________________________
MUD-Dev maillist  -  MUD-Dev at kanga.nu
http://www.kanga.nu/lists/listinfo/mud-dev