It is common for games to offer a 'replay' feature. This feature allows the player to record a sequence of game play and then watch it over again, perhaps from a different viewpoint, or in slow motion. The player may be able to save the recording to disk or memory card, or even transmit it to other players.
When faced with the task of implementing this feature, two different approaches become quickly apparent. The first solution is to store absolute information about all of the objects in the game world (including the player) on a frame by frame basis, or at fixed frequency. This would include data such as position, orientation, and so on. The replayed sequence is then constructed by streaming this information back into the game engine, and interpolating where necessary.
A second and much more elegant approach is to make use of the inherent predictability of computer software: The same sequence of operations performed on the same set of data will always produce the same result. It is reasonable to conclude that a sequence of game play may be precisely reproduced by recording only the initial state of the game, along with the player's inputs. The initial state can then be restored, and the recorded inputs reapplied, to produce the same sequence of play. This solution is instantly more appealing because the amount of data that needs to be stored is much smaller. It is also simpler to implement and maintain, as all necessary coding can take place at the 'player input' level, and remain independent of the underlying game engine.
If you've ever tried to implement a replay feature using this method, then you will know that life is not quite so simple. Despite the fact that the same program is running, with same inputs, things just don't happen exactly the same way the second time around. This is because game software does not run in isolation. It makes extensive use of externally generated run-time data which is somewhat less predictable, and undermines the natural reproducibility of the game engine itself. Just one small difference in this external data will cause the replayed sequence to diverge from the original, potentially resulting in completely different game events. This is often an insurmountable problem. Game software is highly complex, and the task of isolating and dealing with externally generated data can be overwhelming.
However, if external data is isolated at the start of development it can be done effectively and with minimal effort. Moreover, the ability to precisely reproduce a sequence of game play in this way offers many other benefits to development beyond implementing a replay feature. If you have reproducibility, then you have a way of reproducing even the most obscure bug discovered by your testers. More significantly, you also have the foundation of a low bandwidth networking solution.
This article is about building such a game engine. An engine which can record a player's inputs, reapply to them to the same initial state, and precisely reproduce minutes or even hours of game play just as reliably as a video recording. Reproducibility effects most of the components of a game engine, and is characterized by behavioral criteria rather than particular algorithms. For this reason, the focus of this article is to present ideas and design techniques which can be integrated into any game engine, rather than specific code. Most of these ideas have evolved over time through discussions with other experienced game programmers, and proved beneficial to many projects in different ways, so I will discuss how reproducibility can be used to implement other game features, such as networking. I will also highlight the main implementation problems that both I and others have encountered, along with practical solutions.
Maybe you are not convinced yet. Maybe you don't think that you need or even really want reproducible behavior in your software. So before continuing I shall review the benefits that reproducibility has to offer.
Reproducibility : Inputs & Outputs
I have already mentioned that programs are inherently "deterministic". The same inputs applied to the the same starting state will produce the same final state. So exactly what is it that makes a game engine not deterministic? To answer this question, we first need to define and identify the inputs, outputs, and 'state' of our game engine.
An input is a datum passed to the game engine at run time from an external source, which is used in some way to modify internal data. An obvious example is a player's input. Conversely, outputs are data which are generated by the engine and passed to an external target, but which are not used internally by the game. An example output might be vertex data passed to the GPU for rendering. All remaining persistent internal data we shall term as "game state". Examples of a game state data are the speed of a car, or the player's position in the world. Having defined these terms, we can set about identifying them in a game engine. Figure 1.1 represents a simple input/output/state arrangement for a typical game engine.
Inputs, Outputs, and Game State
Some items in figure 1.1 are fairly obvious. Others less so, and warrant a more detailed discussion. For the time being we can begin to recognize the sources of non-reproducible effects in our game, and develop a strategy for dealing with them. All inputs (apart from the player's inputs) need to be isolated and either made to be predictable, or de-coupled from the game state. The player's input must, of course, change the game state in some way, and so these inputs are to be recorded and reapplied in the correct sequence and at precisely the same time that they were originally applied.
If this strategy is successful then during play the game state will undergo numerous state changes, progressing from state to another through the passage of time. When we view a replay of this sequence, the game will start in the same initial state and progress through exactly the same transitions (with the same player inputs reapplied), passing through exactly the same sequence of states, and arriving at exactly the same final state. Let's be clear about what this means: at the end of the replay, every single item of data in the game state will finish in exactly the same state as it did when the game sequence was originally played. We cannot afford for even one thing to be different at any point in the replay, or else it will diverge from the original. But so long as we isolate all of our inputs, then this state transition will occur correctly, and predictably, every time that the sequence is replayed.
It should be noted that outputs are of no concern to reproducibility. They neither effect the game state, nor the inputs. Once they have been identified we need not consider them any further. However, there are some traps to look out for. For instance, rendering data may actually used by other parts of the game, such as the collision detection system. If this is the case, then this rendering data must be considered to be part of the game state.
All that remains, then, is to deal with each of the game inputs in turn. The first input listed in figure 1.1 is that of the player, and we already have a have a good idea of what we are going to do with that. The next item in the list that requires our attention is 'time'.