Game Loops with Fixed Simulation Steps

Hi!

Today I want to talk about game loops. If you're a game developer, you surely know what a game loop is. However, let me summarize it with the following image:

Figure 1. Traditional Game Loop (from http://gameprogrammingpatterns.com)

A game loop is basically a sequence of instructions that is repeated continously from the beginning to the end of the game and which is in charge of interpreting input, simulating the world and rendering the world on screen. Very often, there is a 1:1 mapping between the concept of frame, and one execution of the loop, because a frame of the game is rendered each execution of the loop. However, this doesn't need to be the case and you can have different frame rates for the rendering function and for the simulation function. In fact, a common approach in sophisticated, simulation-intensive games is to fix the timestep of the simulation function in order to achieve predictable and deterministic behaviour of the simulation. Meanwhile, the render function is executed as fast as it can run, leading to a higher, variable display rate. You can read more about this decoupling in the following eye-opener posts:

[1] Fix your timestep

[2] Interpolated Physics Rendering

[3] deWITTERS Game Loop

I actually encourage you to read the previous posts (especially the first one) before continuing reading. Otherwise, this post may be difficult to follow.

I had the idea of writing this article because I tried to use the technique suggested in [1] with no success. After failing, I skimmed through the comments of the post and I found two comments (by Nick and Voy) which basically stated that although the technique was really valuable, the implementation suffered an off by one error, which resulted in no simulation step taken at all. This was in fact the problem I was having (entities of the game weren't moving), and therefore I set out to fix it for educational purposes.

Before showing the actual code, let me illustrate with figures how we want the simulation to happen:

 Figure 2

 Figure 3

Figure 4

Figure 2 shows that we divide the time of the game in discrete chunks of the same size. Don't let the concrete numbers fool you: you'll typically want the simulation to take small steps (say 0.01 seconds) in order to reduce numerical errors. The point is that there are concrete, fixed moments over the life of the game at which we want to simulate the world, and we DON'T want to simulate at any other moments between those.

For instance, let's assume that the time is somewhere between the beginning of the game (0) and the first moment at which we want to simulate (1). This corresponds to what Figure 3 shows. The green arrows show different game times at which we can be, whereas the red arrow shows the point that we actually want to simulate for these times. Notice that while we're between point 0 and 1, we simulate at time 1. Similarly, as illustrated in Figure 4, while we are between moments 1 and 2, we want the simulation of time 2. And so on.

At this point, you might be thinking that this is somewhat incorrect, right? Because this wouldn't produce a smooth movement, as we're treating many different times the same way. That is, the position (and velocities) of objects shouldn't be the same for every time value between 0 and 1. If we're on time 0.2 and then the game advances to time 0.5, you want the objects of the game to move a little bit. However, with what I've just told you up to now, objects wouldn't move until the time of the game advances past 1, at which point we would make another simulation.

This is when interpolation comes into play. The key of the approach is the following: we simulate the future and we interpolate proportionally to the distance to this future. Therefore, if we're on time 0.2, we're further away from the future than if we're on time 0.8. The closer to the future, the closer to the simulation. We can achieve this with a linear interpolation in which an alpha value determines how close we're to the future:

position = position * (1 - alpha) + futurePosition * alpha,    0 <= alpha <= 1

Without further ado, here's the C++/SFML code for the simulation:

 //Initialization (out of the loop)
 const auto dt = sf::seconds(0.01f);
 auto accumulator = sf::Time::Zero;
 auto lastTimeUpdated = 1;
 MotionSystem::SimulateFuture(dt.asSeconds(), futurePos, futureVel);

 //In game loop
 accumulator += elapsedTime;  
 double timesDt;  
 const auto fractionToNextFrame = modf(accumulator / dt, &timesDt);  
 if ((timesDt + 1) > lastTimeUpdated)  
 {  
    for (uint16_t i = lastTimeUpdated; i < timesDt + 1; ++i)  
    {  
       MotionSystem::SimulateFuture(dt.asSeconds(), futurePos, futureVel);  
    }  
    lastTimeUpdated = timesDt + 1;  
 }  
 MotionSystem::Interpolate(fractionToNextFrame, futurePos, futureVel);  

The accumulator variable holds the time that has passed since the game started. Then, by using the C++ function modf, we can extract how many times dt has passed and how close we are to the next frame.

Note that before entering the loop, we have made the first simulation, the one corresponding to the first point in time at which we want to simulate. That is, we have simulated the first point in the future and lastTimeUpdated is assigned this information.

Let's lay out an example: consider that the first time the loop executes, accumulator = 0.004. Being dt = 0.01, we're almost halfway between the present and the simulated future. Given that accumulator / dt = 0.4, after the execution of modf, the variable timesDt = 0, and fractionToNextFrame = 0.4. The if condition is not met, and therefore no simulation is performed. We interpolate the current position with the future position according to fractionToNextFrame when we call MotionSystem::Interpolate. Internally, this function does something like the following:

position = position * 0.6 + futurePosition * 0.4

Let's assume that in the following execution of the loop, accumulator = 0.018. Now, timesDt =  1 and fractionToNextFrame = 0.8. The if condition is now met (2 > 1) and in the for loop, we make one simulation of the future, reaching the second simulation point, and updating lastTimeUpdated = 2. Finally, we interpolate as follows:

position = position * 0.2 + futurePosition * 0.8

In case there's a frame drop or the rendering function (which would be executed after this simulation) takes too long, the simulation can catch up in a controlled way because it will be executed all the times it is required in a fixed timestep. You can work out the numbers yourself considering a sudden accumulator = 0.12.

Hope you liked this post. If you notice that something is missing or that I made any mistake, let me know so that I can fix it.

See you!

Breaking Fast on Steam Greenlight!

Hi buddies!

Breaking Fast is now on Steam Greenlight! I already wrote about this game several posts ago, but here's a quick summary: Breaking Fast is a 2D racing game in which the main characters are pieces of breakfast food, like a toast, a carton of milk or a strip of bacon. Following the lines of masterpieces of  fun like Mario Kart, Breaking Fast proposes frenetic races in delicious scenarios like a kitchen or a picnic. During these races, it's not only a matter of being faster: you also need to be smarter and stronger, because you have to avoid obstacles (all food-related) and the attacks from other players.

The game will come out by the end of 2016. We're working on lots of stuff: polishing animations, creating new scenarios and characters, and on an online mode. Also, we collected a good deal of feedback from users and developers at both Mallorca Game and Gamelab (more about them in future posts), and we'll try to incorporate the best ideas to enhance the gameplay experience.

By the way, we're also very proud that we won the 2nd prize in the Mallorca Game Awards! But as I just mentioned, I'll give more details about this in future posts. 

For now, in addition to upvoting it if you like it, you can watch the trailer we prepared for Steam.