Timestepping

What's new?

If you've seen articles like this before you probably wonder why you're supposed to read yet another one. Here's a list of the important key points.

• The algorithms presented are not new but they may be in variations you haven't seen. The important part is that this article shows ways to evaluate them and the pros and cons of each method.
  
• Focus is on vertical synchronization and why your algorithms must take this into account.
  
• You should calculate the likely timing errors your algorithm will induce.
• Are interpolated draws, as desribed in [1] and [2], worth the trouble? What is gained and what is lost?
  
• Threads and triple buffering, how can they help?
  
• Choose the best timestep algorithm for your game. The needs are not the same for all types of games.

The basics

Almost every animated computer game will have some kind of a time stepping loop. In every cycle of this loop the game mechanics are integrated by some small delta time. This procedure we can call an update . After an update the game state is typically drawn on screen. Simply call this a draw . We should say that a draw doesn't change the game state in any way. It will therefore make no sense to do two draws in a row since the game would be rendering the same frame twice. It becomes important that the updates are synchronized with real time so that the accumulated delta times add up to the actual elapsed wall clock time. Otherwise the game may run too fast or too slow and likely with irregular speed. A simple solution to this is to use a variable delta time in the updates as follows:

start = current_time()
loop
    dt = current_time() – start
    start = current_time()
    update(dt)
    draw()
end

Listing 1 : Variable time step.

Here the game mechanics are moved along with a time of dt each update. It is called variable since dt will be different each cycle depending on the time it takes to update and draw. The method above is easy and commonly used but not deterministic. This can in a bad scenario mean that the game behaves well in one run while blowing up in your face in the next. Much care must be taken when programming a variable time step game to make sure it works reasonably well with very different timesteps. Things that become especially tricky to handle are physics, collision detection, networking and predictions for AI. Therefore many programmers suggest a fixed time step to make life easier and save some computation time. Fixed time steps is mainly what we'll focus on here. If you're not convinced this is a good idea please read the previously mentioned articles. Lets look at the simplest possible fixed time step algorithm:

dt = 1/60
loop
    update(dt)
    draw()
end

Listing 2 : Fixed time step without speed control.

Here the delta time is fixed to 1/60 of second each update i.e. 60 frames per second. The game is now deterministic to the level of floating point precision being different on different machines. This is probably close enough to deterministic for your game. It does however not at all correspond to real time. Your game will behave the same each time you run it on every machine but the speed will obviously differ widely. Let's look at the case where the computer does updates and draws too fast. We may try to solve it with something like:

dt = 1/60
start = current_time()
num = 0
loop
    update(dt)
    draw()
    num = num + 1
    wait(start + num*dt)
end

Listing 3 : Fixed time step with speed control.

The wait function should be interpreted as "wait until we've reached this time stamp". What happens in the first frame is that the game waits until 1/60 of a second has passed before doing the next update. This guarantees that the interval between updates will be correct if the computer can do the update and draw fast enough. Note that we always measure the time elapsed since the game loop started and not only the time of the current frame. This way we don't introduce any unnecessary clock drift from per frame calculation errors. All our algorithms work this way because we want to synchronize with real time also in the long run.

Now all seems well if we have a hasty computer, but now comes the real problem and the reason for writing this article. What matters after all is at what time the user gets to see the image of the game's state on screen. The drawing may likely use double buffering and the users computer can either have vertical synchronization enabld or disabled. If you don't know what vertical synchronization is please read this .

Vertical synchronization

If vsync is not enabled the new image will immediately be displayed on screen as soon as the draw function finishes. So is that a problem? Yes. Since the time it takes to do an update and draw may vary also the time between frames displayed on screen will vary. The game may appear jerky, sometimes moving faster and sometimes slower, because the rendered frames always show the game state logically 1/60 of a second apart. I will call this a time variation flaw in lack of a better name. The error can be up to 1.0 dt = 1/60 second but is likely smaller than that. The average speed of the game in the long run will however remain the same on all fast machines. Depending on the game this error of likely much less than dt and may not even be noticeable. 2D games genarlly suffer more than 3D games. Another, worse problem, is the tearing we get when vsync is disabled. The game may show parts of the old frame and new frame at the same time. This makes animations appear cut off and is very visible when the game has big, fast moving objects such as a scrolling background.

To solve the timing error we can break out the common command to swap buffers from the draw procedure and instead insert it after the wait in listing 3. The frame is now fully rendered to the back buffer in the draw phase, we then do the waiting and lastly swap the buffers right in time to get a nice 1/60 interval between frames. Tearing will still kill some games (Yes, I'm picky) but without vsync there is nothing we can do about it.

So what if vsync is enabled? Actually if vsync was set to 60 Hz the program in listing 2 (not 3) would be the perfect choice for a fast computer. Swapping buffers will now wait for the next vertical blank which happens with 1/60 of a second interval and our program is automatically synchronized with real time. However it is usually not possible to really know if vsync is enabled or in what frequency it runs. You may get a good guess but no guarantees. So what happens with the method in listing 3, with the swap buffer addition, if we consider 60 Hz vsync on a fast enough computer?

Say that the buffers where just swapped and we start on the next frame making first the update, then the draw. After the draw and wait exactly 1/60 second should've passed but since the measuring is not perfect we may miss the vblank by a mircosecond and we're forced to wait for another whole 1/60 second before the program can do the swap. All later frames will then need to wait a negative amount of time and we're out of sync forever. Too bad. Now you might notice that if the swap buffer is moved to before the wait all is well in wonderland, but we're back to the method which was bad for disabled vsync. Indeed it's contradictive.

The first solution we may think of is to wait only 95% of dt, swap buffers and then wait for the full dt to elapse. This does however require our time measuring to be synchronized with the vblanks so that a full dt is elapsed exactly when the vblank comes. It all seems dangerous. But before trying to fix anything let's look at the case when the vsync frequency is different from the update frequency.

Interpolated draws

Consider a vsync of 75 Hz and the update delta time 1/60 (60 Hz). It gives us five vblanks on only four updates. This means that every fifth frame must be the same as the previous. Figure 1 tries to illustrate this simple fact. It is far worse than anything we've looked at so far since the game will seem to halt for a short time when we render the same frame twice. This is very noticable, especially in 2D games. So what can we do about it without losing the nice deterministic bahavior?

 
Figure 1 : With four updates (illustrated as U) spread on five vblanks, two frames are bound to be the same.

A common idea is to save the current and the next game state and interpolate these before doing a draw. Of course we only need to save states relevant to the drawing like positions, rotations, scaling, and other animated properties. The code can look like this:

dt = 1/60
start = current_time()
num = 0
loop
    while (current_time() – start) > num*dt
        update(dt)
        num = num + 1
    end
   
    alpha = (current_time() – start)/dt – (num-1);
    draw_interpolated(alpha)
    swap()
end
   
Listing 4 . Fixed time step with speed control and interpolated draws.

When an update occures in the code above we calculate what the game state will be 1/60 of a second in the future. As long as this time has not passed we will not do another update but instead draw as many times as we can and interpolate towards, but not beyond, this future game state. Notice that the draw now has a state which is changed by the interpolation variable alpha. It's become both a draw and lightweight update procedure. Figure 2 tries to explain a possible scenario. With a fast computer this method can produce unique frames for each vblank in 75 Hz. The result is better than before in the sense that the user will less likely notice the irregularities.

• The first update U takes 0.2 dt
  
• A draw D(0.2) is hence done with interpolation 0.2.
  
• Swap S waits until vblank at 0.8 dt = 1/75 seconds
• Only 0.8 dt < dt has passed so we set out on a new draw with interpolation D(0.8)
• Swap S waits until vblank at 1.6 dt = 2/75 seconds
• Update U takes 0.2 dt
• Draw D(0.8) is done using the latest data from the update we just did i.e. we're drawing the game state at time 1.8 dt .
  
• Swap S waits until vblank at 2.4 dt = 3/75 seconds
• and so on…
  

Threads

Another approach which may pop up in your mind is to use threads. One thread could be doing all updates and another thread does the drawing. The program can look like the one in listing 5.

[Thread 1]
dt = 1/60
start = current_time()
num = 0
loop
    update(dt)
    num = num + 1
    wait(start + num*dt)
end

[Thread 2]
loop
    draw() // Can also be interpolated
    swap()
end

Listing 5 . Fixed time step and drawing in a separate thread.

There are some alternatives to how the draw and update would interact here. The draw can for example (a) always use the latest fully completed update, (b) use an interpolation of the two latest updates or (c) always use the absolutely latest data from the currently ongoing update. Alternative (c) implies that we draw parts of the old and new state in the same frame. All these flavors come with more or less complicated resource locking and need for data redundancy but we shall not go into that. Just know that whatever the setup is all our problems with vsync, time variation and lag remains.

Too see this we just need to look at some examples. Say that we choose the easy method (a). The first draw must wait for the first update to finish and then there will be no point in doing another draw before the next update is done. On a fast enough computer it would be the same result as using the program in listing 3. We still have the vsync waiting problem where we can get inconsistent times between frames if vsync is disabled or miss a swap if it is enabled. The upside is that if a draw would take a long time to complete we can still proceed with an update at the same time. You can reason on method (b) and (c) in the same way.

So the only gain is that we can start on the next update even when the draw is waiting for a vsync or is busy rendering. Still all the problems from before remain. The cost is data redundancy and added difficulty of concurrency issues.

There are of course plenty of other ways to use threads to speed up the individual updates and draws, but this is not an article on optimization.

Triple buffering

Something we also should consider is if triple buffering can help us. If we have three draw buffers we can use one on the screen, put one on queue to the screen and do our drawing to the third. The queued buffer makes it possible to wait for vsync while doing other computations.

Triple buffering will only have effect if vsync is enabled and it will make the swap command return immediately. The gain is that we can begin another draw or update at the same time as we're waiting for the next vblank. It doesn't make a difference for the fast computer scenarios that's discussed above. It can be useful if the display frequency is lower than the update frequency or if the time of draws often become larger than the update frequency so we are forced to drop frames. The important thing to remember is that all the problems above still apply.

This is kind of like a simple version of the thread approach. The gain is that we can, like with threads, start a new update while waiting for vsync. Unlike threads however we can't start the update while still drawing.

Slow computers

So far we've assumed only fast enough computers with no temporary slowdowns. It's rarely the case in practice though. If the update and draw takes longer time than dt then we are simply forced to drop frames. If vsync is not enabled we can hope that sometime in the future a frame will be produced in less time than dt and get us back on track. If vsync is enabled however we must make up for this lost frame by doing two updates in a row. If we're always forced to do this the framerate will be half of the update frequency, e.g. 30 Hz with 60 Hz updates. This may be acceptable and it's not possible to do anything about besides getting a faster computer.

The pseudo code in listing 5 below does many updates in a row if necessary to get back on track with the real time.

dt = 1/60
start = current_time()
num = 0
loop
    do
        update(dt)
        num = num+1
    while current_time() – start > num * dt
    draw()
    swap()
    wait(start + num*dt)
end

Listing 5 : Fixed time step with lower and upper bound speed control.

It's a simple but effective way to make slow computers keep up. Note that if the program should halt for a long time it will do a number of subsequent updates without doing any draws. I would recommend to set a bound on the number of consecutive updates in the while loop, e.g. a maximum of 5 before a draw is done. The game will then run in fast forward until it's back on track with realtime instead of completely freezing. This is left out from the code to keep it clean and simple. If the updates take longer time than dt we simply can't run the game on the computer in question, our only option will be to buy a new one.

Alternating framerate

It may be an annoyance if the framerate keeps alternating. This can happen if the draw load varies much or if the computer is only close to fast enough to render each frame. Sometimes the program is hitting the next vblank and other times missing it. A common case is a 60 Hz game going back and forth from 30 Hz. It's then better to step down and always do 30 Hz. This can be done by measuring the times it takes to produce each frame and if it's above dt too often we assume that we need to always do more updates. If the computer can't do 60 Hz we do 2 updates per draw and get 30 Hz. If it's still too slow we do 3 updates and get 20 Hz and so on. Listing 6 shows this idea in code.