|
Posted by Brian Lindahl on August 17, 2004, 3:12 pm
Please log in for more thread options
While this problem space is somewhat specific to game programming,
I've posted it to other groups because the problem space can be
abstractly applied to concepts in these groups (simulating
worlds/systems, spatial indexing techniques, non-locking
synchronization etc.). Sorry if you feel offended by my intrusion (I
won't respond to flames).
First, 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
|
|
Posted by WTH on August 18, 2004, 11:46 am
Please log in for more thread options
> regions (since they can only cross one region border at a time) and
Your regions are 2 dimensional?
WTH
|
|
Posted by Brian Lindahl on August 18, 2004, 3:47 pm
Please log in for more thread options > > regions (since they can only cross one region border at a time) and
>
> Your regions are 2 dimensional?
>
> WTH
Yes, we're dealing with only 2 dimensional regions here.
|
| Similar Threads | Posted | | spatial indexing | April 25, 2005, 12:14 am |
| Non-Overlapping Spatial Indexing | August 23, 2004, 11:09 am |
| implementing Spatial Indexing in VB | April 25, 2005, 2:11 am |
| Quadtree spatial indexing Algorithm | October 18, 2005, 6:32 am |
| MapBasic mouse event handlers | December 29, 2005, 1:57 am |
| Oracle Spatial (9i or 10g) vs Informix Spatial Datablade ? | June 13, 2006, 7:52 am |
| Spatial Conflation techniques | May 25, 2005, 2:48 pm |
| Oracle versions & Spatial | August 12, 2005, 12:53 am |
| mapserver and spatial operations | February 14, 2006, 5:00 am |
| Spatial data migration | October 9, 2007, 2:49 am |
|
XML Sitemap