Welcome to a brand new series where we will discuss through various video game mechanics, how game developers make them work and what are some challenges along the way. I have been planning this for almost 6 months now but too lazy to start writing. Enjoy!
Before we start, this post and the series as a whole assume that you have university-level knowledge of various computer science subjects, mathematics and physics too. I will try to explain things as simply as possible but if you are unfamiliar with these subjects, it may not be easy to get a grasp on the topics since the sole purpose of the series is to explain the technical background of how games work.
Without further ado, let us begin…
As the name indicates, we will be talking about online multiplayer games. The FPS number of the game indicates how many scenes will be rendered in a second. It is easy to render a scene for a single-player game — well, not actually easy but you understand what I mean — but a multiplayer game will raise some extra concerns.
In a single-player game, the rendered scene will only depend on your actions. Unlike a single-player game, a multiplayer game uses the information of other players in addition to yours in the rendering process. This puts networking into the equation, a way to share and synchronize data between the players so that they can all see the same scene while playing, which wasn’t a concern in a single-player game.
We will start by discussing how game data is shared between the players.
Game Server
In a multiplayer game environment, the game world is affected by the actions of all players that are joined in that session. Imagine a 4vs4 shooter game. You need to ensure that all players in the session see the same scenes (from different angles), otherwise, it wouldn’t be a very good gaming experience and your game will not last long.
Synchronizing the game world is no easy task. For our shooter game example, each time a player makes an interaction by moving, shooting, jumping, using stupid emotes, etc.; the game world will be affected. You need to exchange data between players each time an action occurs so that they can all see the same world.
Peer-to-peer communication is obviously not a good choice here, assuming you have 8 players in the game you would need a total of 28 connections to share data between all players. Instead, online games prefer the server-client approach, in which the players are the clients.
When a player interacts with the game world, interactions of the player are transmitted into the game server to be processed. The game server collects player interactions, processes them and sends updates to the clients so that all players are able to see the same game state on their individual machines.
The game developers can choose to use local-player-hosted games instead of using dedicated servers. In this case, one of the players — preferably the one with the lowest latency — is chosen to be the game host and the player’s local machine is promoted to be the game server. By doing this, the cost of deploying dedicated servers can be avoided but developers will have less control over the servers and the servers are more susceptible to various types of problems.
Latency
Hosting dedicated servers almost always outperforms local hosting since they are specifically designed to fulfil the task. This doesn’t mean that you cannot have a bad experience though, for your experience still depends on your local machine and your network connection.
The round-trip time is the time that passes between sending a request to the server and getting back the answer. If your connection is poor, there will be delays in your communication with the server, which will increase the round-trip time and message latency. When this happens, inconsistencies will occur in the game state between your local machine and the server.
If the server does not receive your messages on the required time window or somehow your messages are lost in transmission, it will calculate your state using the latest data. So let’s say you were running forward and all of a sudden turned left but for some reason, the server did not receive the request to turn left. Then the server will assume that you kept running forward but on your local machine you see that you turned left. When the connection is back to normal, you will get teleported to the server's calculated location.
This phenomenon is what all gamers know as lagging. There may be many reasons you experience lags, from network issues to hardware problems. It also does not have to be consistent, latency on the network can change over time. Fluctuations in the latency cause the jitter effect and it will cause a choppy gaming experience after a certain threshold.
Low latency in the network is significant for online gaming. Many game developers deploy server instances on multiple locations so that they can decrease the round-trip time by enabling regional play. This way you will be connecting to the Asian server instead of the US server, if you are residing in Japan, effectively lowering the latency.
How much latency you can tolerate depends on the needs of your game. If you are developing a turn-based game, for example, you can probably get away with quite a bit of latency without players affecting that much. However, if you are developing an online game in the shooter or racing genres, having a high latency network would greatly lower the user experience.
So far we have only seen the basics of the multiplayer networks, that serves as an introduction — a long one — to this chapter. From now on we will focus on the synchronization part.
Replication
Now let’s start putting the game clients into the equation. The game consists of a bunch of entities: players, vehicles, light sources, all sorts of interactable objects… Each client contains a replica of these entities and each player sees the same game world from their own character’s perspective.
As the players interact with the game world, the state of these entities will be updated. When a player hits on a ball, for example, every player in that game observes the ball’s movement. To do that, the corresponding player sends the ball’s movement to the server, and the server processes the ball’s movement and transmits it to all the clients so that each player can see the ball’s movement on their own device.
Assume that the game we are developing runs at 30 FPS. Does this mean that the server needs to deliver 30 updates (one update for each frame) to each player in each second so that the game can run smoothly? No, that would be overkill and can cause congestion on the network. If we send the updates once every three frames instead, we would lower the network load by 66%.
As you can expect, there are ways to do that. We will use linear algebra to calculate entity positions in some of the frames. Don’t worry, it is very simple. First, we need to understand two related estimation techniques:
- Interpolation: Interpolation is used in the estimation of intermediate values. Assume that you have the position of your character at discrete time intervals t₀, t₁, t₂… Linear interpolation helps you to calculate the continuous values for the character position between t₀ and t₁ so that you can have a smooth character transition.
- Extrapolation: Extrapolation is very similar to interpolation but it takes the previously known values and tries to predict where your character will go in the future.
How does this linear interpolation calculation work? We will visit our physics knowledge next and use the linear movement equation:
We use the speed and acceleration values along with the last known position of the character. This way, we can estimate the character's position at a given time. Of course, this will give us only an estimation, the actual position of the character may not be the same as our estimation but more on this later.
Linear interpolation is frequently used in animation. Since drawing each frame one by one is an exhaustive approach, animators usually draw the keyframes. The intermediate frames are calculated using linear interpolation. The image below depicts the calculated locations between the keyframes.
Dead Reckoning
In a multiplayer game, there is always a certain amount of delay until the clients receive the updates from the server. Imagine you are developing a multiplayer racing game. When the current player’s car moves from point A to point B, the current player immediately observes this movement. The current player sends an update to the server, the server processes the data and sends the update to the clients. Only then can the rest of the players observe the car’s movement.
Even when you play the game on a machine with a good network connection, you still have to wait for the amount of time the packets travel from other clients to the server and then to you. So the update we receive from the server does not actually contain the most recent location of an entity — kind of like we are only able to observe the past states of the stars in the universe. This means that the clients will always be behind the current game state in a multiplayer environment.
Extrapolation to the rescue! A car moves fast, but its movement is quite predictable. In a realistic racing game, you cannot change a car’s future state drastically in just a few frames. You can change its speed a little bit, or turn it a few degrees but you cannot make a 180-degree turn instantly.
We can use its last known positions— and a bunch of things like rotation, velocity, acceleration, etc— and try to predict where it will end up in the future. This technique is also called dead reckoning and actually has various applications in different research areas.
Notice that extrapolation is an estimation technique and it doesn’t necessarily calculate the exact location where your rival’s car will end up. Since the car’s actual position depends on the input of the controlling player, it is natural that the predicted position is a little different than the position received in the next update.
Therefore, we need to correct the error in prediction when the updates are received. You cannot simply update the position of the car with the incoming value, this will cause the car to teleport and players will experience jitter. Instead, what you can do is slowly blend the car into the correct position so players have a seamless gameplay experience. Bezier curves and Hermite splines can be utilized in the correction function. I know you are not going to read them but I still had to share the Wikipedia links.
Entity Interpolation
For the most part of our racing game, the amount of error is fairly low and easily manageable. But what happens if you crash the car? In that case, the predicted position may be extremely wrong. In fact, in any scenario the speed and the direction instantly change, dead reckoning will not work very accurately.
Let’s leave our racing game example for now and consider a shooter instead. Players constantly make sudden moves in shooter games, like suddenly changing direction to shoot other players or jumping and rolling in order to dodge incoming bullets. These types of situations are very hard to predict using the dead reckoning algorithm since the previous position of the player is not that relevant to the current state of the player.
What can we do then? I mean, obviously, we are going to use interpolation but how? There is a neat little trick game developers use. That is, they show the other players a little bit of the past in comparison with the current player. Assume that you are receiving updates from the server once every 100 ms (or once every 3 frames if you are developing a 30 FPS game). The current player will always see where the other players were 100 ms ago while it sees itself in the present.
We were able to use linear interpolation in this case, since we know the exact locations of the players just a little bit late. Therefore, there is no need to predict where they will end up in the future. Notice that, in this method, each player observes a slightly different rendering of the game world.
This method is not bulletproof (appreciate the wordplay) either. For example, when you shoot a player, you are aiming at where the player was 100 ms ago. And since the server decides whether or not your shot hits the enemy… Well, you miss it! Because it will already be gone when your message is received by the server.
Luckily we can fix this too. When you send a message to the server, you are not only telling what actions you performed but also when did you perform them. And the server knows the exact time of the player interactions, it can construct the game world at any point in the past. So the server is able to understand that you are aiming at your enemy when you squeezed that trigger. Thus, the server decides that you successfully hit your enemy.
In this story, we designed a network architecture for multiplayer games and then we studied different techniques that can help us achieve game-world consistency between the players. In a real scenario, there would be many more exception cases to handle but the aim of these posts is to understand the main concepts, as always.
And thus, the first entry in the series concludes… It is designed for developers and game enthusiasts, and I am planning to post new entries for a long time, just like my Algorithms in Context series. So keep in touch and let me know if there are interesting topics you want me to write about.
