[MUD-Dev] Physical Space Representation

[coder at ibm.net]

On 07/06/97 at 07:27 PM, mathue at king.cts.com (Mathue Moyer) said:

>Unfortunately, in the context of internet game development I'm pretty
>much nobody when compared to others on the list, so I won't bother
>you with the details.  :)

/Most/ of the list members don't have any large public presence in the
field.

>On a slightly different note, I think it would be somewhat
>interesting to catalog (in a fairly cursory fashion) all of the PSR
>schemes people have come up with, heard of, etc...  Seeing one list
>of the whole lot (or at least a decently-sized subset) could help
>generate new ideas.  Here's my first stab at categorizing PSR
>attributes (off the top of my head, I confess)... I hope the
>whimsical acronyms aren't too hard to follow.  ;)

>Object Interaction Granularity:
...
>Frame Of Reference Structure:
...

The one you miss, were I to give it a name, is, "Dynamic Reference
Frame Creation".  This is what I'm examining.  Essentially it means
that I determine the PoV's coordinates as a point, and then derive
from there the frame of reference to group only those objects "in
range".  

As I use an R*-Tree for for the basic data storage, this means
ascending the tree until a 3D rectangle is found which entirely
contains the requested frame, iterating across all contained
rectangles to select only those that intersect or are contained by the
requested frame, and then iterating across their contents
(sub-rectangles and individual object lists) to finally create a new
rectangle which contains only the desired objects.

This new rectangle is then time stamped.  Each new access to the
rectangle updates the time stamp (only if the rectangle is "matched"). 
Should the rectangle time stamp get too old, the rectangle is deleted. 


The next spiffy aspect is defining rectangle translations.  At a crude
level this means defining a logical rectangle containing the new
volume to be included, and a logical rectangle containing the volume
to be abandoned.  Everything in the first is then added, and in the
second removed from the original rectangle, and its coordinates
updated to follow a motion.

Thus a player walking across the land is actually represented
internally by a rectangle mapping his frame of reference, with said
rectangle wandering about the land, sucking in objects on the forward
side and abandoning them on the lee side.   As the character's range
increases (say sight, or magic sense), then so the rectangle grows, or
conversely shrinks when the character's abilities shrinks.  

The ugly bit is having one rectangle for each sense.  A lot of
rectangles.  My next stab is to define rectangles for a character in
groups, operating on the basis that processing a slightly excessive
number of objects in a rectangle is preferable to needlessly updating
a vast array of unaccessed rectangles.  As such the basic ranges for a
character are dynamically grouped into loose sets of semi-similar
sizes, and then associated rectangles of that set's max size is
created and tracked.

The last ugly bit is that rectangles are, well, square, and ranges,
are spherical.  This gets even uglier when you consider something like
the sight range of a character standing on an opaque endless plain. 
The actual shape is a half-sphere.  Put him against a wall ang it
becomes a quarter sphere etc.  My intention here it two fold:

  1) ignore the problem and di up-front simplistic spherical range
checking (integer math approximations) to exclude the majority of
inapplicable objects most quickly.

  2) Dream lazily about some sort of magical side effect which would
auto-magically recognise when a large set of objects in a rectagle
were not matched by any of that rectangle's component ranges (eg the
plain/wall situation) and to remove all those objects under the covers

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