Network games - "Do you remember how it all began? ..."

Under the cut - the translation of the first part of the article What every programmer needs to know about game networking , about the history of the formation and principles of the device multiplayer online games. Posted by Glenn Fiedler.

Introduction

You are a programmer. Have you ever thought about how multiplayer games work?

From the outside, it looks like magic: two or more players on the network take part in the same events that agree with each other, as if they exist in the same virtual reality. However, from the point of view of the programmer, it is clear that the essence of what is happening is not really what it may seem at first glance. It turns out this is an illusion. Large-scale deception, sleight of hand. What we perceive as a common reality is, in fact, only an approximation, unique for each individual player, his position in space, and points of observation.

Next, I will describe a number of tricks used by programmers in different genres of online games, as well as the history of their development.
')

Hard synchronization over peer-to-peer networks

At the dawn of their appearance, multiplayer games worked on the principle of peer-to-peer networks, where each computer exchanged data with other computers over a network with a star topology. Nowadays, this model can also be found in real-time strategy (RTS), and what is interesting, perhaps because it was the very first way that multiplayer games work, many people still think that all such games use it.

The idea of ​​the approach is to divide the game into a series of steps (iterations), at each of which the further game state is determined using a certain set of control commands. For example, “move a unit”, “attack a unit”, “build a building”. All that needs to be done in this case is to execute the same set of commands on all gaming machines, starting with some common game state for all.

Of course, this explanation sounds too simple and does not reveal a lot of subtle points, but clearly demonstrates the idea of ​​the work of modern RTS. More details about this can be found here: 1500 Archers on a 28.8: Network Programming .

The solution seems simple and elegant, but it has several limitations.

Firstly, it is extremely difficult to ensure the full determinism of the game; so that every move is played up equally on all machines. For example, the same unit on different machines can move along slightly different routes, while on one of them he will arrive at his destination in advance and “save the situation”, and on another machine he may be hopelessly late. Just like a butterfly, flapping wings causing a hurricane at the other end of the world, one slight deviation over time can lead to complete out of sync.

The next limitation is that in order to guarantee that the next move will be identically beaten on all the machines, it is necessary to wait until its simulation, until control commands are received from all gaming machines. This means that each player will play with a delay equal to the delay of the player with the slowest connection / machine. RTS games usually mask such delays, playing special sounds or playing some cosmetic animation. However, the actually required control commands can be obtained after the expiration of the delay interval.

The reason for the third limitation is the fact that the game sends only control messages that change the game state over the network. For all this to work, the initial state of the game must be the same for all players. This means that the players before the start of the game are connected and are in a special readiness mode ( in the smoking room ). Although from a technical point of view it is possible to organize the connection of players already during the game, usually the first option is more common, because It is rather difficult to ensure the capture and transfer of a completely deterministic initial state of a new player during the game.

Despite all these limitations, this model of work is well suited for RTS and is used in games such as Command And Conqurer , Age Of Empires , Starcraft . The reason is that the game state in these games usually includes information about a large number of objects (units), which is expensive to transfer over the network. Instead, control commands are sent that affect the evolution of this state.

Meanwhile, in other game genres, progress does not stand still. Consider the evolution of action games starting with Doom , Quake and Unreal .

Client / Server

In the era of dynamic action-games, the limitations of the previous approach became apparent in the Doom game, which worked well only on the local network, and terribly on the Internet:

Although it is possible to connect two machines on the Internet with a working Doom using a modem, the game will turn out to be slow, ranging from completely unplayable (for example, with a 14.4Kbps PPP connection) to hardly playable (for example, with a 28.8Kbps connection via SLIP with compression). Since these types of compounds have minimal practical application, this document will only consider direct connections ( faqs.org ).

Undoubtedly, the problem was that Doom was designed to work only over local networks and used the approach described above to organize communication between machines. At each step, player input (keystrokes, etc.) was transferred from his machine to other game nodes of the network, and before simulating the next step, each machine was required to receive input events from all other players. In other words, before moving or shooting, you had to wait until input events came from the player who was lagging. Just imagine how those guys, who wrote above, as it were, gritted their teeth, that “such types of compounds have minimal practical application” :).

To go beyond the LAN and not be limited to well-functioning local networks of universities and large companies, it was necessary to change the network communication model. This is exactly what John Carmack did in 1996, creating Quake using a client / server model instead of a peer-to-peer approach.

Now the game on each machine no longer executed the same game code, and was not communicated with other machines; instead, the players assumed the role of clients and exchanged data with only one computer, a server . The game no longer needed to be deterministic on all machines, since in fact, it existed only on the server. Each client machine turned into a kind of terminal , and displayed an approximate version of the game running on the server.

In a pure client / server model, the client does not execute any code responsible for the game logic, and only sends keystrokes, mouse movements, etc. to the server. In response, the server updates the status of this player and returns packets containing information about this state, as well as the status of the players around it. The client is only required to interpolate between the obtained state data in order to create the illusion of smooth motion. And here on an output we receive model client / server in the pure state.

It was a significant step forward. The quality of the game now depended on the connection speed between the client and the server, and not on the connection speed of the lagging player himself. It also became possible to connect new players in the middle of the game, and the total number of players increased, because decreased the average load on the channel in the calculation for each player.

But even then there were problems:

While I can remember and justify all my decisions used in the network model, starting with Doom and ending with Quake, the essence was always the same - the basic assumptions from which I proceeded when developing were good for a good Internet game. . Initially I was counting on connection delays of less than 200ms. People having a digital connection through a good provider did not experience difficulties in the game. Unfortunately, 99% of users are connected via a modem, and, as a rule, through a fucking overloaded provider. Because of this, delays become equal to at least 300ms. Customer. User modem. Server. Provider modem. User modem. Customer. This sucks.

Perhaps it was a rude expression. I have T1 at home, so I was new to PPP life. Now I will keep this in mind.

Of course, data transfer delays have become a problem.
What John did when he released QuakeWorld changed the gaming industry forever.

Client side prediction

In the original Quake, there was always a connection delay between the client and the server. Click "forward" and you will wait as long as you like until the packets reach the server and back, and then just start to move. Press "fire", and you will wait as much until the bullet takes off.

In modern games, such as shooters, this no longer happens. How do these games mask data transfer delays?

This problem has historically been solved in two rounds. First, John Carmack developed a client-side forecasting system for QuakeWorld, later refined and used in the Unreal game by Tim Sweeney. The second step was the delay compensation system developed by Valve for CounterStrike by Yahn Bernier from Valve. Let us dwell on the first of two parts - how to hide the delay between the arrival of input from the player and the response of the game.

John Carmack wrote in his plans for the upcoming QuakeWorld:

Now I let the client guess at the result of the player’s movement before the response from the server comes. This is a very big change in architecture. The client now has to distinguish between solid objects, know about physical characteristics, such as mass, friction, gravity, etc. I am sad to realize that the elegant client / server model is a thing of the past, but I’m more of a practitioner than an idealist.

Now the client has to execute more code than before. It is no longer just a terminal that sends player input to the server and interpolates the results of changes. Now he is able to assume player movement locally, immediately after input events have arrived .

After pressing the “forward” key, the movement will take place immediately, and you will not have to wait for the packets to travel from the client to the server, and back.

The complexity of this approach is not to predict the movement locally, based only on the user's input and the period of time allotted for the next iteration. The difficulty is to correctly make adjustments to the player’s movement if the client and the server disagree, at what point in space the player should be and what he should do.

Now you may be surprised. Hey, how is it? If the client controls the movement of the character, why not make him the main one in the process? The client could simply calculate the motion and send the necessary information to the server. The problem is that if each client could tell the server “my current position here,” it would not be difficult for the client to hack so that, for example, constantly dodge blows, or teleport behind other players, to shoot them from behind.

Thus, it is necessary that in such games the server has the highest priority when managing characters, despite the fact that each player locally can predict their movement to avoid delays. As Tim Sweeney writes in The Unreal Networking Architecture , “Server is the boss.”

This is where the fun begins. If the client and server calculations do not match, the client must make a server decision, but due to the delay, adjustments must be made to the point in time that has already passed for the client. For example, if the package goes from the client to the server 100ms, and the same amount of time goes back, then the character’s position should be corrected 200ms earlier than the moment before which the client had already predicted the movement.

If the client had made adjustments without any changes “as is,” he would have to roll back everything that he had calculated after that moment, and actually go back in time. How to get around this, at the same time allowing the client to continue forecasting further?

The solution is to use a circular buffer, which stores information about the player’s previous states and input events. When a client receives adjustments from the server, it discards all information that is older than the corrected time point, after which it re-recalculates the player’s state, starting from the adjusted one, ending with the last predicted one, while using the information about the input events that occurred in this period. In fact, the client quietly "rewinds and re-loses" the last n frames of the character's animation, while leaving the rest of the game world fixed.

With this approach, the player can control his character without delay, in addition, the simulation becomes completely deterministic - it gives the same result on the client and the server, and the need to make adjustments rarely appears. Tim Sweeney says this:

... the best of both options: in any case, the server remains central to the management process. Almost all the time the simulation of the player’s movement on the client exactly reflects what is happening on the server, therefore the player’s condition is rarely corrected. Only in some cases, for example, when a rocket hits the player, or he encounters an opponent, his position is changed by the server.

In other words, the position of the player is corrected only in the case when it is affected by some external factors that cannot be predicted locally. Of course, this is only if the player does not use cheats :)