Survived . Recently, the problem of synchronizing gameplay with real time was discovered not just anywhere, but in the game "Quake Champions" . The name of the game "Quake" used to be synonymous with something cool, high-tech and perfect. And it never occurred to me that in a couple of decades and there would be no stone left from the former superiority, and in the new game with the name "Quake" gross errors will appear, leading to the fact that one of the players can get an advantage only because he has better iron. The fact is that the speed of shooting in a new shooter depends on fps, that is, the number of bullets fired by players with different fps values ​​for the same period of time will be different, which means one of them can gain an advantage.

This article is recommended to read to all game developers, and in particular to developers of programs for moving mechanisms. Yes, there were similar problems in the library code for working with stepper motors for Arduino . But if you create programs to control the flight of missiles, or for nuclear reactors, then guys, this article will not help you. You need other levels of synchronicity, and special hardware running RTOS.

Introduction

Anyone who has ever developed an application containing an animation (whether it be a game, visualization of physical processes, or just an animation of a user interface) has encountered the problem of synchronizing processes with real time. The speed of the application can never be constant even for the same computer, not to mention computers with different parameters of the processor, RAM and hard disk.

When solving this problem, a problem arises (and not very trivial, as it may seem at first glance), which is usually called “timer synchronization”, “linking to timer”, “linking to real time”. The essence of this task is to make the animation and other events in the program tied to real time and not depend on computer performance.

I hope you all played some kind of dynamic network shooter, like Quake or Half-Life, and you know how fast events happen there, how important a player’s quick reaction and accuracy of his actions are. In order for a player to play comfortably, the game must show maximum performance, the delay in delivery of network packets is minimal, the keyboard and mouse must be comfortable (and usually fabulously expensive). But even with the satisfaction of all these conditions, a game written without taking into account the nuances of the model of temporary processes of program execution can deliver a lot of unpleasant moments. In general, time synchronization is fatal in very fast dynamic games, but sometimes spoils the mood in other areas that are completely unrelated to games.

The difference of "natural" time from time "computer".

Even physicists have not yet come to a common understanding of what time is. But for ordinary people, in observable reality, where space-time is not too distorted, it seems that time flows continuously, and events occur in parallel. It seems that the objects are actually where we see them, and our everyday experience constantly confirms this. Time in programs looks very different than in observable reality. Forgetting about this, it is difficult to correctly model the behavior of objects in time. Let's understand the properties of "computer" time.

Discreteness (Quantization)

The effects of the flow of time are created through animation - creating a sequence of static pictures (frames), which, with a quick change, create the illusion of movement. Due to the inertia of vision and perception, the brain is forced to complete the missing elements of the movement, so when playing a sequence of little different frames, it seems to us that the movement occurs smoothly. The division of the time process into frames gives computer time the property of discreteness - that is, objects in the path of their movement can occupy only a certain finite number of positions, in the case of "natural" time, it seems that objects in their path occupy an incalculable number of positions.

Heterogeneity

At one moment of “natural” time, the processor core performs only one operation. This gives the "computer" time the property that distinguishes it from the "natural" time - this is the property of the heterogeneity of its flow. That is, for all of our game objects, time does not flow at the same time.

Suppose we have two objects, the state of each object depends on the state of the other. The state will be calculated for objects sequentially, which means that the first object will calculate its state based on the previous state of another object (irrelevant), and the second object will calculate its state based on the state of the first object (actual, but not correct, t. to. it was calculated from the irrelevant state of the second object). A vicious circle of errors is formed due to the fact that objects are processed sequentially, because the “computer” time is not uniform.

High performance timer

To measure time intervals in programs, it is advisable to use functions that provide relatively high accuracy. In Windows, QueryPerfomanceCounter is used, in Linux gettimeofday. Accuracy can differ on different processors, but they almost always give accuracy better than 1 millisecond.

Typical main loop

float dt = 0.0f; while (is_run) { if (active == false) WaitMessage(); timer.start(); doUpdate(dt); doRender(); dt = timer.elapsed(); } 

Types of sync

I distinguish between two ways to synchronize time, each has its own advantages and disadvantages.

Integration

The first method is called "integration". It differs in that the update of the state of objects is called strictly every frame, while we need to measure the time spent on building the frame and use this time to build the next one. For example, we need the value of a variable to increase by one per second. For this we can do the following:

 void onUpdate(float dt) { value += dt; } 

This is an example of the simplest integration.

There are many numerical integration algorithms, the most famous are the Euler method and the Runge-Kutta methods. The Euler method is the simplest method for solving differential equations, but is not suitable for solving complex equations, since it gives unsatisfactory accuracy. The Euler method is the fastest method and is well suited for use in game development. Runge-Kutta methods are used to solve complex systems of differential equations, and are used where high accuracy is needed.

Suppose we have a standard task: it is necessary to calculate the movement of the body under the action of force. The integration will look like this:

 vec3 pos; vec3 velocity; vec3 force; void onUpdate(float dt) { pos += velocity * dt + (force * dt * dt) / 2; velocity += force * dt; } 

Here we see the well-known school formula:

 S = v0*t + (a * t^2) / 2 

An important note is that if we change the order of integration of speed and position, we get the wrong result.

Now let's talk about the disadvantages of this method. The fact is that the formula for integration is not always as simple as it might seem. I can cite as an example the game STALKER, in which I could not normally play on my weak computer - but not because fps was very unacceptable, but just because the developers used something to smooth the rotation of the camera like this:

 vec3 camera_angles; void onUpdate(float dt) { vec3 new_camera_angles = input.getMouseDelta(); float k = 0.5f; // k = 0.0f..1.0f camera_angles = new_camera_angles * k + camera_angles * (1.0f - k); } 

Because of this, the camera was too inert at low fps values. It would seem that simple and obvious smoothing, but incorrectly implemented, it creates discomfort for the player at low fps values, not allowing him to enjoy all the delights of the exclusion zone. As a result, I never played in STALKER.

Fixed time step

This method is based on the fact that we update the state of objects given a constant number of times per second, thereby fixing the time step. The undeniable advantage of this method is that we no longer need to integrate - the formulas become simple and predictable. We simply make it so that the onUpdate () function is called, say, 60 times per second, and we forget about the constant need to integrate all state change processes. Undoubtedly, this method makes life much easier, especially when the game contains network interactions.

I would advise using this method to those who are not too willing to delve into the problems of proper time control and integration, but still this method does not completely solve the problems of time heterogeneity. For online games, this is probably the only option when all processes on different computers will occur more or less synchronously.

Naturally, the method also contains pitfalls:

• Updating the logic is no longer associated with frames, so the movements may not look as smooth as when integrated. It does not make sense to show the player more frames per second than the refresh rate of the logic. Therefore, it is better to make the refresh rate of the logic equal to the frame scan frequency - say, 60, 85, or 120. If the game is too dynamic, it is better to make 120, many modern game monitors can show so many frames.
• There is a problem that I call the “temporary collapse”, or you can call it “the black hole of time”. The problem arises when the execution time of the onUpdate () function is quite large (suppose all the physics are calculated there, and a huge number of objects have been added). At the same time, the onUpdate () game loop begins to be called more and more times, and the program just hangs. We spend a lot of time on onUpdate (), which means we need to compensate for the past time with two onUpdate (), two onUpdate () are already four onUpdate () in the next cycle - and so on. Therefore, it is necessary to control the rendering time of logic, and if it is too large, it is necessary to limit it. Naturally, after this, no synchronicity can be expected, but this will save from a hang. In this case, the user can be informed that his computer cannot cope with the calculations, and offer to purchase a faster computer :)

Periodic events

Let us turn to more specific examples. Periodic event I call an event that occurs after a fixed time interval. An example of such an event is the implementation of an onUpdate () call with a specified frequency when implementing a fixed time step.

 void onUpdate() { } float freq = 10.0f; float time_to_event = 0.0f; void doUpdate(float dt) { float ifreq = 1 / freq; time_to_event -= dt; while (time_to_event <= 0.0f) { event(); time_to_event += ifreq; } } 

In this example, the onUpdate () event will be triggered at a freq rate once per second. We see that if the ifreq is less than dt (that is, the specified calling frequency is greater than fps — the calling frequency of doUpdate ()), then onUpdate () will be called several times within the same doUpdate (). It seems to be all right, but what if you imagine that onUpdate () creates an object that also has a state variable in time?

Let's imagine that we have a shot event from an automaton that should be processed inside onUpdate, just like any game logic. If two shots happen within one onUpdate (), the bullets will simply be created at one point and will fly parallel alongside, although in fact they are separated by a time period of ifreq, for which one bullet flew farther than the other.

Let's see how to avoid this:

 class Bullet { void update(float dt) { } }; float fire_rate = 10.0f; float time_to_shoot = 0.0f; vector <Bullet *> bullets; void onUpdate(float dt) { for (int i=0; i<bullets.size(); i++) { bullets[i]->update(dt); } float ifire = 1 / freq; time_to_shoot -= dt; while (time_to_shoot <= 0.0f) { Bullet *bullet = new Bullet(); bullet->update(-time_to_shoot); bullets.push_back(bullet); time_to_shoot += ifreq; } } 

In this example, we will compensate the pool for the time that has passed from the moment it was launched to the next onUpdate () call, where Bullet :: update () will be called in the normal manner.

And what will happen if the player moves when shooting, or the direction of the shot will change? This also needs to be taken into account:

 class Bullet { void update(float dt) { … } void setTransform(const Transform &tf) { … } }; float fire_rate = 10.0f; float time_to_shoot = 0.0f; vector <Bullet *> bullets; Transform old_tf; bool first_update = true; void onUpdate(float dt) { for (int i=0; i<bullets.size(); i++) { bullets[i]->update(dt); } Transform tf = getBarrelTransform(); if (first_update) { old_tf = tf; first_update = false; } float ifire = 1 / freq; float k = time_to_shoot / dt; float delta_k = ifire / dt; time_to_shoot -= dt; while (time_to_shoot <= 0.0f) { float k = 1.0f - (-time_to_shoot / dt); Bullet *bullet = new Bullet(); bullet->setTransform(lerp(old_tf, tf, k)); bullet->update(-time_to_shoot); bullets.push_back(bullet); time_to_shoot += ifreq; } old_tf = tf; } 

In this case, we still made a small assumption. The fact is that the law of motion of the barrel of a weapon may be non-linear, but we linearly interpolate the transformation, approximately estimating the position of the barrel within the time range of dt. Of course, it is possible to absolutely exactly find the required position, but this will complicate the code even more.

In fact, if you go deeper into this topic, it becomes clear that the more accurately we want to handle temporary events, the more difficult the program will be. It would seem that the simple and obvious code of a periodic event became much more complicated when we began to take into account the properties of the “program” time. Therefore, in some cases it is necessary to put up with the fact that not everything is as correct as it would be in the ideal case. But it is also impossible not to take into account the properties of “computer time”, especially in very dynamic network games, where I would like to get the maximum response from management, and to achieve maximum synchronization between the clients and the server.