Thinking Your Way Out of Tick Order Hell

Anyone that has worked on an active simulation has probably spent a few days in tick order hell. This is the pernicious state where your result differs based on the order you construct your simulation frame, usually involving brain-bending circular dependency. For example you may find that your game camera is a frame behind the update of a monster it’s tracking because the monster is locked in a synced interaction with the player.

Player depends on monster for animation update, monster depends on player for positioning, camera depends on monster for tracking, camera depends on player for positioning, and programmer depends on Tequila for sustenance during this troubling time.

In a massive codebase the next step is an agonizing multi-day journey toward a fragile reshuffling of the systems, they themselves already delicately balanced against other dependencies.

 


Like this, but when the tower falls everyone gets fired

Most projects can cope with this torture. However, by starting at the top and working your way down you’ll find that you can avoid it altogether.

Prevent the Pain, Become a Game Designer:

The level of frustration you’re in for depends on the architectural approach to both the engine and your systems that use them. When designing a new system I’ve found that engineers tend to approach architectural problems myopically by focusing on a core technology feature first and foremost.

They may design for performance, for increasing safety for multithreading, or for any number of other engineering ideals. This isn’t necessarily bad (having a consistent core ideal gives your work focus) but I find that this process is oftentimes backwards in that it starts with the low level implementation goals which then dictate to the users of the system.

Game design rules that drive the code is a place that traditionally has a ton of interdependency. As a thought exercise for the overall problem it helps to start high-level by getting into the skin of a game designer.

 


Metaphorically of course

By troubleshooting the game rules for ambiguity, you’ll find that the tick order problem is already there in spades.

Break out the Dice and Card Games:

Designing a robust system of game rules is a much harder task than it sounds, and is something that videogame designers often don’t actually do. Their approach tends to be more or less analog with the actual interpretation and enforcement of rules left to programmers. The answer to discovered problems in game systems is usually to tell the implementing programmer “do whatever makes sense”. As to what that means, I leave that as an exercise for the reader.

 


I put the phrase in my translator and it exploded

Not to worry though, because modern board games, CCGs (collectible card games), and tabletop RPGs are all about being explicit. There’s no computer to act as judge and jury in the players’ petty disputes; it’s only the rules themselves that mark the difference between a night of delightful fantasy and a sweaty nerd fistfight.

Let’s look at an example of game design “bug fixing” at work. The following cards are from two different editions of the CCG “Magic the Gathering”:

 


What we have here is a tick order dependency stomped out at the source.

In the game of “Magic” game actions for each player’s turn take place on a fictional “stack”, with the stack resolved by popping each action off at end of a game “phase”. In this regard everything in Magic happens in an instant of game time, simulating a fast and frantic wizard’s duel.

The old text for the card implied that the Basilisk destroys the blocked target immediately, essentially putting a “the card is now dead” state into the game action stack. In Magic this is troubling since destroying a card and putting it in the graveyard may chain off a whole series of events.

 


Like your opponent throwing a hissy fit

The root of the problem is that the time when the card is actually destroyed changes the outcome of each interaction the Basilisk makes. This is beyond the spirit of the card and creates a potential feedback loop with the other game rules. The solution implemented here? Decouple the action from the result and make the time of its resolution explicit to the end of the game phase.

Make Your Frames Instantaneous

The preceding example teaches an important lesson: the order of execution in a moment of time should never circumvent the game state. Let’s apply this to our understanding of a frame of simulation.

Regardless of whether you have a single monolithic tick or independent systems that can update on their own interval (input system updates at 60 fps, gameplay at 30 fps, rendering as fast as the game will allow, etc), a frame represents the smallest interval of time your system can simulate. In that sense everything within a frame is taking place at once, and reordering the operations within that instant of time should never change your outcome.

 


Unlike reordering actions in the past.

Although this sounds simple enough at first blush, keep in mind that this must change every aspect of your highest level gameplay programming. So no more…

 

pPlayer->DealDamage( _Damage );
if ( pPlayer->IsDead() )
{
    // etc.
    …

of this

If you were to have several damage dealing actions in a game frame and your code allowed you to evaluate the “dead” state of the player immediately afterwards then the order damage is dealt would allow the player to “die” at different points in the frame depending on tick order.

This case actually mirrors the Basilisk example from the CCG perfectly, but in a computer simulation this could have more subtle, disastrous effects. Highlevel code is usually rife with these implicit tick order dependencies, and they must be clipped first at this level.

The first step is to always frame your problem using this mentality. Much like the case of the Basilisk, reword the language of your tasks to eliminate ambiguity. The actual deferred implementation comes last.

This last part is done easily enough, provided your programmers have the proper tools. However, writing these tools is a different story altogether.

Countering Intuition

Making your frame instantaneous means that nearly all your systems must be able to be deferred, which is admittedly counter intuitive.

 


Like the rules for detecting a witch

Writing decoupled highlevel code requires a clear separation between actions that change the simulation state and those that evaluate it. It also requires that all state-changing actions are able to be deferred and resolved at some point after their calling. For example, in the case of the Basilisk the gameplay code would issue an action saying “destroy this thing”, but the actual resolution of that action would not happen until after all the other combat actions had been processed.

Putting it Into Practice

As long as you separate your state changing actions from your state evaluating actions, your implementation could take any number of forms. My own approach uses deferred priority queues of actions with delegates or callbacks attachable to the end of each queue.

So in other (pseudo code) words:

 

// A delegate is defined in order to check results of actions
// (and possibly issue further actions).
DELEGATE( eActionType_Combat, Player, PostDamageFunc );

...

// Code issues actions through the queue
DamageAction        CurDamage( this, pPlayer, DamageAmount );

PriorityQueue.IssueAction( CurDamage );

...

// Eventually this queue is consumed.
while ( PriorityQueue.Num() )
{
    PriorityQueue.ConsumeActions( eActionType_Move );
    PriorityQueue.ProcessDelegates( eActionType_Move );

    PriorityQueue.ConsumeActions( eActionType_Combat );
    PriorityQueue.ProcessDelegates( eActionType_Combat );

    // etc.
    ...
}

You may notice that there really is sequence to this “instant of time” in that move actions take place before combat. Plus the whole process can be repeated if any of the delegates issue more actions. However, in this case all aspects of the resolution order are controllable at the highest possible level. The priority queue allows for fine control of particular actions within a specific “action type”, and action types within each iterative pass are always resolved in a defined order.

Resolving tick order dependency here is systemic, trivial, and hopefully intuitive since we committed to a top down view of implementing our game design rules. Note that you need not use my framework. As long as the core concept is maintained (decouple your game design rules, split your behavior, and defer your state changes) any approach will do. This is just one, fairly simple, way to do it.

However be aware that, in my opinion, this level of commitment is often an “all or nothing” affair. Committing to a deferred state management system in one area but not in others introduces the code-base to a brand new kind of ordering hell caused by the desynchronization of the various systems. If you decide to implement a system like this in an engine that has an “immediate” frame of mind, make sure you’re very careful about how the two ideologies intersect.

Further Tips:

Write Good Tools:

A drawback to this kind of programming is that it can spread out the code and make things more abstract and difficult to debug. Much of this can be solved by creating good debug tools. When properly implemented you may find that your deferred data actually can give you more meaningful information than a simple callstack.

Simulate Rather Than Doing and Correcting:

You can reduce the number of splits between action and evaluation code if you allow your systems to simulate an action without actually doing it, returning the important data back to you immediately. This can be good practice anyway depending on the circumstance. I actually had to correct the following behavior deep within a popular engine (code has been converted to pseudo code to protect the innocent):

 

MoveForSwim( pThing, Delta );
if ( !IsInWater( pThing ) )
{
    PutBackInWater( pThing );
}

Splash

This caused roughly a bazillion problems, not the least of which was the fact that objects floating on the surface would make a splash sound every frame (because they were physically leaving and re-entering the water). This is only desirable if in the fiction of your game world all the character types frantically dog paddle.

 


Note to self: replace all monsters with Labradors

The fix used simulation and caused considerably less exciting (yet predictable) results:

 

Vector      NewSwimPos = MoveForSwim_Simulate( pThing, Delta );

if ( !IsPointInWater( NewSwimPos ) )
{
    Delta = FindWaterSurfaceAndTrimDelta( pThing, NewSwimPos, Delta );
}
MoveForSwim( pThing, Delta );

Think before you act

Reduce the Granularity of Your Objects:

You may find that you don’t have the luxury of creating a fully deferred framework. In that case you may still be able to lessen your tick order problems but simply splitting your game objects into less dependent pieces. Many engines have a component model even if it’s not their core feature. Use them. If you’re already using components reduce the dependency between individual components.

Note that this is a good idea in the deferred case as well since it can make architecting, organizing, and eventually multithreading your data much more straightforward.

Conclusion:

Savvy engineers could point out that many of the solutions here also intersect with multithreading and encapsulation concepts, and they’d be right to. This proves that highlevel planning doesn’t necessarily prevent strong, efficient low level goals. Often times they intersect organically.

However, the top down approach introduces a change in workflow and state of mind that can’t be fully quantified. By starting at the top and working your way down, you’ll find that you can stop short of descending into tick order hell, and you’ll retain a fresh new perspective to boot.