1. Parts I, II (single player with authoritarian server)
2. Part III (The appearance of the enemy)
3. Part IV (Headshot!)

I bring to your attention the translation of the article Fast-Paced Multiplayer (Part I): Introduction .
')
Developing a game is not an easy task in itself. But multiplayer games create completely new problems that need resolution. It's funny that our problems have only two reasons: human nature and the laws of physics. The laws of physics will introduce problems from the field of the theory of relativity, and human nature will not allow us to trust the messages from the client.

If you are already familiar with the basic ideas behind multiplayer games, feel free to skip the first part and go on to the second.

Part I

Cheating problem

All our headaches begin with cheating.

If you develop a single game, you do not care if the user decides to cheat - his actions only affect him. Yes, the player may not get the experience you wanted to give him, but in the end he bought the game and can use it as he pleases.

But in multiplayer games, everything is completely different. In any competitive game, cheater does not just simplify the game for itself, but also worsens someone else's gaming experience. You, as a developer, should discourage this, as cheaters drive away players from your game.

There are many things you can do to prevent cheating. But the most important principle (and probably the deepest) is very simple: do not trust the player . Always expect the worst - that the player will try to deceive you.

Authoritarian server and naive client

This principle leads us to a simple, at first glance, solution - all game logic spins on the main server, under your control, and the client only demonstrates the current state of the server and sends commands to it (keystrokes, etc.). This is usually called an authoritarian server , because it is the only one who can model the world.

Of course, the server can be hacked, but this topic is beyond the scope of this series of articles. However, the use of an authoritarian server prevents a wide range of cheats. For example, you cannot trust a client with a player’s life level. A hacked client can change local information and report that a player has 100,000% of lives, but the server knows that only 10% of lives and if a player is attacked, he will die, regardless of what the client thinks about it.

It is also impossible to believe a player when he reports his position in the world. If you trust, a hacked client can tell the server:

- I'm on (10, 10)
A second later:

- I'm on (20, 10)

At the same time, perhaps he “passed” through the wall or moves faster than he should be.

But the correct paradigm. The server knows that the player is in position (10, 10); the client says, "I want to move one unit to the right." The server updates the player’s position on (11, 10), performing all necessary checks, and then replies to the player: “You are on (11, 10)”:





To summarize: the game state is controlled only by the server. Clients send their actions to the server, and the server periodically updates its status and sends it to clients, which, in turn, display it to users.

We deal with networks

A naive client is great for slow turn-based games - strategies or poker. It also works well for a local connection, where information is transmitted almost instantly. But it is absolutely unsuitable for fast games on the Internet.

Let's talk about physics. Suppose you are in San Francisco and are connecting to a server in New York. This is approximately 4,000 kilometers. Since nothing can move faster than the speed of light, at best, the signal will come in 13 milliseconds. But it is highly unlikely that you will have such a good connection. In the real world, information does not go straight, and not at the speed of light.
So let's assume it takes 50 ms. And this is practically the best scenario. What if you connect to a server in Tokyo? And what if the communication line is overloaded? In such cases, the delay reaches half a second.

Let's return to our example. Let the customer send a message:

- I clicked on the right arrow.

The server receives the request after 50 ms and immediately sends back the updated state.

- You are on (11, 10)

This message will reach the user after another 50 ms.

From the player’s point of view, he clicked on the arrow, then nothing happened for 0.1 seconds, and then the character finally moved one point to the right. This lag between the team and its result may seem insignificant, but it is noticeable. And, of course, a lag of half a second would not only be noticeable, but would make the game absolutely unplayable.

Summarizing

Online games are incredibly fun, but they bring a whole new class of problems and obstacles. The authoritarian architecture is good against cheaters, but a naive implementation will make the game responsive for users.

In the future, we explore the possibility of creating a system based on an authoritarian server, but with minimal delays for the players, making them indistinguishable from singles.

---

Part II

Introduction

In the first part, we looked at a client-server model with an authoritarian server and a naive client, which sends commands to the server and displays the updated state that came in the response.
The naive implementation of this concept leads to a noticeable delay between the team and the reaction. For example, if a player presses the left arrow, the character will begin to move in half a second. This happens because the command should go to the server, and the result of the command after that should go to the client.



On the Internet, where delays can be a few tenths of a second, the gameplay will be non-responsive at best, and unplayable at worst. In this part we will find ways to reduce this problem or get rid of it altogether.

Client side prediction

Despite the fact that some players try to cheat, most of the time the server receives valid requests. This means that the input received will be correct and the game will be updated as expected. That is, if a character is on (10, 10) and sends a command to move to the right, he will be on (11, 10).

We can use this if the game is sufficiently deterministic (that is, the result is determined by the teams and the previous state).

Suppose that we have a lag of 100 ms and the time of movement of the character is 100 ms. When using a naive implementation, the duration is 200 ms.



Assuming that the teams will be executed, the client can predict the state of the game world and often the prediction will be correct, since the game world is deterministic.

So instead of sending a command and waiting until a new game state comes in to render it, we can send a command and start rendering the result as if the team had already been completed. And, of course, we must wait for the result from the server - the “real” state of the game, which for the most part will coincide with the local state.



Now we have absolutely no delay between the player’s action and the result on the screen, and the server is still authoritarian (if the hacked client starts sending incorrect commands, it can render anything on the screen, but it doesn’t affect the state of the game on the server that they see other players).

Sync issues

In the previous example, I carefully picked up the numbers so that everything worked fine. Let's change the script a bit. The lag will be 250 ms, and the animation of movement by one unit will last 100 ms. And let the player quickly double-click on the arrow to the right.

When using the current approach, this is what will happen:



We faced an interesting problem at t = 250 ms, when a new state came to us. The client predicted x = 12, but the server says that x = 11. Since the server is authoritarian, the client must move the character back to x = 11. But later, at t = 350, the server says that x = 12, so the character jumps again, but this time ahead.

From the player’s point of view, he pressed the right arrow twice, so the character moved two units to the right, stood there 50 ms, jumped one left, stood there 100 ms and jumped one to the right. Of course, this is completely unacceptable.

Reconcile with server

The key to solving this problem lies in understanding that the client sees the gaming world in the present tense , but because of the lag updates from the server come about the state of the world in the past . By the time the server sent us updates, it had not yet received some of our commands.

But to get around this problem is not so difficult. Let's add to each request from the client his number. And when the server responds, it will add the number of the last processed request. And let's keep on the client a copy of all commands sent to the server.



So, at t = 250, the client receives “x = 11, the last command is # 1”. The client deletes all commands up to # 1 inclusive, but leaves a copy of # 2 that the server does not yet know about. It applies the status received from the server (x = 11) and then applies the input that is not yet visible to the server. In this case, # 2 is "right by 1 unit." The end result is x = 12, which is true.

Further, at t = 350, a new state comes from the server: “x = 12, the last command # 2”. The client deletes all copies of commands up to # 2, inclusive, and then applies the state x = 12 (nothing has changed). Since there are no more unprocessed commands, this is the end, with the correct result.

Results

We have analyzed the example of motion, but the same principle applies to almost everything. For example, when attacking an enemy character, you can immediately show the blood and the number that reflects the damage done.

But you should not actually update the life of the character until the server sends an updated state.

Due to the complexities of the game state, which is not always easy to roll back, it is probably not worth killing a character even if his level of life has dropped below zero. What if another player recovered right before your attack, but the server has not yet reported this?

Note trans. I would kill the character immediately, but ensured the persistence (the ability to roll back states). So it will be easier to write portable code that runs on both the server and the client. In any case, as you will see later, this will have to be done.

This all leads us to an interesting conclusion - even if the world is absolutely deterministic and there are no cheating players, it’s still possible that the state predicted by the client and the state sent from the server do not match. Although this is not possible for a single player, it is very easy to reproduce such a problem with several players playing simultaneously. This will be the topic of the next article.

Summarizing

When using an authoritarian server, you must give the player the illusion of responsiveness, although in reality you are waiting for the server to actually process the input. For this, the client simulates the result of all commands. When an update comes from the server, the status is updated based on the current state of the server and the commands it has not processed.