August 2004
- What is an MMOG? ceo
- MEDIA: .hack//SIGN Japanise animated series Mike Rozak
- MEDIA: .hack//SIGN Japanise animated series
- MEDIA: .hack//SIGN Japanise animated series Otis Viles
- MEDIA: .hack//SIGN Japanise animated series Richard A. Bartle
- MEDIA: .hack//SIGN Japanise animated series Scott Tengelin
- MEDIA: .hack//SIGN Japanise animated series Dana V. Baldwin
- MEDIA: .hack//SIGN Japanise animated series David Kennerly
- MEDIA: .hack//SIGN Japanise animated series Ghilardi Filippo
- MEDIA: .hack//SIGN Japanise animated series Ola Fosheim Grøstad
- MEDIA: .hack//SIGN Japanise animated series zgj22@drexel.edu
- Books on Virtual Worlds Matt Cruikshank
- DGN: Requesting feedback on a "concept document" (somewhat related to Better Combat) Craig Huber
- The Casual-Player Killer: Time? (was MMO Communities) Will Jennings
- The Casual-Player Killer: Time? (was MMO Communities) Amanda Walker
- The Casual-Player Killer: Time? (was MMO Communities) Michael Sellers
- [BIZ] CoH subscribers numbers Ghilardi Filippo
- [DGN] Socialization against the fun [was: MMO Communities] HRose
- Cognitively Interesting Combat (was Better Combat) Paolo Piselli
- Fwd: Cognitively Interesting Combat (was Better Combat) kennerly@finegamedesign.com
- Time debt Stephen McDonald
- Fwd: Cognitively Interesting Combat (was Better Combat) kennerly@finegamedesign.com
- Cognitively Interesting Combat (was Better Combat) Paolo Piselli
- Cognitively Interesting Combat (was Better Combat) David Kennerly
- Cognitively Interesting Combat (was Better Combat) Paolo Piselli
- Cognitively Interesting Combat (was Better Combat) Paolo Piselli
- Cognitively Interesting Combat (was Better Combat) David Kennerly
- Cognitively Interesting Combat (was Better Combat) Paolo Piselli
- Cognitively Interesting Combat (was Better Combat) David Kennerly
- Cognitively Interesting Combat (was Better Combat) Paolo Piselli
- Cognitively Interesting Combat (was Better Combat) Paul Schwanz
- Cognitively Interesting Combat (was Better Combat) Paolo Piselli
- Cognitively Interesting Combat (was Better Combat) Paolo Piselli
- Cognitively Interesting Combat (was Better Combat) Paolo Piselli
- Cognitively Interesting Combat (was Better Combat) cruise
- Cognitively Interesting Combat (was Better Combat) ceo
- Cognitively Interesting Combat (was Better Combat) ceo
- Cognitively Interesting Combat (was Better Combat) cruise
- Cognitively Interesting Combat (was Better Combat) ceo
- Cognitively Interesting Combat (was Better Combat) cruise
- Cognitively Interesting Combat (was Better Combat) Paul Schwanz
- Cognitively Interesting Combat (was Better Combat) KaVir@t-online.de (Richard Woolcock)
- Cognitively Interesting Combat Derek Larson
- Cognitively Interesting Combat (keyword: archetypes) Eric Random
- Cognitively Interesting Combat (keyword: archetypes) Paolo Piselli
- ADMIN: Effective progress methods for MUD-Dev (was Better Combat (long)) J C Lawrence
- FW: Deriving Self Esteem from one's MMORPGavatar[was:Long-Term Rewards] vladimir cole
- 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 - database design Lazarus
- database design Hans-Henrik Staerfeldt
- database design Lazarus
- database design
- [DGN] database design Steven King
- database design Erik Bethke
- database design Sean Kelly
- database design Hans-Henrik Staerfeldt
- PVP and perma-death Ola Fosheim Grøstad
- PVP and perma-death Artur Biesiadowski
- PVP and perma-death Ola Fosheim Grøstad
- PVP and perma-death Vladimir Cole
- PVP and perma-death Vladimir Cole
- PVP and perma-death Artur Biesiadowski
- PVP and perma-death Steven King
- PVP and perma-death Ola Fosheim Grøstad
- PVP and perma-death Steven King
- PVP and perma-death Ola Fosheim Grøstad
- PVP and perma-death Douglas Goodall
- PVP and perma-death HRose
- PVP and perma-death [NEW THEME] After Deployment Tiago Carita
- PVP and perma-death Paul Schwanz
- PVP and perma-death J C Lawrence
- PVP and perma-death Ola Fosheim Grøstad
- PVP and perma-death HRose
- PVP and perma-death Ola Fosheim Grøstad
- PVP and perma-death HRose
- PVP and perma-death Ola Fosheim Grøstad
- PVP and perma-death HRose
- PVP and perma-death Ola Fosheim Grøstad
- PVP and perma-death HRose
- PVP and perma-death Ola Fosheim Grøstad
- PVP and perma-death Koster, Raph
- PVP and perma-death HRose
- PVP and perma-death ceo
- PVP and perma-death Michael Sellers
- PVP and perma-death Matt Mihaly
- PVP and perma-death Douglas Goodall
- PVP and perma-death HRose
- PVP and perma-death Derek Licciardi
- PVP and perma-death HRose
- PVP and perma-death Ola Fosheim Grøstad
- PVP and perma-death J C Lawrence
- PVP and perma-death Ola Fosheim Grøstad
- PVP and perma-death HRose
- PVP and perma-death Michael Sellers
- PVP and perma-death Byron Ellacott
- PVP and perma-death J C Lawrence
- PVP and perma-death Ola Fosheim Grøstad
- Casual Crowd vs.Time Rich Crowd [was: Time Debt] William Leader
- Casual Crowd vs.Time Rich Crowd [was: Time Debt] Stephen McDonald
- Casual Crowd vs.Time Rich Crowd [was: Time Debt] David Kennerly
- Casual Crowd vs.Time Rich Crowd [was: Time Debt] J C Lawrence
- Casual Crowd vs.Time Rich Crowd [was: Time Debt] David Kennerly
- Casual Crowd vs.Time Rich Crowd [was: Time Debt] Koster, Raph
- Casual Crowd vs.Time Rich Crowd [was: Time Debt] J C Lawrence
- ADMIN: Effective progress methods for MUD-Dev Jim Purbrick
- The Great Scam J C Lawrence
- [MEDIA] Finding an Interesting Middle Path in the RPG J C Lawrence
- [MEDIA] Finding an Interesting Middle Path in the RPG Koster, Raph
- [MEDIA] Finding an Interesting Middle Path in the RPG Douglas Goodall
- [MEDIA] Finding an Interesting Middle Path in the RPG J C Lawrence
- [MEDIA] Finding an Interesting Middle Path in the RPG David Kennerly
- [MEDIA] Finding an Interesting Middle Path in the RPG Megan Fox
- SOC DGN - Spawn locations Matthew Rick
- SOC DGN - Spawn locations Brian Hook
- SOC DGN - Spawn locations ceo
- SOC DGN - Spawn locations Sean Middleditch
- SOC DGN - Spawn locations Paul Schwanz
- SOC DGN - Spawn locations Jason Lai
- SOC DGN - Spawn locations J C Lawrence
- SOC DGN - Spawn locations HRose
- SOC DGN - Spawn locations J C Lawrence
- SOC DGN - Spawn locations Megan Fox
- SOC DGN - Spawn locations J C Lawrence
- SOC DGN - Spawn locations Ola Fosheim Grøstad
- SOC DGN - Spawn locations HRose
- SOC DGN - Spawn locations Brian Miller
- SOC DGN - Spawn locations Michael Sellers
- SOC DGN - Spawn locations Michael Hartman
- SOC DGN - Spawn locations Brian Miller
- SOC DGN - Spawn locations Chris Duesing
- SOC DGN - Spawn locations Douglas Goodall
- SOC DGN - Spawn locations J C Lawrence
- Casual Crowd vs.Time Rich Crowd [was: Time Debt] William Leader
- On balance and reality Ola Fosheim Grøstad
- On balance and reality William Leader
- On balance and reality Koster, Raph
- On balance and reality Ola Fosheim Grøstad
- On balance and reality HRose
- On balance and reality Ola Fosheim Grøstad
- On balance and reality Vladimir Cole
- On balance and reality William Leader
- On balance and reality William Leader
- Casual Crowd vs.Time Rich Crowd [was: Time Debt] Koster, Raph
- Casual Crowd vs.Time Rich Crowd [was: Time Debt] Gedanken
- Casual Crowd vs.Time Rich Crowd [was: Time Debt] Koster, Raph
- Casual Crowd vs.Time Rich Crowd [was: Time Debt] HRose
- Casual Crowd vs.Time Rich Crowd [was: Time Debt] Koster, Raph
- Casual Crowd vs.Time Rich Crowd [was: Time Debt] Matthew Dobervich
- Casual Crowd vs.Time Rich Crowd [was: Time Debt] Mike Rozak
- text based MUD Codebases, which one to pick? mirjam.eladhari@interactiveinstitute.se
- Casual Crowd vs.Time Rich Crowd [was: Time Debt] Douglas Goodall
- Casual Crowd vs.Time Rich Crowd [was: Time Debt] Steven King
- Casual Crowd vs.Time Rich Crowd [was: Time Debt] Michael Hartman
- Complexity and Accessibility (was: Better Combat (long)) Will Jennings
- SOC DGN: AC like alligiance system Matthew Rick
- SOC DGN: AC like alligiance system Hans-Henrik Staerfeldt
- SOC DGN: AC like alligiance system cruise
- SOC DGN: AC like alligiance system Artur Biesiadowski
- SOC DGN: AC like alligiance system HRose
- "a nicer species" (from today's Chronicle) (fwd) J C Lawrence
- Distributed State Systems Michael Tindal
- Distributed State Systems Davion Kalhen
- Distributed State Systems Michael Tindal
- Distributed State Systems Alex Arnon
- Distributed State Systems Davion Kalhen
- Distributed State Systems Michael Tindal
- Distributed State Systems Alex Arnon
- Distributed State Systems Alex Arnon
- Distributed State Systems Michael Tindal
- Distributed State Systems Bruce Mitchener
- Distributed State Systems Michael Hartman
- Distributed State Systems Michael Tindal
- Distributed State Systems Thomas Tomiczek
- Distributed State Systems Brian Lindahl
- Complexity and Accessibility Ola Fosheim Grøstad
- wherefor in-game artists? Paolo Piselli
- wherefor in-game artists? Richard A. Bartle
- wherefor in-game artists? Sean Howard
- wherefor in-game artists? David Kennerly
- wherefor in-game artists? ceo
- wherefor in-game artists? David Kennerly
- wherefor in-game artists? Richard A. Bartle
- wherefor in-game artists? Paolo Piselli
- wherefor in-game artists? Richard A. Bartle
- wherefor in-game artists? Ola Fosheim Grøstad
- wherefor in-game artists? Richard A. Bartle
- wherefor in-game artists? Ola Fosheim Grøstad
- wherefor in-game artists? Robert Zubek
- wherefor in-game artists? Matt Mihaly
- wherefor in-game artists? Christopher Allen
- wherefor in-game artists? Matt Mihaly
- wherefor in-game artists? Christopher Allen
- wherefor in-game artists? Ola Fosheim Grøstad
- wherefor in-game artists? Douglas Goodall
- wherefor in-game artists? Christopher Allen
- wherefor in-game artists? Ola Fosheim Grøstad
- wherefor in-game artists? Christopher Allen
- wherefor in-game artists? Ola Fosheim Grøstad
- wherefor in-game artists? Koster, Raph
- wherefor in-game artists? Ola Fosheim Grøstad
- wherefor in-game artists? Koster, Raph
- wherefor in-game artists? Douglas Goodall