Multiplayer Game Development with HTML5 (2015)
Chapter 4. Reducing Network Latency
Now that we have a working game that allows the presence of multiple players in the same or multiple game rooms, we will iterate and take care of a very important issue in online games, namely, network latency. Given the fact that you will need to think about this problem for many years to come, we will be very focused on the topics covered in this chapter.
In this chapter, we will discuss the following principles and concepts:
· Dealing with network latency in multiplayer games
· Implementing a local game server in the client
· Client-side prediction
· Interpolating real positions to correct bad predictions
Dealing with network latency
Although you may well be one of the happy citizens out there with a gigabit internet connection, you should know that most of the world is certainly not as fortunate. Thus, some of the most important things to keep in mind when developing online multiplayer games are that not all players will have the same network speed and not all players will have high-speed connections.
The main takeaway point that you need to remember from this section is that, as long as there is a network between your players and the game server (or between two players connected directly to each other), there will be latency.
It is true that not all games need near instantaneous response times over the network, for example, turn-based games such as Chess, or our implementation of Snake, since the game tick is much slower than most action games. However, for a real-time, fast-paced game, even a small latency of, say, 50 ms, can make the game very jerky and annoying to play.
Imagine this for a moment. You press the right arrow key on the keyboard. Your game client tells the server that your intent is to move to the right. The server finally gets your message 50 ms later, runs its update cycle, and tells you to place your character at the position (23, 42). Finally, another 50 ms later, your client receives the message from the server, and a whole tenth of a second after you pressed the key on the keyboard, your player begins to move to your desired location.
As mentioned in the previous chapters, the most commonly used solution to the network latency problem is to change the client logic so that it can respond to user input immediately, while updating the server about its input at the same time. The authoritative server then updates its own game state based on the input from each client and finally sends out its version of the current state of the game world to all of the clients. These clients can then update themselves so that they are in sync with the server and the process continues.
Thus, as you may have realized, the goal is not at all to get rid of latency since this is physically impossible, but merely to hide it behind a constantly updating game so that the player has the illusion that the game is being updated by the server in real time.
As long as the player feels that the game is responsive and behaves as the player expects it to, for all practical purposes, you have solved the network latency issue. With every communication with the server (or from the server to the client), ask yourself where the latency is and how you can hide it by keeping the game going while the packets travel across the wire.
Synchronizing clients in lockstep
So far, we've discussed the client-server structure where the server is the ultimate authority on the game, and clients have little or no authority over the game's logic. In other words, clients simply take in any input from the player and pass it along to the server. Once the server sends out updated positions to the clients, the game state is rendered by the clients.
One other model that is commonly used in online multiplayer games is the lockstep method. In this method, a client tells the server about any input received from the player as often as it can. The server then broadcasts this input to all other clients. The clients in turn use the input state for each participant in the next update cycle, and in theory, everyone ends up with the same game state. Each time the server takes a lockstep (runs physics update from the input data from each client), we call it a turn.
In order for the server to remain as the ultimate authority over the game, an update cycle is also run in the server's simulation, and the output of the simulation is also broadcasted to the clients. If a client's updated state differs from the one sent by the server, the client takes the server's data tobe correct and updates itself accordingly.
Fixed-time step
The first thing that we'll update in our server's code is the game loop, and the first thing that it'll do differently is that it will no longer have the concept of delta times. In addition, we will need to queue up all input from each client between update cycles so that we have the data to update the game state with, when we run the physics update.
Since we're now using a consistent time step, we have no need to keep track of delta times on the server. As a result, the server also has no concept of delta times from the clients' perspective.
For example, imagine a racing game where a player is driving at, say, 300 pixels per second. Suppose this particular client is running the game at a frequency of 60 frames per second. Provided that the car maintained a steady speed during the entire second, then after 60 frames, the car will have travelled 300 pixels. Additionally, during each frame the car will have travelled an average of 5 pixels.
Now, suppose that the server's game loop is configured to run at a frequency of 10 frames per second, or once every 100 milliseconds. The car will now travel further per frame (30 pixels instead of 5 pixels), but in the end, it will also be 300 pixels further than where it started one second ago.
In summary, while the clients will still need to track how long it takes to process a single frame in order for all the clients to run at the same speed, regardless of how fast or slow different computers run the game loop, the server's game loop doesn't care about any of this because it doesn't need to.
// ch4/snake-ch4/share/tick.js
var tick = function (delay) {
var _delay = delay;
var timer;
if (typeof requestAnimationFrame === 'undefined') {
timer = function (cb) {
setImmediate(function () {
cb(_delay);
}, _delay);
}
} else {
timer = window.requestAnimationFrame;
}
return function (cb) {
return timer(cb);
}
};
module.exports = tick;
Here, we first update our tick module that we built for the purpose of reusing code in the server code as well as in the code that is shipped to the browser. Note the use of setImmediate instead of setTimeout, which will perform theoretically faster since the callback is scheduled earlier in the execution queue.
In addition, observe how we export the wrapper tick function instead of the closure that it returns. This way we can configure the server's timer before exporting the function.
Finally, since the delta time is now predictable and consistent, we no longer need the tick's variable to simulate the passage of time. Now, we can just pass the interval value directly into the callback function after each tick.
// ch4/snake-ch4/share/game.js
var tick = require('./tick.js');
tick = tick(100);
var Game = function (fps) {
this.fps = fps;
this.delay = 1000 / this.fps;
this.lastTime = 0;
this.raf = 0;
this.onUpdate = function (delta) {
};
this.onRender = function () {
};
};
Game.prototype.update = function (delta) {
this.onUpdate(delta);
};
Game.prototype.render = function () {
this.onRender();
};
Game.prototype.loop = function (now) {
this.raf = tick(this.loop.bind(this));
var delta = now - this.lastTime;
if (delta >= this.delay) {
this.update(delta);
this.render();
this.lastTime = now;
}
};
The only difference that you will notice here is that the tick module is called with the frequency it is being passed in, so we can configure how fast we wish it to run.
Note
You may wonder why we selected the possibly arbitrary number of 10 updates per second for the server's game loop. Remember that our goal is to make our players believe that they're actually playing an awesome game together with other players.
The way in which we can achieve this illusion of real-time game play is by carefully hand-tuning the server to update fast enough so that the accuracy is not too far off and slow enough so that the clients can move in such a way that the lag is not too noticeable.
You need to find the balance between the authoritative server that provides accurate game state versus the client's ability to provide a responsive experience to the player. The more often you update the clients with data from the server's update cycle, the less accurate your simulation will be; this depend on how much data the simulation had to process and possibly drop data along the way in order to keep up with the high update frequency. Similarly, the less often you update the clients with data from the server's update cycle, the less responsive the client will feel, since it'll need to wait longer on the server before it knows for sure what the correct game state should be.
Synchronizing the clients
As the server consistently pushes out updates about the current state of the game world, we need a way for the clients to consume and make use of this data. A simple way to achieve this is to hold the latest server state outside the game class and update itself whenever the data is available since it won't be present every update tick.
// ch4/snake-ch4/share/app.client.js
// All of the requires up top
// …
var serverState = {};
// …
socket.on(gameEvents.client_playerState, function(data){
otherPlayers = data.filter(function(_player){
if (_player.id == player.id) {
serverState = _player;
return false;
}
_player.width = BLOCK_WIDTH;
_player.height = BLOCK_HEIGHT;
_player.head.x = parseInt(_player.head.x / BLOCK_WIDTH, 10);
_player.head.y = parseInt(_player.head.y / BLOCK_HEIGHT, 10);
_player.pieces = _player.pieces.map(function(piece){
piece.x = parseInt(piece.x / BLOCK_WIDTH, 10);
piece.y = parseInt(piece.y / BLOCK_HEIGHT, 10);
return piece;
});
return true;
});
});
Here, we declare the serverState variable as a module-wide global. Then, we modify the socket listener that grabs the state of all other players when the server updates that, but now, we look for the reference to the player that represents the hero here, and store that in the global serverStatevariable.
With this global state on hand, we can now check for its existence during the update method of the client and act accordingly. If the state is not there at the beginning of a given update cycle, we update the client as before. If the world state from the server is in fact available to us at the beginning of the next client update tick, we can synchronize the client's positions with the server instead.
// ch4/snake-ch4/share/app.client.js
game.onUpdate = function (delta) {
if (serverState.id) {
player.sync(serverState);
// On subsequent ticks, we may not in sync any more,
// so let's get rid of the serverState after we use it
if (player.isSyncd()) {
serverState = {};
}
} else {
player.update(delta);
player.checkCollision();
if (player.head.x < 0) {
player.head.x = parseInt(renderer.canvas.width / player.width, 10);
}
if (player.head.x > parseInt(renderer.canvas.width / player.width, 10)) {
player.head.x = 0;
}
if (player.head.y < 0) {
player.head.y = parseInt(renderer.canvas.height / player.height, 10);
}
if (player.head.y > parseInt(renderer.canvas.height / player.height, 10)) {
player.head.y = 0;
}
}
};
The actual implementation of Player.prototype.sync will depend on our strategy for error correction, which is described in the next couple of sections. Eventually, we'll want to incorporate both teleportation and interpolation, but for now, we'll just check whether any error correction is even necessary.
// ch4/snake-ch4/share/snake.js
var Snake = function (id, x, y, color_hex, width, height) {
this.id = id;
this.color = color_hex;
this.head = {
x: x,
y: y
};
this.pieces = [this.head];
this.width = width || 16;
this.height = height || 16;
this.readyToGrow = false;
this.input = {};
this.inSync = true;
};
Snake.prototype.isSyncd = function(){
return this.inSync;
};
Snake.prototype.sync = function(serverState) {
var diffX = serverState.head.x - this.head.x;
var diffY = serverState.head.y - this.head.y;
if (diffX === 0 && diffY === 0) {
this.inSync = true;
return true;
}
this.inSync = false;
// TODO: Implement error correction strategies here
return false;
};
The changes to the snake class are pretty straightforward. We add a flag to let us know whether we still need to synchronize with the server state after a single update cycle. This is necessary because when we decide to interpolate between two points, we'll need multiple update cycles to get there. Next, we add a method that we can call to verify whether the player is (or isn't) in sync with the server, which determines how the snake updated the given frame. Finally, we add a method that performs the actual synchronization. Right now, we simply check whether there is a need to update our position. As we discuss different error correction strategies, we'll update the Snake.prototype.sync method to make use of them.
Predicting the future with a local game server
The strategy that we will use in order to make our clients responsive, yet bound to the authoritative server, is that we will act on the input that we receive from the player while we tell the server about the input. In other words, we will need to take the player's input and predict what will happen to our game state as a result, while we wait to hear back from the server with the actual output of the player's action.
Client-side prediction can be summarized as your best guess about what should happen between authoritative updates. In other words, we can reuse some of the server code that updates the game world on the client-side so that our guess about what the output should be from the player's input is pretty much the same as what the server will simulate.
Reporting user input
The first thing that we'll change is the control mechanism on the client side. Instead of simply keeping track of our position locally, we'll also inform the server that the player has pressed a key.
// ch4/snake-ch4/share/app.client.js
document.body.addEventListener('keydown', function (e) {
var key = e.keyCode;
switch (key) {
case keys.ESC:
game.stop();
break;
case keys.SPACEBAR:
game.start();
break;
case keys.LEFT:
case keys.RIGHT:
case keys.UP:
case keys.DOWN:
player.setKey(key);
socket.emit(gameEvents.server_setPlayerKey, {
roomId: roomId,
playerId: player.id,
keyCode: key
}
);
break;
}
});
Of course, doing this directly in the event handler's callback might quickly overwhelm the server, so be sure to time this upward reporting. One way to do this is to use the tick update to contact the server.
// ch4/snake-ch4/share/app.client.js
game.onUpdate = function (delta) {
player.update(delta);
player.checkCollision();
// …
socket.emit(gameEvents.server_setPlayerKey, {
roomId: roomId,
playerId: player.id,
keyState: player.input
}
);
};
Now, we update the server at the same frequency that we update our local simulation, which is not a bad idea. However, you might also consider leaving all networking logic outside of the game class (update and render methods) so that the networking aspects of the game is abstracted out of the game altogether.
For this, we can put the socket emitter right back in the controller's event handler; however, instead of calling the server right away, we can use a timer to keep the updates consistent. The idea is that, when a key is pressed, we call the server right away with the update. If the user pushes a key again before some time has gone by, we wait a certain amount of time before calling the server again.
// ch4/snake-ch4/share/app.client.js
// All of the requires up top
// …
var inputTimer = 0;
var inputTimeoutPeriod = 100;
// …
document.body.addEventListener('keydown', function (e) {
var key = e.keyCode;
switch (key) {
case keys.ESC:
game.stop();
break;
case keys.SPACEBAR:
game.start();
break;
case keys.LEFT:
case keys.RIGHT:
case keys.UP:
case keys.DOWN:
player.setKey(key);
if (inputTimer === 0) {
inputTimer = setTimeout(function(){
socket.emit(gameEvents.server_setPlayerKey, {
roomId: roomId,
playerId: player.id,
keyCode: key
}
);
}, inputTimeoutPeriod);
} else {
clearTimeout(inputTimer);
inputTimer = 0;
}
break;
}
});
Here, the inputTimer variable is a reference to the timer that we created with setTimeout, which we can be canceled at any moment until the timer is actually fired. This way, if the player presses many keys really fast (or holds a key down for a while), we can ignore the additional events.
One side effect of this implementation is that, if the player holds down the same key for a long time, the timer that wraps the call to socket.emit will continue to be canceled, and the server will never be notified of subsequent key presses. While this may seem like a potential problem at first, it is actually a very welcome feature. Firstly, in the case of this particular game where pressing the same key two or more times has no effect, we really don't need to report the additional presses to the server. Secondly (and this holds true for any other type of game as well), we can let the server assume that, after the player presses the right arrow key, the right key is still being pressed until we tell the server otherwise. Since our Snake game doesn't have a concept of a key being released (meaning that the snake will constantly move in the direction of the last key press until we change its direction), the server will continue to move the snake in a given direction until we press a different key and tell the server to move it in the new direction.
Error correction
Once the server has every player's input state, positions, and intents, it can take a lockstep turn and update the entire game world. Since at the time when an individual player makes a move, he or she only knows about what is happening in that particular client, one thing that could happen is that another player could play in their local client in such a way that there is a conflict between the two players. Maybe, there was only one fruit and both players attempted to get to it at the same time, or it is possible that another player ran into you, and you're now going to be taking some damage.
This is where the authoritative server comes into play and puts all the clients on the same page. Whatever each client predicted in isolation should now match what the server has determined so that everyone can see the game world in the same state.
Here is a classic example of a situation where network latency can get in the way of a fun multiplayer experience. Let's imagine that, two players (player A and player B) start heading for the same fruit. According to each player's simulation, they're both coming from opposite directions and headed for the fruit, which is now only a few frames away. If neither player changes direction, they would both arrive at the fruit at the exact same frame. Suppose that, in the frame before player A eats the fruit, he decided to change direction for whatever reason. Since player B doesn't get player A's updated state and position from the server for a few frames, he might think that player A was indeed going to eat the fruit, so player B's simulation would show player A eating the fruit and getting points for it.
Given the previous scenario, what should player B's simulation do when the server sends the next turn's output that shows that player A swerved away from the fruit and didn't earn any points? Indeed, the two states are now out of sync (between player B's simulation and the server), so player B should get better synchronized with the server.
Play through the intent, but not the outcome
A common way to handle the scenario that was mentioned previously is to include some sort of animation that a client can start right away based on its current knowledge of the player's intent and the current state of the game world. In our specific case, when player B thinks that player A is about to grab the fruit and earn some points, his or her simulation could start an animation sequence that would indicate that player A is about to level up by eating a fruit. Then, when the server responds back and confirms that player A didn't actually eat the fruit, player B's client can fall back to some secondary animation that would represent that the fruit was untouched.
Those of you who are fans of Halo might have noticed this in action when you attempted to throw a grenade in the game during an online session with your mates. When a client decides to toss a hand grenade in Halo, the client will inform the server about this intent right away. The server will then run a bunch of tests and checks to make sure that this is a legal move. Finally, the server will respond back to the client and inform it whether it is allowed to continue with the tossing of the grenade. Meanwhile, during this time when the server confirmed that the client could throw that grenade, the client started playing through the animation sequence that it does when a player throws a grenade. If this is left unchecked (that is, the server doesn't respond back in time), the player will finish swinging his arm forward, but nothing will be thrown, which, in this context, will look like a normal action [Aldridge, David (2011), I Shot You First: Networking the Gameplay of HALO: REACH. GDC 2011].
How close is close enough?
Another use case is that a client has the current state of the game along with the player's input information. The player runs the next turn's simulation and renders the snake at a certain position. A few frames later, the server tells the client that the snake is actually at a different position now. How do we fix this?
In situations where we need to change a player's position, it might look strange if the player launches a blue robot into the air and over a pit with spikes at the bottom, and a few frames later (after the server syncs up all of the clients), we suddenly see the robot several pixels away from where the player expected it to be. However, then again, there are cases where the adjustment needed from an update from the server is small enough so that simply teleporting the player from point A to point B is not noticeable. This would be heavily dependent on the type of game and the individual situation.
For the purpose of our Snake game, we can choose to teleport if we determine that the discrepancy between our prediction of where the snake should be, and where the server tells us the snake is, is only off by one unit in either (not both) axis, except if the head is off by one unit in both the axes but adjusting one of the axis would put us at the neck of the snake. This way, the player would only see the snake change the position of its head by one place.
For example, if our prediction puts the player's head at point (8,15), and the snake is moving from right to left, but the server's update shows that it should be at point (7,16), we would not teleport to the new point because that would require adjusting two axes.
However, if we still have the snake moving to the left and its head is now at point (8,15), and the server update puts it at point (7,15), (8,14), (8,16), (9,15), (9,14), or (9,16), we can simply teleport the head to the new point, and in the next update, the rest of the body of the snake would be repositioned, as needed.
// ch4/snake-ch4/share/snake.js
Snake.prototype.sync = function(serverState) {
var diffX = serverState.head.x - this.head.x;
var diffY = serverState.head.y - this.head.y;
if (diffX === 0 && diffY === 0) {
this.inSync = true;
return true;
}
this.inSync = false;
// Teleport to new position if:
// - Off by one in one of the axis
// - Off by one in both axes, but only one unit from the neck
if ((diffX === 0 && diffY === 1)
|| (diffX === 1 && diffY === 0)
|| (this.pieces[0].x === serverState.head.x && diffY === 1)
|| (this.pieces[0].y === serverState.head.y && diffX === 1)
){
this.head.x = serverState.head.x;
this.head.y = serverState.head.y;
this.inSync = false;
return true;
}
// TODO: Implement interpolation error correction strategy here
return false;
};
You will notice that teleporting could put the head of the snake over itself, which, under normal circumstances, would result in the player losing the game. However, when this happens, the game won't check for that collision again until the next frame is updated. At this point, the head will be first moved forward, which will readjust the rest of the body of the snake and thus remove any possible collisions.
Smooth user experience
Another way to adjust between the player's current position and the position set by the server is to gradually and smoothly move towards that point through the course of multiple frames. In other words, we interpolate between our current position and the position we want to get to.
The way interpolation works is simple, as explained here:
1. First determine how many frames you want the interpolation to take.
2. Then determine how many units you will need to move in each direction per frame.
3. Finally, move each frame a little bit until you get to the destination point in the desired amount of frames.
Essentially, we simply move a percentage of the way towards the target point at the same percentage of the time we wish to get there. In other words, if we would like to get to the target position in 10 frames, then at each frame we move 10 percent of the total distance. Thus, we can abstract away the following formula:
a = (1 – t) * b + t * c
Here, t is a number between zero and one, which represents a percentage value between 0 percent and 100 percent (this is the current distance between the starting point and the target point).
We can implement the linear interpolation method in the snake class directly; however, the obsessed object-oriented designer inside of you might argue that this mathematical procedure might be better suited inside an entirely separate utility class that is imported and used by the snake class.
// ch4/snake-ch4/share/snake.js
Snake.prototype.interpolate = function(currFrame, src, dest, totalFrames) {
var t = currFrame / totalFrames;
return (1 - t) * src + dest * totalFrames ;
};
This interpolation method will take (besides the source and destination points) the current frame within the animation as well as the total number of frames that the animation will last. As a result, we'll need some way to keep track of the current frame and reset it to zero when we wish to start the animation again.
A good place to reset the interpolation sequence is in the socket callback, which is where we first learn that we might need to interpolate towards a different position.
// ch4/snake-ch4/share/app.client.js
socket.on(gameEvents.client_playerState, function(data){
otherPlayers = data.filter(function(_player){
if (_player.id == player.id) {
serverState = _player;
serverState.currFrame = 0;
return false;
}
return true;
});
});
We will then also need to update the snake class so that we can configure the maximum amount of frames that each interpolation cycle can handle.
// ch4/snake-ch4/share/snake.js
var Snake = function (id, x, y, color_hex, width, height, interpMaxFrames) {
this.id = id;
this.color = color_hex;
this.head = {x: x, y: y};
this.pieces = [this.head];
this.width = width || 16;
this.height = height || 16;
this.interpMaxFrames = interpMaxFrames || 3;
this.readyToGrow = false;
this.input = {};
this.inSync = true;
};
With this in place, we can now implement linear interpolation in our sync method so that the snake can interpolate smoothly to its actual position over the course of a few frames. The number of frames that you choose to arrive at the target destination can be dynamically set depending on the distance to travel, or you can leave it constant as per your game's individual case.
// ch4/snake-ch4/share/snake.js
Snake.prototype.sync = function(serverState) {
var diffX = serverState.head.x - this.head.x;
var diffY = serverState.head.y - this.head.y;
if (diffX === 0 && diffY === 0) {
this.inSync = true;
return true;
}
this.inSync = false;
// Teleport to new position if:
// - Off by one in one of the axis
// - Off by one in both axes, but only one unit from the neck
if ((diffX === 0 && diffY === 1) ||
(diffX === 1 && diffY === 0) ||
(this.pieces[0].x === serverState.head.x && diffY === 1) ||
(this.pieces[0].y === serverState.head.y && diffX === 1)) {
this.head.x = serverState.head.x;
this.head.y = serverState.head.y;
this.inSync = true;
return true;
}
// Interpolate towards correct point until close enough to teleport
if (serverState.currFrame < this.interpMaxFrames) {
this.head.x = this.interpolate(
serverState.currFrame,
this.head.x,
serverState.head.x,
this.interpMaxFrames
);
this.head.y = this.interpolate(
serverState.currFrame,
this.head.y,
serverState.head.y,
this.interpMaxFrames
);
}
return false;
};
Finally, you will notice that, in this current implementation of our client-server setup, the client receives the exact positions of the other players, so no prediction is made about them. Thus, their positions are always in sync with the server and need no error corrections or interpolations.
Summary
The focus of this chapter was to reduce the perceived latency between the authoritative server and the clients that it runs. We saw how client prediction can be used to give the player immediate feedback while the server determines the validity of a player's requested move and intent. We then looked at how to incorporate the lockstep method on the server so that all the clients are updated together, and every client can also deterministically reproduce the same world state that is calculated by the game server.
Finally, we looked at the two ways to correct a bad client prediction. The methods we implemented are teleportation and linear interpolation. Using these two error-correction methods allows us to show the player a close approximation of what should happen as a result of his or her input, but it also makes sure that their multiplayer experience is accurate and identical to what other players are experiencing.
In the next chapter, we will take a step into the future and play with some of the newer HTML5 APIs, including the Gamepad API, which will allow us to ditch the keyboard and use the more traditional game pad to control our games, Full-screen mode API, and WebRTC, which will allow us to do true peer-to-peer gaming and skip the client-server model for a while, and much more.