Simulator Design

Design patterns for real-time interactive simulators. Most of this was learned while working on NetworkRTS.

Event Loop

Challenge:

Handle incoming events as soon as possible
Allow the program to go completely to sleep (so that the operating system might swap it completely out of RAM and possibly go to sleep itself) whille nothing is happening

Solution

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 nextAutoUpdateTime and the process repeats.

With no events occuring

             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

When an event occurs

             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.

Immutable datastructures

Using immutable datastructures has several benefits:

Simplifies concurrent processing.
- Updates may continue while visibility calculations or rendering are done.
- Updates to independent parts of the world can be parallelized.
Simplifies serialization and caching.
Forces state changes to be explicit.

But it also introduces some challenges:

Structures must be chosen such that small updates don't require large amounts of data to be copied.
- Replacing large arrays with trees mostly solves this, but leads to many small objects being continuously allocated and freed.
Updates to many objects must be done in such a way that trees don't need to be rewritten as each object is processed.

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.

Message-based solution to movement on a grid

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):

Have every moving object send a message to its destination cell. Nothing actually happens, so the tree is not rewritten.
Process the move messages. Destination cells that are suitable for objects to be moved into rewrite themselves to contain the moved objects, sending 'move success' messages back to the source cells, and 'move failure' messages back to those that failed to move. If all messages are processed in one batch, each node in the tree will be rewritten at most once.
The response messages are processed. Cells update themselves to remove old blocks or to pass along 'you failed to move there' messages to blocks that failed to move as intended. Those blocks may attempt another move (e.g. if you can't move northeast, try moving north or east). Again, if all messages are delivered in a single batch, this will cause at most one rewrite per node.
If step 3 enqueued new messages, repeat from step 2.

Continuous movement with [almost] immutable object trees

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.

To process collisions, togos.networkrts.experimental.gameengine1.demo.BouncyDemo 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).

BitAddresses

A technique for addressing objects with large integers, which are compared bitwise to ranges. See togos.networkrts.util.BitAddressUtil.

Other stuff

There are still other things that need thinking about.