Geekly Articles each Day
📜 ⬆️ ⬇️

State synchronization in multiplayer games

image

The problem of multiplayer games


One of the most difficult tasks of multiplayer games is to synchronize the states of all players with the state of the server. There are good articles on the Internet on this topic. However, they lack some details that can confuse newcomers to programming games. I hope that I can explain everything in this article.

I will designate several techniques commonly used to solve such problems. Before proceeding to the problem, let's briefly consider the principle of multiplayer games.
')
Usually a game program should simulate the following:

changes in the environment, taking into account the time and data entered by players .

A game is a program that stores a state, so it depends on time (real or logical). For example, PACMAN simulates an environment in which ghosts constantly move.

Multiplayer is no exception, but because of the interaction of players, its complexity is much higher.

Take, for example, the classic game "Snake":

Suppose we use a client-server architecture. Game logic works as follows:

  1. Reading the data entered by the player, changing the direction of movement of the snake. They can have one of the meanings: [←, ↑, →, ↓].
  2. Application of input data if available. This changes the direction of the snake.
  3. Move the snake to one unit of measurement space.
  4. Checking the presence of a collision of each of the snakes with the enemy / wall / body, then removing them from the game.
  5. Repeat the cycle.

This logic should be executed on the server at regular intervals. As shown below, each cycle is called a frame (frame) or a beat (tick) .

class Server { def main(): Unit = { while (true) { /** * 1.    ,    : [←, ↑, →, ↓]. * 2.     ,     . * 3.       . * 4.    //    ,    . * 5.      . */ Thread.sleep(100) } } }

The simplest client reads server updates and renders each received frame for the player.

 class Client { def onServerUpdate(state: GameState) = { renderGameState(state) } }


Fixed state update


Concept


To ensure synchronization of all clients, the easiest way is to ensure that the client sends updates to the server at fixed intervals. For example, take an interval of 30 milliseconds. The update contains user-entered data, which may also contain a value of no user-entered data .

After receiving input from all users , the server can proceed to the next cycle, taking into account this data.


The figure above shows the interaction of a single client with a server. I hope the problem is as obvious for you as it is for me: the client may be idle on the interval from T0 to T1 , waiting for the update to continue from the server. Depending on the quality of the network, the delay can vary from 50 to 500 ms, and modern players notice delays of more than 100 ms. Therefore, braking the user interface for 200 ms will be a huge problem for some games.

This is not the only complexity of the approach with a fixed interval.



The picture above is a bit more complicated; it demonstrates interaction with a server of several clients. You can see that client B has a slower network connection, so although A and B send input data to T0 to the server, the update from B reaches the server at T2 , and not at T1 . Therefore, the server continues to calculate only when it receives all the updates, that is, in T2 .

What does it mean?
The delay of the game is now equal to the delay of the “lagging” player.
It turns out that we punish all the players because one of them has a slow connection. Therefore, sooner or later all the players will leave your game ...

Not to mention the fact that there is a possibility of disconnecting the client B, which will block the actions of the server until the connection timeout expires.

Discussion


In addition to the two problems mentioned above, there are a few more:

  1. The client will not respond until it receives a status update from the server (which is terrible from the user's point of view).
  2. Responsiveness of the game depends on the most "lagging" players. Do you play DSL with a friend? Good luck!
  3. The connection will be very "talkative": customers need to regularly send useless data so that the server can confirm that it has all the necessary information to continue, and this is ineffective.

First, games of a certain type are immune from these problems, for example, most turn-based games use variations of this model, because the customer has to wait.

For slow games, a small delay is also acceptable. A good example is Farm Ville .

Another good example is chess , in which two players take turns and each turn lasts about 10 seconds.

  1. Users must wait for each other for 10 seconds. And they are waiting.
  2. Two players take turns in turn, so the delay of one does not affect the other.
  3. Each turn takes an average of 5 seconds (one request every 5 seconds is enough).

But what about fast games? For example, for all FPS because of such problems, the solution with fixed intervals is not suitable. In the rest of this article, we will learn how to solve these problems.


Customer forecasting


Let's first solve the player response problem. The game reacts after 500 ms after the player has pressed the button, because of which the game process collapses.

How to solve this problem?

Concept


Some readers already know the answer: instead of waiting for a server update, the client actually emulates the game by executing the game logic locally (that is, on the client’s machine).

Suppose to calculate the state of a game in Tn we need to know the state in Tn-1 and the data entered by the user in Tn-1 .



The idea is simple: let's make a fixed update rate, which in our example is equal to one unit of time .

The client sends the input to the server at T0 to emulate the game state at T1 , so the client can then render the game without waiting for a status update from the server, which will only be received at T3 .

This approach only works in the following conditions:

  1. Game state updates are deterministic, i.e. there is no chance or it is transparent, and the server with the client can play the same game states from the same input data.
  2. The client has all the information necessary to execute the game logic.
  3. Note: 1 this is not always true, but we can try to make them as similar as possible and ignore small differences, for example, floating-point calculations on different platforms, and use the same seed for a pseudo-random algorithm.

Point 2 is also not always true. I will explain:



In the picture above, client A is still trying to emulate the state of the game in T1 using information obtained in T0 , but client B has already sent input data to T0 that client A. does not know about.

This means that customer A's prediction about T1 will be wrong. Fortunately, since client A still receives the T1 status from the server, it has the ability to correct its error in T3 .

The client side needs to find out if the previous emulation was correct and how conflicts can be resolved.

Conflict resolution is usually called Reconcilation .

The implementation of the agreement depends on the specific conditions of use. I will show the simplest example in which we simply give up the prediction and replace it with the exact state received from the server.

  1. The client needs to store two buffers: one for forecasts, the other for input data. It can later be used to calculate forecasts. Remember that the state Tn is calculated from the state Tn-1 and the input data Tn-1 , which will first be empty.
  2. When a player presses an arrow key, the input is saved to the InputBuffer, and the client performs the prediction, which is then used for visualization. The forecast is saved in PredictionBuffer.


  3. At the time of receiving the State0 state from the server, it does not match the client’s Prediction0 forecast, so we can replace Prediction0 with State0 and recalculate Prediction1 taking into account Input0 and State0 .
  4. After negotiation, we can safely remove State0 and Input0 from the buffer. Only after that we can confirm that everything is correct.

Note: reconciliation has a flaw. If the server state and the client's forecast are too different, then rendering may cause visual errors. For example, if we predict that in T0 the enemy moves south, but in T3 we understand that he moved north, then we coordinate the data by simply using the state from the server. The enemy abruptly changes its direction in order to display the correct position.

There are ways to deal with this problem, but they will not be covered in this article.

Discussion


Client-side prediction techniques have a huge advantage: the client works with its own update rate (independent of the server update rate), so when the server “slows down”, this does not affect the frame rate on the client side.

But this is inevitably associated with a certain complexity:

  1. We need to handle more states and logic on the client (prediction buffer, state buffer, prediction logic).
  2. We need to decide how to resolve conflicts between the forecast and the real state on the server.

And we still have old problems!

  1. Visualization errors due to incorrect predictions.
  2. Frequent exchange of useless data.

Conclusion


In this part we have considered only two ways to implement a network connection in multiplayer games:

  1. Fixed state update
  2. Client side prediction

Each of them has its own set of compromises, and we still have not considered in more detail what is happening on the server side.

Interesting related articles



What is the role of the server?


Let's start by defining server actions. Typical server tasks:

a) Connecting point for players
In a multiplayer game, players need a common endpoint to communicate with each other. This is one of the roles of the server program. Even in the P2P communication model, there is a connecting point for exchanging network information for setting up a P2P connection.
b) Information processing
In many cases, the server executes the game simulation code, processes all data entered by players, and updates the game state. It is worth considering that this is not always the case: some modern games shift most of the processing to the client. In this article, I will assume that it is the server that is responsible for processing the game, that is, for example, for creating game bars.
c) A single source of the true state of the game
In many multiplayer games, the server program also has power over the state of the game. The main reason for this is protection against cheating. In addition, it is much easier to navigate when there is a single point for obtaining the correct state of the game.

Naive server implementation


Let's start the implementation of the server in the most straightforward way, and then improve it.

The core of the game server is a loop that performs a GameState update based on user input. This cycle is usually called TICK (tact) and is indicated as follows:

(STATE n , INPUT n ) => STATE n+1

A simplified snippet of server code might look like this:

 def onReceivedInput(i: UserInput) = { storeInputToBuffer(i) } while(!gameEnded) { val allUserInputs = readInputFromBuffer() currentState = step(currentState, allUserInputs) // .. (STATEn , INPUTn) => STATEn+1 sendStateToAllPlayers(currentState) }

Discussion


I hope the code snippet looks intuitive and straightforward for you: the server simply accepts input from the buffer and applies it in the following TICK function to get the new GameState state. Let's call this approach a greedy game loop , because it tries to process data as quickly as possible. This is normal, if you do not think about our imperfect Universe, in which sunlight reaches the Earth in eight minutes.

Here again, delay becomes important.

The fact that the server processes buffer input from each TICK means that GameState depends on network latency. The diagram below shows why this is becoming a problem.



The diagram shows two clients sending input to the server. We see two interesting facts.

  1. Requests take different time between different clients and server: 1 unit of time from client A to server, 1.5 units of time from client B to server.
  2. Requests take different time for one client: the first request took 1 unit of time, the second - 2 units of time.

In short, the delay is variable, even for the same connection.

A variable delay combined with a greedy game cycle leads to several problems. We will look at them below.

Client side prediction does not work


If we cannot predict the time at which the server will receive the input data (due to a delay), we cannot make predictions with high accuracy.

Low latency players take advantage


If the input data gets to the server faster, they will be processed faster, which creates an unfair advantage for players with fast networks. For example, if two players shoot each other at the same time, they will have to kill each other at the same time, but player B has a lower delay, so he kills player A before the team of player A is processed.
To smooth out a non-constant delay, there is a simple solution — the above-described update with a fixed step. The server does not continue the calculations until it receives input from all players. There are two advantages to this approach:

  1. No client side prediction required
  2. All players will have the same delay as the slowest player, eliminating the aforementioned advantage.

However, this approach does not work in fast active games due to low responsiveness.

In the next section we will talk about how to make the server side work in fast games.

Reconcile on server


To solve the problem of inaccurate client-side prediction, we need to make client-server interaction more predictable from the client's point of view. When a player presses a key on the client side, the client program needs to know when this input will be processed on the server side.

One possible way to do this is to allow the client to suggest when the input should apply . Thus, the client side will be able to accurately predict the time of their application. The term “offer” is used because the server can reject this offer if it is incorrect, for example, the player tries to cast a spell, although his mana has run out.

Input data should be applied almost immediately after data entry by the player, for example, T input + X , where X is the delay. The exact value depends on the game, for responsiveness a delay of less than 100 ms is usually required. Note that X can be zero. In this case, the data is applied immediately after user input.

Let's take X = 30 ms, which is approximately equal to one frame at 30 frames per second. To transfer data to the server requires 150 ms, then there is a high probability that when the input data reaches the server, the frame for input will already be skipped.



Look at the diagram: user A has pressed a key at T. This data should be processed in T + 30 ms , but the input data due to the delay is received by the server at T + 150 ms , which is already outside of T + 30 ms . We will deal with this problem in this section.

How does the server use input that should have happened in the past?

Concept


You probably remember that forecasting on the client side had the same problem with inaccurate forecasts due to lack of information about opponents. Incorrect predictions were later corrected by status updates from the server using reconciliation. The same technique can be used here. The only difference is that we fix GameState on the server based on data entered by customers.

All user input must have a time stamp. These tags are used to tell the server when to process them.


Note: on the first dashed line Time X on the client side, but Time Y on the server side. This is an interesting feature of multiplayer games (and many other distributed systems): since the client and server work independently, the time on the client and on the server is usually different. Our algorithm allows us to cope with this difference.

The diagram above shows the interaction between the same client and server.

  1. The client sends the input with a time stamp, telling the server that this data from client A should occur in Time X.
  2. The server receives a request in Time Y. Suppose that Time X is earlier than Time Y. When developing an algorithm, we must accept that Time Y is greater or less than Time X, this will provide us with greater flexibility.
  3. The red field is the moment of the reconciliation. The server must apply Input X to the last state of the game, so that input X seems to have occurred in Time X.
  4. Transmitted by the GameState server also contains a timestamp, which is necessary for the coordination of both the server side and the client side.

Details of coordination ( red field )


  1. The server must store

    • GameStateHistory - the history of the state of the GameState during the time frame P , for example, all GameState for the last second.
    • ProcessedUserInput - UserInput input data history processed per time frame P , for example, the same value as GameStateHistory time frame
    • UnprocessedUserInput - received but not yet processed UserInput, also in time frame P

  2. When the server receives input from a user, it must be inserted into UnprocessedUserInput .
  3. Then, in the next frame server

    1. Checks for input to UnprocessedUserInput that is older than the current frame.
    2. If they are not there, then everything is in order, the game logic is simply executed with the latest GameState and the corresponding input data (if available), and broadcast to customers.
    3. If they are, then this means that some of the previously generated game states are erroneous due to missing information, and we need to fix this.
    4. First we need to find the oldest raw input, for example, during Time N, (hint: this operation is performed quickly if UnprocessedUserInput is sorted).
    5. Then we need to get the corresponding GameState state in Time N from the GameStateHistory and the processed input data in Time N from ProcessedUserInput
    6. With these three pieces of data, we can create a new, more accurate Game State.
    7. Then we move the raw input data Unprocessed Input N to ProcessedUserInput so that it can be used in the future for reconciliation.
    8. Update GameState N in GameStateHistory
    9. Repeat steps 4 through 7 for N+1, N+2 ... until we get the latest GameState.
    10. The server sends its last frame to all players.

Discussion


Server side negotiation suffers from the same problems as client negotiation. When coordination is needed, it means that we did something wrong, and we correct the mistake by changing the story. This means that we cannot apply irreversible consequences, such as killing players. Such irreversible effects can only be applied when they come from a GameStateHistory , i.e. when they can no longer be overwritten.

In addition, incorrect GameState sometimes lead to terrible UI jumps.The diagram below shows how this happens.



The object is first located in the upper left corner and moves to the right. After five such he moves to the right, but then the server receives user input, indicating that the object has changed direction in Tick N, so the server coordinates the state of the game. In this case, the object suddenly jumps to the lower left corner of the screen.

Perhaps I exaggerate this influence, sometimes the object moves not so far and the jump is less noticeable, but in many cases it is still obvious. We can control jumps by changing the size of the GameStateHistory , UnprocessedUserInput and ProcessedUserInput. The smaller the buffer size, the smaller the jumps will be, because we will be less tolerant of heavily delayed input data. For example, if the entered data is delayed by more than 100 ms, then they are ignored, and a player with a ping for> 200 ms will not be able to play the game.

We can sacrifice tolerance to network delays for more accurate updating of the game state , or vice versa.

There is one popular technique for dealing with the problem of inaccurate Game State - this is Interpolation of objects ( Entity Interpolation ). The idea is to smooth out the jumps by stretching them for short periods of time.


In this article I will not describe the details of the implementation of interpolation of objects , however, I will provide useful links at the end.

Summarize


We discussed how clients and servers work in multiplayer games.


In general, a multiplayer game contains three freely connectable cycles: a server game cycle , a client prediction cycle, and a client UI rendering cycle . By creating a buffer between them, you can divide the process of their execution, which gives us flexibility in creating a better gameplay.

Conclusion


This ends my article on multiplayer games. I learned a lot about the topic from specialists in this field; an example of a simple multiplayer game also helped me a lot . I showed only one way to implement a multi-user server, there are others. Choosing the right one depends on the type of game you are creating. I recommend that you explore some of the approaches by creating a simple game.

Thanks for reading, successful hacking!

Links and additional reading


Source: https://habr.com/ru/post/328702/

More articles:


All Articles