Designing for predictability

(cross-posted to http://mtnphil.wordpress.com/2012/03/14/designing-for-predictability/)

When writing a game or game engine, it can be very beneficial to ensure that your engine can produce predictable behavior in response to a given set of inputs (either human inputs or random number seeds).

Some of the benefits are:

In this post I'll go over some of the obvious things I did to prepare Tank Negotiator for this, as well as some less obvious problems I encountered when needing reliable replays.

Random number seeds

This is fairly straightforward. In order to have predictable gameplay, you must have the exact same set of random numbers generated each time. This means you need to choose your random number seed and store this information so it can re-used.

Alternatively, you can store the results of the random number generator, but this is obviously a lot more information.

Note that not every random number sequence generated by your game needs to be repeatable, though this depends on your requirements. For Tank Negotiator, I use a repeatable random number sequence for gameplay-crucial events (such as which type of power ups to generate, and when) and a non-repeatable one for non-essential visual things (such as the orientation of bullet hole decals).

You maybe just be tempted to use a single repeatable random number sequence for all random numbers required, but be careful of where they are used. If you require random numbers during your Draw cycle then you probably don't want to use the same generator as that used during your Update cycle, since there may not be a 1-to-1 correspondence between Update and Draw. If a Draw cycle is skipped due to frame-rate issues, your entire sequence will then be off (more on this in the next section).

For this reason I very carefully identify areas of code that consist of crucial game state and are always called in a consistent manner - and those areas use a repeatable sequence, while other areas use a very clearly identified "unpredictable" random number generator.

Fixed time step

In the XNA framework, the default behavior is for the Update cycle to use a fixed time-step. This means that the Update method is called every 16.66666 milliseconds (if the frame-rate is set to 60 FPS) - always the same time span (Draw cycles may be skipped if the GPU is overburdened). This makes things much easier when it comes to predictability since you know exactly how long a frame will be. Any calculations you make with the "elapsed frame time" will always be the same: you can store one set of inputs for each frame and always get the same results.

Frankly, I'm not sure how you would ensure predictable behavior if the time step was variable, since floating point inaccuracies would gradually result in a deviation (more on how bad this can get in the next section). I suppose you would have to re-calibrate everything every once in a while - but then you're losing a lot of benefits of predictability.

Compressing inputs

When it comes time to actually implement recording of player input, you will probably want to apply some compression to the data. On/off buttons are fairly easy to put in a bitfield, but a pair of analog 2d inputs (e.g. a left and right thumbstick) result in 16 bytes of information per player per frame. At 60 FPS, that's nearly a kilobyte of data per second per player.

There are many ways to compress this data. You could pack it into lower precision floating point values, or use some sort of temporal compression scheme - it really depends on the nature of the input and the size of the data.

The important thing to remember is that if you use a lossy compression scheme, you actually need to apply this compression and decompression when responding to the actual player inputs while "recording" the game play (as opposed to just during playback). Otherwise, floating point precision errors will begin creeping up on you.

In Tank Negotiator, I had everything set up - or so I thought - to allow for playbacks based on recorded controller input. But something just wasn't right - player units would get off course after a few seconds. And once something is slightly off, everything just falls apart (the butterfly effect). It took a while, but it finally dawned on me that because I was compressing 32 bit floating point values to 16 bit floating point values when recording player inputs, that I actually needed to apply the compression (and then decompress) during actual gameplay (luckily this results in no perceptible difference to the player).

Predictable component update order

I'm using a fairly simple somewhat hierarchical list of game components that implement an Update method. From the beginning I knew I had to keep things roughly in order (e.g. component A needs to be updated after component B, since it depends on something component B has calculated).

Tank Negotiator was the first modern game I worked on, so its architecture was honestly a bit of a mess. There were many things which just happened to be added to a component list in the right order, and some hidden dependencies that only manifested themselves if things ended up in the "wrong" order. Dependencies were not clearly called out.

When it came time to implement the replay system, it was obvious there were still some problems. Most of them were solved by applying an explicit update order to all the components. Some were a little more insidious, such as certain player components being added to a component list in a different order during a replay than they were during the live game. They were marked with the same update order number since they were all the same type of component - the problem was that there was one component for each player.

The different order meant that things would proceed along just fine - until two players's tanks collided with each other. Worse yet, it only happened when 3 or more players were in the game. The fix was to also consider the "player index" in the update order.

The moral of the story is: be very explicit about the order your game state is updated. Don't leave anything to chance.

Also related to component updates...

One very insidious bug I had was related not to component update order, but to the fact that some components are updated all of the time (even when the game is paused), more are updated only while the game is un-paused, and some - very unfortunately - are updated during the transition period when the pause screen is in the process of going away! Yes, that is a bug.

The player has a tank whose top speed is reduced while they are shooting bullets. Their top speed recovers gradually in the few seconds following a bullet being fired. The component that measures the time since the last bullet was fired was the "unfortunate component" mentioned in the previous paragraph.

If a pause screen was invoked during the playback of a recorded game, then when gameplay finally resumed after the pause screen was dismissed there would be slightly more time that had elapsed since "last bullet fired". This would result in a slightly slower speed (like 0.0001% slower) - which, when the butterfly effect is taken into account, throws everything off!

Again, this is related to the crappy game component update architecture I had implemented. I cannot emphasize enough the importance of very explicitly-ordered update logic for game state. If you support pausing the game, try to understand when each component will be de-activated (for instance - could the pause screen be triggered in the middle of an Update cycle, causing some components to update and others to not? That would probably be a bug).

Making changes

Wonderful. You've built a predictably-random, explicitly-ordered game. Now you need to make changes because you're not quite ready to ship yet. Or, you've shipped but you need to make an update with a bug fix. You tweak a few values: weapon A does a little more damage, power-up B appears less often.

Congratulations, you've broken all your recorded games! For Tank Negotiator, this has been an issue. I want to supply some sample "recorded games" with the trial version of the game so people can see some intense multiplayer action that they might not get to within the short trial time limit. This means that once I have a recorded game I think is worthwhile, I can't change any of the game's constants - at least, not without versioning the recorded game.

In my case, I store a single version number for the entire game. For any part of gameplay I change, I offload that to a special section of logic that switches values (or whatever) based on the recorded game version number.

If I were starting again from scratch, I would favor a more robust system. For instance, you could store all game constants as part of the recorded game, and then tweak to your hearts content without needing to make any additional code changes to support old recorded game versions.

You may still need some "app compat" logic based on some global version number if you're actually changing key game logic (for instance, adding a new type of power up, or changing the way a weapon works entirely).

And in conclusion...

Hopefully this has been helpful to anyone trying to implement a replay system, whether it actually gets used by players, or is simply for reproducing and diagnosing bugs. A little consideration ahead of time can ensure your game is "replay-ready" when the time comes.