Game cycles or ElectroCardioGama

The game cycle is the pulse of each game. No game will work without it. However, unfortunately for each new game developer, there are no good articles on the web that have paid enough attention to this topic. But do not be sad, because as soon as you got the opportunity to read a one-of-a-kind article that gives the issue of game cycles deserved attention. On duty, I often have to deal with a large number of code of small mobile games. And every time I wonder how many realizations of the game cycle there are. You too can wonder how for such a seemingly simple thing, you can come up with many implementations. But you can! And in the article I will try to talk about the advantages and disadvantages of the most popular options for game cycles. Also, I will try to describe the best in my opinion version of the implementation of the game cycle.
(Thanks to Kao Cardoso for Felix this article is also available in Brazilian Portuguese) (Thanks for me, in Russian also, approx. Transl.)

Game cycle

Each game contains a sequence of calls for reading user input, updating the game state, processing AI, playing music and sound effects, drawing graphics. This sequence of calls is performed within the game cycle. Ie, as it was said in the teaser, the game cycle is the pulse of each game. In the article I will not go into the details of the implementation of the tasks mentioned above, but will focus exclusively on the problem of the game cycle. For the same reason, I will simplify the list of tasks to two functions: status update and rendering. Below is a sample code for the most simple implementation of the game cycle.

bool game_is_running = true; while( game_is_running ) { update_game(); display_game(); } 

The problem with this implementation is that it does not handle time. The game is just running. On a weak gland, the game works slowly, on a strong one - quickly. Long ago, when computer performance was known and about the same on different machines, this implementation did not give rise to problems. Today, when there are many platforms with different performance, there is a need to handle time. This can be done in different ways. I will tell about them later. In the meantime, let me explain a couple of points that will continue to be used.

FPS
FPS is an abbreviation of “Frames Per Second” (Frames Per Second, approx. Transl.). In the context of the above implementation of the game cycle, this is the number of display_game () calls per second.
')
Game speed
Game speed is the number of game state updates per second. In other words, the number of calls to update_game () per second of time.

FPS depending on constant game speed

Implementation

The simplest solution to the timing problem is to simply make calls with a fixed frequency 25 times / sec. The code implementing this approach is below.

 const int FRAMES_PER_SECOND = 25; const int SKIP_TICKS = 1000 / FRAMES_PER_SECOND; DWORD next_game_tick = GetTickCount(); // GetTickCount() returns the current number of milliseconds // that have elapsed since the system was started int sleep_time = 0; bool game_is_running = true; while( game_is_running ) { update_game(); display_game(); next_game_tick += SKIP_TICKS; sleep_time = next_game_tick - GetTickCount(); if( sleep_time >= 0 ) { Sleep( sleep_time ); } else { // Shit, we are running behind! } } 

This is a realization with one big plus: SIMPLICITY! As soon as you know that update_game () is called 25 times per second, writing the rest of the code becomes easier for the fixed turnip. For example, implementing replay functionality becomes a trivial task. If the game does not use random variables, then you can simply log user input and play it back later. On your test machine, you can pick up a compromise value for FRAMES_PER_SECOND, but what happens on a faster or slower hardware? Let's find this out.

Weak iron

If the iron is able to withstand a given FPS, then there is no problem. Problems will appear when the machine can not keep FPS at a given level. The game will run slower. In the worst case, the game will lag some intervals, while others work fine. Time will flow at different speeds, which ultimately can make your game unplayable.

Productive iron

There will be no problems on powerful hardware, but the computer will be idle, wasting "precious" (apparently this is irony? - approx. Transl.) Processor time. Were ashamed to run the game from 25..30 FPS, when she could give out for over 300! Your game will lose in attractiveness compared to what it could show when using the processor to its fullest. On the other hand, on mobile platforms, it can be for the better - it will save energy.

Conclusion

Setting an FPS at a fixed game speed is a simple solution that allows you to keep the code simple. But there are problems: by setting too much importance for FPS, we will create problems on a weak iron; setting the value too low will inefficiently use powerful hardware.

Game speed dependent on variable FPS

Implementation

Another solution to the problem is to let the game run as fast as possible and make the game speed dependent on the current FPS. The game will be updated using the amount of time spent drawing the previous frame.

 DWORD prev_frame_tick; DWORD curr_frame_tick = GetTickCount(); bool game_is_running = true; while( game_is_running ) { prev_frame_tick = curr_frame_tick; curr_frame_tick = GetTickCount(); update_game( curr_frame_tick - prev_frame_tick ); display_game(); } 

The code is complicated because we must now handle the time delta in update_game (). But the code is slightly complicated. I have seen many clever developers who have implemented this approach. Surely some of them would like to be able to read this post before they implemented such a cycle on their own. Below, I will show why such an approach can have serious problems both on a weak gland and on a powerful one (yes ... and on a powerful one too).

Weak iron

Weak iron can sometimes cause delays in places where the game becomes “heavy”. This will definitely take place in 3D games when too many polygons are drawn. As a result, failure in FPS will slow down the processing of user input. Updating the game will respond to failures of the FPS, as a result, the state of the game will change with noticeable lags. As a result, the player’s reaction time, exactly like the AI, will slow down, which may make even a simple maneuver impossible. For example, an obstacle that can be overcome with a normal FPS will not be possible to overcome with a low FPS. Even more serious problems on weak gland will be when using physics. A physics simulation may explode .

Powerful iron

You may be surprised that the above implementation of the game cycle may not work correctly on fast hardware. Unfortunately it can. And before you show why, let me explain a few moments of mathematics on a computer. In view of the finite bitness of representing a floating-point number, some values ​​cannot be represented. Thus, a value of 0.1 cannot be represented in binary form and will be rounded when stored in a double variable. I'll demonstrate this using the python console:
>>> 0.1
0.10000000000000001
This in itself is not a bad thing, but in sequential calculations it leads to problems. Suppose you have a car, the speed of which is equal to 0.001 in parrots (free translation, approx. Transl.). After 10 seconds, the car will move to a distance of 10.0 parrots. If we divide this calculation into frames, we get the following function with FPS as a parameter:
>>> def get_distance( fps ):
... skip_ticks = 1000 / fps
... total_ticks = 0
... distance = 0.0
... speed_per_tick = 0.001
... while total_ticks < 10000:
... distance += speed_per_tick * skip_ticks
... total_ticks += skip_ticks
... return distance

And let's try to calculate the path for 40 FPS.
>>> get_distance( 40 )
10.000000000000075

Wait ka! This is not 10.0 parrots! What happened? Everything is simple ... Since we split the path calculation into 400 frames, then a significant error accumulated during the summation. Can you imagine what will happen at 100 FPS?
>>> get_distance( 100 )
9.9999999999998312

Wow! The error has become even more !!! This is because we make even more additions at 100 FPS. So the error accumulates more. Thus, the game will work differently with 40 FPS and 100 FPS.
>>> get_distance( 40 ) - get_distance( 100 )
2.4336088699783431e-13
You may think that such a difference is insignificant and can be neglected. However, if you use this value in any other calculations, then problems will arise more serious (as an example - the integration of diff. Ur-s, note trans.). Thus, the error can accumulate so large that it zakachapit (slightly censor than in the original, approx. Transl.) Your product on large FPS. You ask how likely it is? Probably enough to attract attention. I had the honor to contemplate the game with such a realization of the game cycle. And, indeed, it had problems with large FPS. After the developer realized that the “dog is buried” in the very core of the game code, it was necessary to refactor a ton of code to fix the bug.

Conclusion

At first glance, this type of game cycle seems very good, but only at first. Both weak and powerful iron can cause problems. In addition, the implementation of the state update function has become more complicated compared to the first implementation. So in her furnace?

Constant game speed and maximum FPS

Implementation

Our first implementation, "FPS, depending on the constant speed of the game," has problems on a weak gland. It generates lags for both FPS and game state updates. A possible solution to this problem is to perform a state update at a fixed frequency, but reduce the frequency of rendering. Below is the implementation code for this approach:

 const int TICKS_PER_SECOND = 50; const int SKIP_TICKS = 1000 / TICKS_PER_SECOND; const int MAX_FRAMESKIP = 10; DWORD next_game_tick = GetTickCount(); int loops; bool game_is_running = true; while( game_is_running ) { loops = 0; while( GetTickCount() > next_game_tick && loops < MAX_FRAMESKIP) { update_game(); next_game_tick += SKIP_TICKS; loops++; } display_game(); } 

The game will be updated with a fixed frequency 50 times per second, and the drawing will be performed with the maximum possible frequency. Note that if the drawing is performed more often than the update state, then some adjacent frames will be the same, so in reality the maximum FPS value will be limited by the frequency of updating the game state. On a weak gland, the FPS will decrease until the state update cycle reaches the value MAX_FRAMESKIP. In practice, this means that the game will really start to slow down only when the FPS drawing sags below the value 5 (= FRAMES_PER_SECOND / MAX_FRAMESKIP).

Weak iron

On a weak hardware, the FPS will drop, but the game itself will most likely work at normal speed. If the iron is not able to withstand even the minimum FPS, it will begin to slow down and update the state, and the drawing will lose even a hint of smooth animation.

Powerful iron

On a powerful hardware game will work without any problems, but as in the first implementation, the processor will be used inefficiently. Finding a balance between a quick upgrade and the ability to work on a weak gland is crucial.

Conclusion

Using fixed game speed and maximum possible FPS is a solution that is easy to implement and keeps the code simple. But still there are some problems: setting the state update rate too high will cause problems on the weak gland (though not as serious as in the case of the first implementation), and setting the state update rate low will inefficiently use the computing power (resources could be used for increase the smoothness of animations, but instead they are spent on frequent drawing).

Constant game speed independent of variable FPS

Implementation

Is it possible to improve the previous implementation so that it works faster on a weak gland and would be more attractive visually on a powerful one? Well, fortunately for us, yes, it is possible! The game state does not need to be updated 60 times per second. User input, AI, as well as updating the state of the game, enough to update 25 times per second (I do not agree with this, not always, approx. Transl.). So let's call update_game () 25 times per second, not more, not less. But let the drawing be done as often as the iron pulls. But slow rendering should not affect the frequency of updating the state. How to achieve this is shown in the following code.

 const int TICKS_PER_SECOND = 25; const int SKIP_TICKS = 1000 / TICKS_PER_SECOND; const int MAX_FRAMESKIP = 5; DWORD next_game_tick = GetTickCount(); int loops; float interpolation; bool game_is_running = true; while( game_is_running ) { loops = 0; while( GetTickCount() > next_game_tick && loops < MAX_FRAMESKIP) { update_game(); next_game_tick += SKIP_TICKS; loops++; } interpolation = float( GetTickCount() + SKIP_TICKS - next_game_tick ) / float( SKIP_TICKS ); display_game( interpolation ); } 

As a result, the implementation of update_game () will remain simple. However, unfortunately, the display_game () function becomes more complex. You will need to implement interpolation and prediction. But do not worry, it is not as difficult as it seems. Later, I'll tell you how interpolation and prediction work, but first let me show you why they are needed.

Why do you need interpolation

The game state is updated 25 times per second. Therefore, if interpolation is not used, then frames will be displayed with the same maximum frequency. Here it should be noted that 25 frames per second is not as slow as it might seem to someone. For example, in movies, frames are replaced with a frequency of 24 frames per second. So 25 frames per second seems sufficient, but not for fast moving objects. For such objects, you should increase the frequency of updating the state to get a smoother animation. An alternative to the increased refresh rate is precisely the combination of interpolation and prediction.
* Approx. trans .: in the NeoAxis engine for the physical object you can set the flag Continuous Collision Detection; I suspect that it is just that processing is performed, similar to the implementation of the game cycle described above.

Interpolation and prediction

As it was written above, the state is updated on its own, independent frequency. Therefore, it is possible that the drawing starts between two consecutive ticks. Suppose you have updated the status 10 times. Then the drawing is called and it runs somewhere between 10 and 11 ticks. Let it be discrete time 10.3. As a result, “interpolation” will have a value of 0.3. As an example, imagine a car moving as follows:
position = position + speed;
If at the 10th step of the status update cycle the position is 500, the speed will be 100, then at the 11th step the position will be 600. So what will be the position of the machine during the drawing? You can simply take a position in the last step, i.e. 500. But it is much better to predict the position in the next step and interpolate for time 10.3. Get the view code:
view_position = position + (speed * interpolation)
Thus, the machine will be drawn at position 530. The variable “interpolation” generally contains a value from 0 to 1 relative position in time between the current and next frames (redone for better understanding, approx. Transl.). There is no need to make predictions too complex to ensure smooth animation. Of course, a situation is possible when one object partially intersects with another immediately before the detection of a collision. But, as we saw earlier, the state of the game is updated 25 times per second, so the rendering artifact will be visible only a split second (and what if the density of objects is large and there are a lot of collisions? - approx. Transl.) And with little probability it will be noticed by the user.

Weak iron

In most cases, update_game () will run much faster than display_game (). In fact, we can take for granted that even on a weak gland, the update_game () function is called 25 times per second. Therefore, our game will handle user input and update state without any problems even in the case when the drawing is performed at a frequency of 15 frames per second.

Powerful iron

On powerful hardware, the game will still go at a fixed speed of 25 ticks per second, but rendering will be faster. Interpolation + prediction will add to the attractiveness of the animation, because in fact, rendering will be performed at a higher FPS. The beauty is that this way you cheat with FPS. You do not update the state of the game with great frequency, but only a picture. But at the same time your game will still have a high FPS.

Conclusion

Decoupling updates and rendering from each other seems like the best solution. However, it is necessary to implement interpolation and prediction in display_game (). True, this task is not too complicated (only when using primitive object mechanics, approx. Transl.).

Conclusion

The game loop is not such a simple thing as you might think. We considered 4 possible implementations. And among them there is at least one (where the state update is tightly tied to the FPS), which you should definitely avoid. A constant frame rate may be acceptable on mobile devices. However, if you want to port the game to different platforms, you will have to decouple the update frequency and drawing frequency, implement interpolation and prediction. If you do not want to bother with prediction and interpolation, then you can use a large frequency of updating the state, but finding its optimal value for a weak and powerful iron can be a difficult task.

Now march to code your <% place_your_game_title_here%>!

Associated articles (from translator)

1. habrahabr.ru/blogs/silverlight/125037 - Game cycle in SL
2. habrahabr.ru/blogs/gdev/112444 - there is mention of the fact that in Unity3D there is no game cycle as such (apparently it is hidden away?)
3. habrahabr.ru/blogs/gdev/102930 - about the creation of the game engine
4. habrahabr.ru/blogs/android_development/136968 - an example of playing coconut
5. gafferongames.com/game-physics/fix-your-timestep - another article about discrete time in games