Clients synchronization in Phaser Quest

In a previous article, I explained the basics of making a multiplayer online game. From there, many improvements are possible and desirable with respect to clients synchronization, especially for more complex games such as Phaser Quest.

A crucial aspect in real-time multiplayer online games is to keep all clients synchronized. In other words, to make sure they all share a similar view of the state of the game, without any discrepancies. The state of the game corresponds to the positions of all players and non-player elements, their status, the actions they are performing, and any other variables that can have any impact on the game itself.

Synchronization is achieved by properly sending information to the clients so that they can update their representation of the game state. The quantity of data sent to do so, and the pace at which the data is sent, has important consequences. Too much, and you’ll exceed the available bandwidth, causing delays on the client side (and possible billing troubles on your side depending on how you host your server). Too little, and you risk that the synchronization might break and that the game states of the different clients start to diverge. In this article, I’ll explain the approach I adopted to manage client updates and synchronization in the case of Phaser Quest.

The source code of Phaser Quest can be accessed on the Github repository. However, some of the code shown in this article is different from the code on the repository, because of additional optimizations that are not discussed in this article for the sake of clarity.

The naive approach

The naive approach to clients synchronization is to have the server repeatedly send the entire game state to all clients, multiple times per second (e.g. 60 times per second). For example, the server could send, every 16ms, a JSON object containing the position of all players, monsters and items in the game. The clients would process this by iterating over all these objects and updating their positions if necessary.

This can quickly become very heavy. Let’s consider that we want to send data about players only, and that we can encode the data corresponding to one player with 10 bytes (which is conservative, complex games where players have a lot of properties relevant to the game state will need more than that). Here is how the amount of data exchanged evolves as the number of players increases:

Number of playersClient bandwidthServer bandwidth
22*10*60 = 1.2Kbps2*10*60*2 = 2.4Kbps
33*10*60 = 2.7Kbps3*10*60*3 = 8.1Kbps
1010*10*60 = 6Kbps10*10*60*10 = 60Kbps
100100*10*60 = 60Kbps100*10*60*100 = 6Mbps

As you can see, this quickly gets out of hand, even for a very small payload and a very limited game state. This can be improved a lot by using what I’ll refer to as “delta packets”.

Clients synchronization using delta packets

The idea of delta packets is to send over only the changes that were applied to the game state, instead of sending the whole game states (hence the name “delta”, for difference). These packets consist in bundles of all the properties that have changed in any game object. If new objects have been added to the game state, the change is the creation of the object itself, and in this case all of its relevant properties need to be sent.
Note: An alternative would be to broadcast the changes to all players a soon as they take place. This is not optimal, because of the overhead of sending lots of packets containing small amounts of update information. Bundling the changes together in update packets sent at regular intervals alleviates this overhead.

In addition, given the relatively slow pace of Phaser Quest (compared to a FPS for example), these packets are sent 5 times per second, instead of 60. It turns out that this update rate is fast enough to represent the changes in the game (such as a player picking up an item or killing a monster) without any feeling of lag or stutter.
Note: such a rate would not be suitable to update the position of the players, therefore a different approach is used for that; see relevant section below.

This approach has two main advantages. First, the number of entities whose properties have changed between two updates is typically much smaller than the total number of entities in the game. Moreover, the number of properties affected is usually smaller than the total number of properties that the entities have. It follows from this that the amount of data to send to inform the clients about changes in the game state is much lower than the amount of data needed to send the full game state.

Second, when nothing happens, no update is sent at all, which in terms of benefits is the extreme case of the above point. This benefit may not arise in a standard implementation (as a game where nothing happens is very dull), but when combined with an interest management system, it is quite possible to go through several update cycles without any updates to send, with significant savings in terms of resources.

In the rest of this section, I’ll show how keeping track of the differences to send is implemented in Phaser Quest. A similar approach is used to take care of new objects added to the state. I’ll not provide too much code, for two reasons:
– Some of the actual code is actually a bit different and more complex than what I’m describing here, because I implemented a custom interest management system.
– Covering all the code involved would be quite long and tedious and would be detrimental to the focus of the article. My attempt here is to convey the main idea of what has been done; for more details, I invite you to check the source code and to contact me to ask any question you might have. If I receive multiple questions on the same aspect, I’ll try to address it here.

Keeping track of changes in the game state

On the server side, all the game entities susceptible of being updated inherit from the GameObject object.

js/server/GameObject.js
Class hierarchy for the game objects on the server

In the rest of the server code, whenever a method modifies a property of a game object and this change is relevant for the clients, the change is made using the GameObject.setProperty() method:

// Updates a property of the object and update the update packet
GameObject.prototype.setProperty = function(property,value){
    this[property] = value;
    // category is a string property indicating if the game object is actually a 'monster', 'player' or 'item'
    if(this.id !== undefined) GameServer.updatePacket.updateProperty(this.category, this.id, property, value); // Updates the current updatePacket
};

GameServer.updatePacket is the object that the clients will receive at each update, containing the information regarding what updates to apply. Among other things, it contains associative arrays that map the id’s of game objects to smaller objects listings which properties have changed. Here is an example about changes affecting players. In this example, player 2 has had his life change to the value of 100, whereas player 9 has had his life change to 150 and his armor to 3 (the id of the actual armor object).

{
  players:{ // list changes made to player objects; maps the id's of the modified players to objects listing the changes
    2:{
      life: 100
    },
    9:{
      life: 150,
      armor: 3
    }
  }
}

js/server/UpdatePacket.js

The updatePacket prototype contains several other methods to populate the updatePacket objects. For example, when a player connects to the game, the relevant method will add it to an array listing the players that have been added to the game state. When an item spawns, it will be added to a similar array, but for items. When an existing player changes one of his properties (e.g. has equipped a new armor), the map players will contain an entry reflecting the change, in a similar fashion as in the example above. Such updates are recorded using the updatePacket.updateProperty() method:

UpdatePacket.prototype.updateProperty = function(type,id,property,value){
    var map; // Determine if the map to update is this.items, this.players or this.monsters, based on the "type" argument
    switch(type){
        case 'item':
            map = this.items;
            break;
        case 'player':
            map = this.players;
            break;
        case 'monster':
            map = this.monsters;
            break;
    }
    if(!map.hasOwnProperty(id)) map[id] = {}; // If this map doesn't have an entry corresponding to the id of the entity whose property has changed, add it
    if(map[id][property] != value) map[id][property] = value;
};

Depending of the type of the modified object, a different map is selected, and key-value pair indicating the property that has changed and the value it has taken is added to the map.

Every 200ms, the GameServer.updatePlayers() method will send the current updatePacket object to all clients, and then delete it to create a fresh new one ready to store changes to the game state for the next 200ms. On the client side, each property of the update packet is processed by the relevant methods. For example, the changes stored in updatePacket.players are processed by Game.updatePlayerStatus() and Game.updatePlayerAction().

What I have described so far corresponds to what I call “global” update packets; packets containing updates that will be them same for all clients and visible to all (e.g. if a player changes his armor, everyone should be able to see it). In addition to that, a similar process is used to maintain “local” update packets; changes specific to only one player and visible only to him. The local update packet of each client is bundled to the global update packet, so the client receives both at the same time, without any overhead.

Sending movement updates

All the above works well for discrete changes, such as changes in appearance, monsters dying, objects being dropped or picked and so on. In order to work well for continuous changes, such as players moving across the map, the same logic could be used, but with a much higher pace of updates (at least 30 times per second). It is however possible, in the context of this game, to be smarter than that, by leveraging the deterministic nature of the pathfinding algorithm.

Deterministic pathfinding

In Phaser Quest, the trajectory of player movements is computed using pathfinding, with the easystar.js library on the client side (to compute the paths that the players will follow) and the pathfinding npm package on the server side (to compute the paths that the monsters will follow). When player A clicks on a tile, the algorithm computes the shortest path to that tile, and sends the computed path to the server. The server checks if the path is legal (i.e. if no cheating attempt was made), and if yes, it notifies all other clients that player A is moving.

The computation of the path is deterministic, in the sense that the algorithm will always return the same path given the same pair of starting and ending coordinates, no matter what. In addition, since the obstacles in Phaser Quest do not move, a path is not at risk of changing during the movement, and therefore never needs to be updated.

On a side note, this has the advantage that when a player clicks to move, the client can immediately start the movement, without waiting for the validation of the server. If a genuine, non-cheating click was made, the pah will be correct. This is called client-side prediction and allows for a more responsive experience for the player. (If the provided path is illegal, e.g. because a player attempted to send a fake one via the console, the server will return an instruction to reset the position of the player.)

The deterministic nature of the pathfinding has the advantage that the server doesn’t need to broadcast the full path to the other clients. It can simply notify them that player A is moving to coordinates (x,y). Then, each client, upon receiving this information, will compute the path between the current position of A and the coordinates (x,y). Because this computation uses the same library and is deterministic, all clients can be trusted to compute the same path. This has two small advantages:
– Less data has to be sent by the server, since only the end point of the path needs to be sent to the clients, instead of the full path;
– The pathfinding computations are offset to the clients, leaving more resources to the server.

More importantly, using this approach, the server doesn’t need to send the position updates 30 times per second, because the clients already know how the player position will progress through time. In terms of movements, the only communication between server and clients is:
– Player A sends his path to the server, to notify it of the movement and to check that the move is legal;
– The server sends the endpoint of A’s path to all other clients.

js/server/Route.js

That’s it, one initial message and one single broadcast, for an optimal use of bandwidth and server CPU. The information about the path is added to the updatePacket introduced earlier, in the form of a Route object. This object contains properties such as the id of the moving player, the destination, what should be the orientation of the player at the end of the path (for when an action is performed at the end), etc.

Updating coordinates on the server

js/server/MovingEntity.js

Although this approach removes the need to send position updates 30 times per second, the server still has to keep track of the position of the player throughout his movement. Player and Monster objects inherit from the MovingEntity object.

Class hierarchy for the game objects on the server

This object has a method MovingEntity.updateWalk() which is called every 80ms (12 times per second) to update the coordinates on the server of any moving entity. This is done as shown below, based on the speed of the entity and the time elapsed since it started moving:

MovingEntity.prototype.updateWalk = function(){
    // Based on the speed of the entity and the time elapsed since it started moving along a path,
    // compute on which tile of the path it should be at this time. If path ended, check what should happen.
    // this.speed is the amount of time need to travel a distance of 1 tile;
    // delta = the number of tiles traveled since departure
    var delta = Math.ceil(Math.abs(Date.now() - this.route.departureTime)/this.speed); 
    var maxDelta = this.route.path.length-1;
    if(delta > maxDelta) delta = maxDelta;
    this.setAtDelta(delta); // Put at the right tile based on the computed delta
    if(delta == maxDelta){
        // ... do what has to be done when a player finishes his path
    }
};

MovingEntity.prototype.setAtDelta = function(delta){
    // Update the position of an entity by putting at the delta'th tile along its path (see updateWalk())
    if(!this.route.path) return;
    this.x = this.route.path[delta].x; // no -1 because it's done in updateWalk() already
    this.y = this.route.path[delta].y;
};

Correcting for latency

The main problem with the approach described so far is that the clients don’t receive the movement notification at the same time, depending on the time that the packets take to reach them. If player A clicks on a tile at t0 and has a latency of 20ms, the message will take 20ms to reach the server. From there, it might take another 30ms to reach player B, but it could take 150ms to reach player C because player C has a bad connection. The result is that player A’s character will reach his destination at time t1 on player A’s screen, but it will reach it at time t1+50 on B’s screen, and a time t1+170 on C’s screen. Such a situation is not appropriate, as it breaks the clients synchronization.

Latency breaks client synchronization

The solution to this is to keep track of each player’s latency, and then adjust the duration of the movement tweens accordingly. The latency of the moving player is added to the Route object containing the data relative to its movement. The latency of the player receiving the update is always part of each update packet. Here is a small version of the object that player B will receive to inform him that player A is moving:

{
  players:{
    1:{ // The id of player A is 1
      route:{
        end: {x:10,y:11},
        delta: 20 // delta is the latency of the moving player
      }
    }
  },
  ...
  latency: 30 // latency of the player who receives the update
}

Upon receiving this information, player B’s client will compute the path between player A’s position and the end point (10,11). Assuming that player A starts at (0,11), the length of the path will be 10 tiles. Players take 120ms to travel a distance of 1 tile, so the duration of the tween that will move player A from (0,11) to (10,10) will be 1200ms.

But as we now know, the server learned about A’s movement 20ms after it started, and B received the server’s notification 30ms after it was sent (this information is known to B as it is part of the update packet he received). In total, B was notified 20 + 30 = 50ms after A started moving. The natural fix is that on B’s side, the duration of the tween should be 50ms shorter, for a total of 1200 – 20 (A’s latency) – 30 (B’s latency) = 1150ms.

For player C, we said earlier that his latency was 150ms. In his case, the correction will be 1200 – 20 (A’s latency) – 150 (C’s latency) = 1030ms.

The result is that on the screens of the three players, A’s character will arrive at (10,11) at the same time, give or take a few milliseconds, thus achieving clients synchronization. Typically, such changes in tween duration are not very perceptible; either the tween lasts a long time, and a difference of even a few hundred milliseconds will be no difference, either the tween is short, and the tween will happen too fast anyway for a human observer to really perceive the difference.

Conclusion

This article explained the main ideas behind client synchronization in Phaser Quest. Hopefully, this might be food for thought for the design process of your own game. Keep in mind that this solution worked for this game, but might not work as is for other games; networking solutions always have to be tailored to the particular aspects of each game. In this case, the fixed environment, deterministic pathfinding and the low pace of the interactions were the key factors.

The delta packets concept is actually applicable to most games, as it is always better to encode differences in updates rather than full game states. For faster games, the rate of updates should simply be higher (up to 30 or 60 times per second).

For fast-paced games with dynamic environments, in would be necessary to transmit the coordinates of the players at a high rate (at least 10 times per second). The time intervals would probably become too small to apply the correction described here based on the tween duration; some form of client-side interpolation to smooth the movements could be required instead. I refer you to Gabriel Gambetta’s and Glenn Fiedler’s pages for nice readings about existing solutions.

In addition to this, Phaser Quest makes use of another optimization, which is the use of an interest management system. This one is usually considered a must, especially for massively multiplayer online games.

Jerome Renaux

I'm an independent game developer, working mainly on browser-based multiplayer online game (HTML5 & Javascript). I love to discuss about all aspects of game development so don't hesitate to get in touch!

More Posts

Follow Me:
Twitter

Jerome Renaux

I'm an independent game developer, working mainly on browser-based multiplayer online game (HTML5 & Javascript). I love to discuss about all aspects of game development so don't hesitate to get in touch!