How do multiplayer games sync their state? Part 1
The problem with multiplayer games
In multiplayer games, one of the most complex issues is to keep all player’s state in sync with the server state. There are a few good articles around this topic on the internet. However, some details are missing here and there, which may be confusing for beginners in the field of game programming. I hope I can clear things up in this article.
I’ll present a few techniques commonly used in this problem space.
Before we jump into the problem, let’s have an overview on how multiplayer game generally works.
Typically, a game’s program needs to simulate the following:
the changes in an environment with respect of time and players input
Game is stateful program, so it depends on time (be it real or logical time). For example, PACMAN is simulating an environment where ghosts will continuously move around.
A multiplayer game is no exception, however the complexity is higher due to the interaction between multipler players.
Let’s use the classic Snake Game as an example:
Assume we use a server-client settings. The core game logic works like this
- Read user inputs which can be one of [←, ↑, →, ↓], to change the direction of the snake.
- Apply user input if any; this changes the direction of the snake.
- Move the snake by 1 unit space
- Check if any snakes bump into the enemy/wall/self, then proceed to remove them from the game.
- Repeat!
This logic will be ran at a fixed interval on the server side. As demonstrated below, each loop is a called a frame or a tick
The most simple client will listen to the server update and render every frame received to player.
Lockstep State Update
The Concept
To make sure all clients are in sync, the simplest way is to let client send update to server in a fixed interval, and for the purpose of explaining this to you in a way that makes sense, let’s say make that every 30ms. The update would contains user input, which can also represent no user input.
Once the server gathers input from ‘all user’ it can then proceed with next tick using those inputs.
The image above demonstrates how one client interacts with the server. I hope this problem is obvious to you as it is to me, as the client will remain idle from T0 to T1, waiting for server update to proceed. The latency can range from 50ms to 500ms, depending on network quality, and human’s in today’s day and age will notice any delay over 100ms, so freezing the user interface for 200ms can be a big problem for some games.
This is not the only issue with the lockstep approach.
This image is slightly more complicated, showing multi-client interaction with server. You can see that client B has a slower network connection, and although both A and B send input to the server at T0, the update from B reaches the server at T2 instead of T1, so the server only proceeds once it has receiveed all of the updates which is T2.
What does this mean?
the latency of the game is now the latency of the most lagged player
We’re punishing all players because one of them is lagging. So eventually all players will leave your game ….
Now, this isn’t to say that there’s a possiblity that client B might be disconnected, thus blocking the server until the connection timeout.
Discussion
There are some problems including 2 of which we just mentioned :
- Client will not be responding until it has received a state update from the server (horrible user experience).
- Game responsiveness depends on the most lagged players. Playing with a friend with DSL connection? Have Fun!
- The connection would be really chatty: clients need to send some useless heartbeat data regularly so that server can confirm it has all of the information needed to step forward, which is not efficient.
First of all, certain kind of games are immune to these problems, most Turn-based game actually use some variant of such model, as client are supposed to wait.
For slow-paced game, small amount of delay is acceptable too. Farm Ville makes for a good example.
Another great example is Chess, where 2 players take their own turn, assuming each turn takes 10 secs
- Users are expected to wait for each other for 10 secs. They wait.
- 2 players take turns alternatively, so one lagged player does not affect the other player
- Each turn takes on average 5 secs (1 request every 5 secs is fine).
But for fast-paced games? Like all FPS, all of these problems make lockstep approaches not suitable for them. We will see how we can solve these problems in the rest of articles.
Client Predictions
Let’s first solve the problem of user-responsiveness. The Game responds after 500 millis after a user presses a key, destroying the gaming experience.
How to solve this problem?
The Concept
Some of you might have already have the answer; instead of waiting on a server update, the client can actually emulate the game by running game logic locally (ie. on the client’s machine).
Let’s assume to produce game state at Tn, we need state at Tn-1 and all user input at Tn-1.
The idea is simple; let’s have a fixed update rate, which in this example is 1 unit of time
The client sends input to the server at T0 to emulate the game state at T1, so the client can then render the game without having to wait for the state update from the server, which only arrives at T3.
This approach only works if the following takes place:
- The game state updates logic are deterministic, ie. no randomness, or in some way, referentially transparent, so that the server and the client produce the same game state given the same input.
- The client has all of the information required to run gaming logic
- Note: 1 is not always true, but we can try to make it as similar as possible, and ignore the small differences, ie. floating points computation of different platform, use the same seed for pseudo-random algorithm.
2 is also not always true. I’ll explain…
In the image above, Client A still tries to emulate the game state at T1 using the information it has from T0, but Client B has also submitted input at T0, which Client A is not aware of.
This means that client A’s prediction of T1 will be wrong. Luckily, since Client A still receives the state of T1 from server, the client has the chance to correct it’s mistake at T3.
Client’s side needs to figure out if the previous emulation is correct, and how to resolve the conflicts.
The resolution of conflicts is normally called Reconcilation.
Implementation of Reconcilation varies depending on use case, I’ll show a simple one, which we just throw away our prediction and replace it with the correct state from server.
- The client needs to maintain 2 buffers; one for predictions and one for user input. This can then be used to compute predictions. Remember, State Tn is computed using State Tn-1 and Input Tn-1 which will be empty at first.
- When the player presses an arrow key, the input in stored in the InputBuffer, and the client will also produce predictions, which is then used to render the view. The prediction is stored in PredictionBuffer.
- When the server State0 is received and doesn’t match with the client’s Prediction0, we can replace Prediction0 with State0, and recompute Prediction1 using Input0 and State0.
- After reconcilation, we can safely removed State0 and Input0 from the buffer. Only then can we confirm it’s correct.
Note: this reconcilaton comes with a drawback. There might be glitches in view if the server state and the client prediction differ too much. For example, if we predict enemy is moving south on T0, but at T3 we realize it’s move towards the north, and then reconcile by simply using state from server. The enemy will bounce from ‘towards north’ to reflect it’s correct position.
There are ways to handle this problem, but it will not be in this article. Stay tuned!
Discussion
Client prediction techniques offer huge benefit:
The client runs on it’s own update rate (independent to the server update rate), so if that server is having hiccups, it does not affect client side frame rate.
This inevitably comes with some complexity :
- We need to handle more state and logic on the client side, (Prediction buffer, state buffer, prediction logic).
- We need to decide how to handle conflict between prediction and real state from server.
And it still leave us with these problems!
- View glitches due to wrong predictions
- Chatty connection
The Conclusion
In this article, we went through only 2 ways of approaching multiplayer game networking:
- Lockstep state update
- Client prediction
Each comes with it’s own set of trade off, and so far we havent get a closer look on the server side, which will be covered in the next article.
Thanks for reading !
Update: Part 2 is published
How multiplayer game works on server side?
Related articles
- Fast paced multiplayer game series by Gabriel
http://www.gabrielgambetta.com/fpm1.html - Game networking basics from gafferongames
http://gafferongames.com/networking-for-game-programmers/what-every-programmer-needs-to-know-about-game-networking/ - Article from valve
https://developer.valvesoftware.com/wiki/Source_Multiplayer_Networking
