[MUD-Dev] Re: Nested Coordinate spaces.

[J C Lawrence]

On Tue, 23 Jun 1998 11:14:30 -0400 
Elis Pomales<pomales at caip.rutgers.edu> wrote:

> I've been thinking of using a b-trees with morton coded keys for my
> objects (one tree per "area") and a quad tree (or several) for area
> information (again per "area"). Though the biggest problem I
> currently see, for this and for the R*-Tree is in how you store the
> actual players? I mean players move around, thus requiring a delete
> and an insert... Sooo is this ideal? Am I thinking along the wrong
> track? I like R*Trees but have yet to find enough info on em (am
> trying to get a good book and spatial representations.)

I don't have time to check right now, but IIRC the Stony Brook
Algorithms site covered the area fairly well.

I really like the neighborhood concept, and have been thinking
seriously about looking at it again in my Linux port.  The fact that
neighborhoods integrate so well (sorta) with R*-Tree helps (think of
them as rectangles generated from the bottom up as versus top-down).  

Currently I take a very expensive approach for the context for mobile
objects: I create a semi-private not-really-a-rectangle for them and
remove objects when I notice that they are out of range (ie I don't go 
looking, reactive rather than proactive).  

Its not really a rectangle in that I'm very unaggressive about
removing objects from the rectangle which are out of range -- instead
I remove them when and if I notice them being out of range.  Similarly
its semi-private in that sloppy rectangles are sticky and will attempt
to share themselves (ie a small crowd of players maintains only one
sloppy rectangle which is shared across all characters, rather than
one rectangle per player).

This of course creates two types of rectangles: those that are
accurate, and those that we hope are accurate.  Only (potentially)
rapidly moving objects maintain hopeful rectangles (actually they are
created upon rapid movement and then are eventually torn down upon too
little movement (slow enough movement and full query/rectangle
generation is cheaper)).

Rectangles are built based on queries.  An incoming query first looks
for a rectangle which fits the query within fairly sloppy tolerances
(ie a larger enclosing rectangle that isn't too much larger).  If it
find one, then it uses that rectangle as its reply -- after all the
processing code has to qualify objects anyway, and so can handle the
(hopefully slight) extra load of the objects enclosed by the space
between the borders of the wished-for rectangle and the returned
rectangle.

  +-----------------------+
  |\                      |
  | Returned rectangle    |
  |                       |
  | +----------------+    |
  | |\               |    |
  | | Queried        |    |
  | |  rectangle     |    |
  | |                |    |
  | |                |    |
  | |                |    |
  | +----------------+    |
  |                       |
  +-----------------------+

The pessimal case of course is:

  +-----------------------+
  |\                      |
  | Returned rectangle    |
  |                       |
  | +----------------+##  |
  | |\               |##  |
  | | Queried        |##  |
  | |  rectangle     |##  |
  | |                |##  |
  | |                |##  |
  | |                |##  |
  | +----------------+##  |
  | ####################  |
  | ####################  |
  +-----------------------+

Where the #'s represent very high object concentrations *just* outside 
the desired rectangle's borders.  While I don't attempt to handle this 
currently (I was hoping to think of a decent detection algorithm for
this case so that I could then kick in other more expensive
intelligence only when needed -- I just haven't thought of a decent
detection method yet).

If a decent matching rectangle for the query can't be found, then I
generate a new rectangle.

Theoretically rectangles are maintained on a sort of LRU cache basis.
This means that each rectangle retains two stats: a last accessed
value (ie this rectangle was the answer to a query), and a last
referenced value (ie this rectangle was used as a resource to answer a
query (eg as an enclosing or component rectangle in generating a new
rectangle)), and I then tear down rectangles as they fall out of use.
Note that I don't go looking for stale rectangles however.  I merely
note them in other more typical processing, and throw them onto a
queue for a background thread to tear down at low priority.

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