[MUD-Dev] Asynchronous Event Execution & Localizing

[Brian Lindahl]

First of all, I've posted this exact same thread on several
google.groups for a broader reaching pool of talent. On
google.groups, the thread is titled: Spatial Indexing - Event
Localization - Non-locking synchronization. Groups posted to:
comp.games.development, programming.algorithms,
comp.infosystems.gis, comp.graphics.algorithms, comp.programming

Second, a few definitions for the problem space:

  Events are changes to the world that occur at a specific point in
  time, within a geographical coverage known as the event window.

  The world contains regions made up of polygons. They are generally
  in a heirarchal format with child regions being completely
  contained within a parent region and rarely overlap.

  Objects can move around way too often and there can be millions of
  them, therefore it is ineffecient to spatially index
  them. However, we CAN spatially index the regions, and simply move
  objects between regions (since they can only cross one region
  border at a time) and storing them in regions in arrays/linked
  lists.

  Objects are update their position lazily (only when crossing
  regions) and maintain a movement vector to minimize dirtying
  (database term).

Now onto the real problem. I'm trying to execute events as
asynchronously as possible, without a locking mechanism. Therefore,
events can be executed in a parent spatial index structure that
contains all possible children it will modify (the event window).

There are two spatial index structures I can choose for event
execution.

  1) Heirarchy of Regions (where regions contain other regions)

    advantages

      a) naturally defined, no space overhead
      b) world-design specific
      c) area-balanced

    disadvantages

      a) not load-balanced
      b) regions cannot overlap (though they rarely will anyway)

  2) An R-Tree or derivative (possibly Packed)

    advantages

      a) load-balanced
      b) can be preprocessed to optimize coverage and overlapping
      (known as packing)
      c) regions can overlap

    disadvantages

      a) extra space needed
      b) difficulty of embedding large regions
      c) not area-balanced

Note I consider R-Trees to be load balanced because typically busy
locations where lots of events are being scheduled are partitioned
into small regions and therefore will have finer grained nodes
(i.e. cities -> neighborhoods).

When an event is scheduled, we schedule it in the event queue of
smallest-sized spatial index node that fully contains the event
window.

For internal events, ones that originate inside a region, we trace
up the parent chain of spatial index nodes until we find a node
where only one of it's children overlap the event window, or the
node fully contains the event window. We then mark recursively mark
all the parent nodes as having an event (stopping when we find one
that is already marked).

So, for external events, we do a range search from the root until we
reach a node where more than one of it's children overlap the event
window, marking each node we traverse as having an event.

When we begin executing events, we tell the root spatial index node
to execute it's events, if it's been marked as having events. We
then recrusively define executing a node's event by executing events
in it's own event queue, and then asynchronously telling it's
children to execute their events. (Depth-first traversal/execution,
where events on the same level and lower can be executed
asynchronously).

Anyhow, I wanted to explain my implementation for synchronizing the
execution of events using localization instead of a locking
scheme. I also want to serve my implementation up for criticism -
constructive kind only please. I'd love to get some feedback on ways
to improve it. As well as other considerations I should make when
deciding between the R-Tree and Region Heirarchy
implementations. One thing I'd really like help on is how to go
about allowing larger regions to exist in the R-Tree non-leaf
nodes. I've also considered using linear quadtrees and having
regions being located in non-leaf quadtree node that corresponds to
the region's minimum bounding binary square - but I'm unaware of any
benefits this would have over the other possibilities - ideas here
would be great too.

-Brian Lindahl
_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev