Design patterns for real-time interactive simulators. Most of this was learned while working on NetworkRTS.
The main event loop knows when the simulation needs to be updated
due to internal processes (this is accomplished by having a tree of
objects with a
getNextAutoUpdateTime() method). It waits
until that time (or possibly just before, to take step processing time
into account) for an incoming message. If an incoming message
does arrive in that time, the simulation is updated to the
time at which the message came and the message is processed. The
simulation is again asked for its
the process repeats.
A B time →.................................................... ......| |.......| | Listen for \__ __/ | incoming messages | | | Finish processing previous Ask simulation to update update, bringing the simulation itself to time = B to time = A
A B time →.................................................... | |.......| |.......| | Listen for \__ __/ \__ __/ | incoming messages | | | | Auto-update to time = B Finish processing | processing update to time = A | message effects | Incoming message received; process immedately
The event could have caused a new auto-update time to come before B. I did not illustrate that scenario because the diagrams are already too cramped.
We could also say that the world will only be updated at a regular schedule (still leaving the possibility of skipping steps when nothing is happening). In this case we would not process an event immediately, but queue all events that are received to be processed at once at the next soonest tick.
A B time →.................................................... ......| | | |.......| | Listen for | | \__ __/ | incoming messages| | | | | | | Finish processing previous | | Ask simulation to update update, bringing the simulation| itself to time = B and process to time = A | | all events received | | | | Incoming events received
Note that in this case, time B must be the time of the next upcoming tick after the received events, which may be sooner than the next auto-update time calculated before the events were received.
Using immutable datastructures has several benefits:
But it also introduces some challenges:
Structures such as quad/octrees are great for storing static world data. For highly dynamic data (crowds of moving objects, or even just a few) they make the traditional 'update each object in sequence' approach rather clunky.
I've found that physics calculations for simulations where moving objects are constrained to a grid, while rather simple to implement using a single thread with mutable data, are surprisingly hard to adapt to immutable data structures. Traditionally, if two characters try to enter a cell simultaneously, the first one wins and the second cannot enter (or pushes on the first), but that implies that movements must be processed in order and their results saved for the next object's movement to be based on, which would require lots of tree traversals and re-writing.
If we are to stick with grid-based movement, one solution might be to do movement in multiple whole-world passes (as opposed to one pass per object):
If we are not sticking with grid-based movement, we might
give dynamic objects their own tree which is optimized for being rewritten every tick.
togos.networkrts.experimental.gameengine1 demonstrates this approach.
gameengine1 also optimizes building of the new tree by allowing
mutation of new tree nodes. Only after the entire tree is written
is it 'frozen', becoming effectively immutable.
updates all entities at once, writing a new tree with the results.
Each entity is only updated once, but may take into account multiple
collisions. Collision results are calculated deterministically, so
each entity only needs to update its own velocity, trusting that the
other will also detect the collision and update its velocity.
When movement is continuous, we can allow collisions between entities to happen, and then detect and correct them on next update. It would be possible for entity updates to immediately detect collision with a static background so that no overlap ever happens. Fast-moving entities may do collision checks all along their route, but if they pass all the way through, some other way of communicating the collision to collided-with entities would be required. Possibly leaving some type of collision indicator objects behind, though if the collided-with entity is also moving quickly, those would not be guaranteed to be detected. True message-passing to the object would require it to have an ID, which I find slightly annoying to have to give to every object that might possibly move (non moving objects can be addressed using their position, and objects whose state never changes may be addressed by their state (though the only point of addressing such an object would be to delete it). Giving IDs to all objects whose position and/or internal state change over time may be something I need to just get over).
A technique for addressing objects with large integers, which are
compared bitwise to ranges.
There are still other things that need thinking about.