Fixed Timestep Tutorial

2014-01-31

This tutorial demonstrates a way of running animation and game logic at a constant speed independent of effective frame rate. It's a pretty simple technique, so I'll try to keep it short and sweet.

Frame-based animation

Frame-based animation is a system in which the game world is updated one iteration each frame. This is the easiest system to implement, and the way most new programmers do it, but it has several drawbacks. The speed of your game is effectively tied to the frame rate, which means it will run more slowly (chronologically) on older computers, and faster on newer ones. This is generally undesirable.

Variable interval time-based animation

Variable interval time-based animation is a system in which the game state is updated once per frame, similarly to frame-based animation. The difference from frame-based animation is that the amount of time elapsed since the last frame is used as part of your game state update mechanisms. For example, if an object is to move at a rate of three units per second, you might do something like this:

object.position += (3.0 * interval);

The larger interval is, the further the object moves.

As opposed to frame-based animation, this system allows your game to run at a constant speed regardless of frame rate, but it has its own drawbacks. It tends to be rather unstable; different frame rates will produce slightly (or in some cases, dramatically) different results. Take, for instance, an object moving along a curved path:

At each iteration, the object is moved forward, and the direction it's moving is rotated slightly. Notice that the object's path hits the edge of the wall. This works fine with short timesteps, but with longer ones, something like this might happen:

The object has missed the wall entirely because its curve is less rounded, since it's moving longer distances and turning sharper angles to make up for the longer time interval. The behavior of your game has been indirectly affected by a difference in frame rate. This could potentially be remedied by subdividing the timesteps as necessary, or with more sophisticated collision detection code that takes into account the curved path of the object. However, there's a much simpler and easier way:

Fixed interval time-based animation

Fixed interval time-based animation is the system I'll be demonstrating in this tutorial. Using this system gives you most of the benefits of a variable interval system with a lot less headache. If you've already implemented frame-based or variable interval time-based animation, you can switch to fixed interval time-based animation with very little change in your code.

In a nutshell, the idea behind fixed interval time-based animation is to update the state of your game world a variable number of times per frame, but at a fixed timestep interval. If a particularly complex scene is being drawn, the frame rate will bog down, causing more game world update cycles to happen at once in order to catch up. If a very simple scene is being drawn and the frame rate is high, the state of the game world will be updated fewer times (or not at all, in some cases) in one frame.

You may want to cap the number of update cycles at some point to prevent large hiccups in performance from causing mass mayhem in your game. If your game stalls for some reason (due to a background task, large amounts of virtual memory being paged in, etc.), this will allow gameplay to pause momentarily until it can run at a reasonable speed again, rather than catching up by a large amount while the user has no way of interacting with the game. (Note that if your game runs over a network, and needs to remain synchronized with a peer, capping the number of update cycles may not be an option.)

So, enough preamble. On with some example code!

#define MAXIMUM_FRAME_RATE 120
#define MINIMUM_FRAME_RATE 15
#define UPDATE_INTERVAL (1.0 / MAXIMUM_FRAME_RATE)
#define MAX_CYCLES_PER_FRAME (MAXIMUM_FRAME_RATE / MINIMUM_FRAME_RATE)

void runGame() {
	static double lastFrameTime = 0.0;
	static double cyclesLeftOver = 0.0;
	double currentTime;
	double updateIterations;
	
	currentTime = GetCurrentTime();
	updateIterations = (currentTime - lastFrameTime) + cyclesLeftOver;
	
	if (updateIterations > MAX_CYCLES_PER_FRAME * UPDATE_INTERVAL) {
		updateIterations = MAX_CYCLES_PER_FRAME * UPDATE_INTERVAL;
	}
	
	while (updateIterations > UPDATE_INTERVAL) {
		updateIterations -= UPDATE_INTERVAL;
		
		updateGame(); // Update game state a variable number of times
	}
	
	cyclesLeftOver = updateIterations;
	lastFrameTime = currentTime;
	
	drawScene(); // Draw the scene only once
}

First, we define the constants MAXIMUM_FRAME_RATE, MINIMUM_FRAME_RATE, UPDATE_INTERVAL, and MAX_CYCLES_PER_FRAME. MAXIMUM_FRAME_RATE determines the frequency of update cycles; MINIMUM_FRAME_RATE is used to constrain the number of update cycles per frame. UPDATE_INTERVAL is the amount of time, in seconds, that passes between updates. MAX_CYCLES_PER_FRAME is the maximum number of updates per frame before gameplay starts slowing down to let drawing catch up.

In the runGame() function, two static variables are defined: lastFrameTime and cyclesLeftOver. lastFrameTime is the return value of GetCurrentTime() (more on this in a moment) at the end of the last call to runGame(). cyclesLeftOver stores fractions of update cycles between calls to runGame() to be carried out later, when/if they add up to UPDATE_INTERVAL, and consequently an extra cycle.

The first thing we do in the function is get the current time in seconds with GetCurrentTime(). This is a made-up function name; you'll have to replace it with an appropriate function call in whatever API you're using. I'll list some functions you can use for it in various APIs at the end of the tutorial.

currentTime is used, along with lastFrameTime and cyclesLeftOver, to compute the number of update cycles for this frame. The number of update cycles is then capped to meet the minimum frame rate. Note that updateIterations is actually an interval, not a literal number of cycles. This is more convenient, as we'll see below.

The while loop runs a variable number of times, determined by the value of updateIterations. In your updateGame function, you should perform the necessary actions to update the state of your game world by one iteration. Note that if you're converting your code from a variable-interval system (or want to have the flexibility to do the reverse) and your game state updates require an interval argument, the appropriate value to pass for the interval is the UPDATE_INTERVAL constant.

After the game update loop is finished running, the remaining value of updateIterations (which, after the while loop, will be less than UPDATE_INTERVAL) is saved in cyclesLeftOver, and currentTime is saved in lastFrameTime. At this point, you're ready to draw the game scene.

One other thing to watch for: In this example, I set the initial value of lastFrameTime to 0.0. In some APIs, The function you choose to replace GetCurrentTime() will return time since program startup, which would be appropriate here; however, some others will return the time since the computer last started, or since a fixed reference date. In these cases, you'll want to explicitly set the initial value of lastFrameTime, like so:

if (lastFrameTime == 0.0) {
	lastFrameTime = GetCurrentTime();
}

As promised, here's a list of functions you can use to get the current time, in various APIs. See your API documentation for more information on how to use them:

API	Function name	Units returned
Carbon	`GetCurrentEventTime()`	Seconds
Cocoa	`[NSDate timeIntervalSinceReferenceDate]`	Seconds
POSIX	`gettimeofday()`	Microseconds
Linux	`clock_gettime()`	Seconds/nanoseconds
SDL	`SDL_GetTicks()`	Milliseconds
GLUT	`glutGet(GLUT_ELAPSED_TIME)`	Milliseconds
Win32	`QueryPerformanceCounter()`	Variable; see also `QueryPerformanceFrequency()`