Features

Instant Replay : Building a Game Engine with Reproducible Behavior

A typical way of implementing frame rate independence is to update the game state once for each rendered frame. At the start of each update the system timer is read, and the time that has elapsed since the last update is calculated. This "last frame time" is used to calculate the next game state, and then the next frame is then rendered, and so on. For example, if a car is moving with some velocity 'V' is the game world, and its position at the last rendered frame is 'P1', then its position for the next frame, P2, may be calculated using the simple integration:

P2 = P1 + V * last_frame_time

You may not have thought of time as being an input into your game engine before, but looking at the above equation you can see that the result of each game state transition is determined by the last measured frame time. The sequence of game states that the engine passes through is directly dependent on time readings from the system timer. Even though the animation is independent of frame rate, this dependency will undermine the reproducibility of the game engine because we cannot rely on getting the same frame times during the replay.

For example, imagine that our engine renders two frames, and that the frame-time for each update is 30 milliseconds. This will result in two state changes, each representing a time update of 30ms. Now imagine that we wish to replay this sequence, as seen from a different viewpoint in the world. From this new viewpoint, we can see fewer world objects, and consequently our engine renders at a higher frame rate. Perhaps a single frame takes only 20ms to render. Instead of generating 2 frames of 30ms, our frame rate independent engine now generates 3 frames of 20ms. The result of this is that our car's position is now slightly different. Even though it has been moving for exactly the same amount of time, inaccuracies in the integration of its velocity mean that its position is marginally different. In the replay, the car is not passing through the same set of states as it did the original sequence. Aside from this, we also have a problem reapplying the player inputs. If the inputs are read once per frame, then we cannot apply them at exactly the same time in the replay as we did when they were originally applied.

Dealing with system time readings is thus critical to reproducibility. Even when running a replay on the same computer that it was generated, there is no guarantee that the same timer readings will be generated. Even making a small change to the view point will result in different readings, and therefore a different sequence of game states. This problem is exacerbated when running a PC based game, because the OS may be executing other external processes, or the player may, perhaps, decide to upgrade his or her graphics card to achieve a higher frame rate!

Unfortunately, timer readings cannot be eliminated from the game, or even made to be predictable, if we are to retain frame rate independent animation. However, the game state may easily be de-coupled from the system time. Perhaps the simplest way to do this is to quantise the state execution time, by updating the game state at a fixed frequency. Game updates can then be controlled with a small time control loop. This loop reads the system time, and decides how many fixed-time state updates to execute. When the required number of updates have been applied, the frame is rendered. This of course means that several state updates may occur to produce a single rendered frame of animation.

The C-like pseudo code for such a system is shown below. In this case, the game state is updated at a frequency of 100Hz (10 millisecond increments).

static int execution_time; //time to be executed this frame
static int num_updates = 0;
static const int update_time = 10; //miliseconds = 100hz;
static bool playing = true;
while(playing) //frame update
{

//see how much time we need to execute for the next rendered //frame : read system timer & find elapsed time
execution_time += LastFrameTime();
while(execution_time > update_time)
{

//read & save player inputs
ReadPlayerInputs();
SavePlayerInputs(num_updates);

//update game state
UpdatePlayer(update_time);
UpdatePhysics(update_time);
UpdateAI(update_time);
//etc…

execution_time -= update_time;
num_updates++;
}
RenderFrame();

Notice that any unexecuted time remaining in execution_time is carried over to the next frame update. This is important, because when the game is achieving a high frame rate, no time is 'lost' and frame rate independence is maintained. This schema also gives us a perfect way to record and reapply player inputs. The inputs are read once per state update, and are recorded against the total number of state updates that have been executed at that point. This means that they can be reapplied against exactly the same game state that they were originally applied.

Reproducing a sequence of game play generated in this way thus becomes a simple task. Starting from the same initial state we can execute the replay using the same process of updating the game state at a fixed frequency. Stored inputs can be reapplied by checking the number of updates that have been executed, to see if they match the recorded number of updates of the next input in the list.

even if the frame rate is different during in the replay, the game state will pass through exactly the same sequence of states, and that the player inputs will applied at exactly the same time (and to the same game state) that they were originally. The code needed to execute a replay is shown below.

static bool replaying = true;
while(replaying) //frame update
{

//see how much time we need to execute for the next rendered //frame, as before
execution_time += LastFrameTime();
while(execution_time> update_time)
{

//reapply recorded inputs
if(TimeToApplyNextSavedPlayerInput(num_updates))
ApplyNextSavedPlayerInput();

//update game state
UpdatePlayer(update_time);
UpdatePhysics(update_time);
UpdateAI(update_time);
//etc…

execution_time -= update_time;
num_updates++;
}
RenderFrame();

Thus, the replayed sequence will always generate identical game behavior, even if the viewpoint is changed, or the replay is run on a different hardware configuration. It is important to note that all components of the game which modify the game state should be parameterised by the 'game time' only. Under no circumstances should a programmer be tempted to read the system time directly, as to do so and use it to change the game state will result in non-reproducible behavior

In order to reproduce a sequence of game play it is necessary to ensure that the replayed sequence starts in the same initial state as the original. It is almost certain that we will want to record sequences mid-game, and so it necessary to be able to save and reload the game state. In practice this is not difficult to achieve, and it is probable that we will require a load and save game feature anyway. However, it is important to ensure that the loaded game state is identical to the original. If it is not, the subsequent behavior may not identically match that of the original. We have now progressed a good way towards a generic design for a reproducible game engine. However there are still some remaining points to be dealt with.

Other External Data Sources
The input list in the beginning of this feature includes the somewhat ambiguous item 'External Data', which essentially means "any other source of externally generated run-time data", and may include hardware or operating system sources, or software libraries used by the game. These are specific to each individual game, (for example, some games make use of software libraries licensed written by other developers) and so need to be considered on a case by case basis. However, the important thing is that they do not damage the reproducibility of the engine. Any external data source used by the game needs to be reproducible. It is also important that it can be restored by the game when the game state is loaded.

Generally there actually few such sources, but one which is used in most games is the C/C++ random number generator provided by the standard library. This random number generator is in fact reproducible. It will always generate the same sequence given the same seed. However there is a problem with loading and saving the game state.

When a game is reloaded it is clearly necessary to restore the random number generator so that it will generate the same sequence from that point as it did after the game was saved. A tempting solution would be to re-seed the random number generator whenever a save occurs, and save the seed as part of the saved game state. However, this is not a good approach, because it means that the act of saving the game will effectively change the game state, and we wish to be able to save and reload the game freely.

The easiest way to circumnavigate this problem is to avoid using the standard library random number function altogether, and instead use our own. Fortunately there are many pseudo-random number algorithms in existence, which can be coded and included in the game engine; it is then only necessary to save the generator's data as part of the game state.

______________________________________________________

Floating Point Math

join | contact us | advertise | write | my profile
news | features | companies | jobs | resumes | education | product guide | projects | store



Copyright © 2003 CMP Media LLC

privacy policy | terms of service