Connect with us

Articles

Networking of a turn-based game

I’ve learned a lot while developing S&R, and I wanted to share some of the knowledge I’ve gained to people that might be interested in doing a similar project.

3 years ago, I started developing Swords & Ravens, an open-source online multi-player adaptation of a strategy board game I love, A Game of Thrones: The Board Game (Second Edition), designed by Christian T. Petersen and published by Fantasy Flight Games. As of Febuary 2022, around 500 players gather daily on the platform and more than 2000 games have been played since its release. While I stopped actively developping S&R, the platform is still seeing new features being added thanks to the work of the open-source community.

I’ve learned a lot while developing S&R, and I wanted to share some of the knowledge I’ve gained to people that might be interested in doing a similar project. There is a lot to say about how it works but this blog post will focus on how I’ve designed the networking part of the game. I’ll first describe the problem in a more formal way. I’ll continue by explaining how it’s solved in S&R, as well as describe other possible solutions that I’ve discovered or imagined. I’ll detail the advantages & disadvantages of each method and conclude with which method I think is the best (Spoiler alert: it’s the last one 👀).

Problem statement

In a single-player game, everything lives inside a single computer. The player’s actions are applied to the game state, and modifications to this game state are reflected on the screen of the player. In an online multiplayer environment, things are different. Each player is playing on its own computer, which all have their own current information about the game, and which all have their own UI to display the current state of the game.

The general architecture of an online game can be summarized with the following schema:

The UI displays to the player the current state of the game, based on the local copy of the state of the game. The Clients are responsible for the communication with the server, both to send the actions of the player and to receive new information about the game state.

The problem we’re interested in solving is how to synchronize the different local states of the game of the clients with the game state of the server. More specifically: when the server applies the action of a player to its game state, how must it communicate the modifications to the game state to the clients.

Update propagation method

The most obvious solution is to apply any action received by the server to the game and transmit the different updates to the state of the game to the clients. The following diagram shows it in action.

This is the method used by Swords & Ravens. It’s simple, intuitive and it’s easy to know which kind of data you’re sending or not to the different clients. This also makes it trivial to have secret data (i.e. data that should only be known to a subset of the players). If a player draws a card and place it in his (secret) hand, then you can transmit which card was drawn only to this player so that no other player knows which card it is.

The first downside to this method is that you must code all the possible updates to the state of your game. While there are certainly ways to automate this in JS using, for example, decorators to control the access to the variables of your game state, it may make your code less readable.

The second downside is that since you’re possibly sending multiple updates for a single action, the local game state of a client might temporarily be in an invalid state before all the updates have been received. In the diagram shown above, between the update Remove footman in Winterfell and Add footman in Kings’ Landing, there is a missing Footman which would modify the count of Footman shown in the UI. Though this particular issue could be solved by sending a combined update (for example Move Footman Footman from Winterfell to King’s Landing), not all updates can easily be concatenated.

A better way to address this would be to combine all the updates done because of the action and send them at once. This is essentially what the next method is about.

Delta-update propagation method

The delta-update propagation method works by computing the delta between the new state of the game and the state of the game before the action was applied. This delta is then sent to the clients so that they can apply it to their own local state of the game. This is how the game engine boardgame.io works.

This solves the 2 downsides described in the previous method. We no longer need to code all the possible updates, since once you change something, it will be computed in the delta after the action has been processed. You no longer get transient invalid states, since the updates will be applied at once, atomically.

One thing we’ve lost, though, is the easiness of managing secret state. If you want to prevent some secret information to be sent to a specific client, the server must filter the delta out of any potential private information before sending it to the clients.

Deterministic action propagation method

This method is inspired by the deterministic lockstep2 method used in online real-time games.

It relies on the assumption that processing the actions of a player is deterministic, meaning that for a given state of the game, applying an action will always give us the same resulting state of the game. We can exploit this property to avoid having to propagate the updates to the state of the game to the clients. Instead, the server can apply the action it has received from the client, and then propagate this action to the clients who can then apply the action to derive their own new game state. Since applying the action is deterministic, the clients will arrive at the same state of the game as the server.1

This solution has numerous advantages compared to the previous ones.

First, we don’t need to code additional network logic in our code. The only thing that needs to be implemented is the propagation of the action done by the players.

Secondly, bandwidth consumption isn’t tied to the size of the modifications done to the game state. If a single player action changes 1000 entities in our game state, the server will still only need to transmit the action and not the changes. This is actually the reason why deterministic lockstep is used for real-time strategy games, such as Age of Empires. While it is quite uncommon for turn-based games (even less so for board games) to have lots of moving entities when performing an action, having this opens up new possibilities for turn-based games.

Thirdly, since the actual gameplay code is run on the client, we can perform animations of the different updates done to the game state. For example, if a player action would reduce their amount of money by 10 and then raise it by 40, we could play 2 different animations client-side while with the previous solution, we would only receive from the server the fact that the amount of money was raised by 30, preventing the client from doing so.

Fourthly, when the player decides to perform an action, the client can directly apply the action to its own game state after sending it to the server without waiting for confirmation from the server. This process, called “optimistic update”, allows us to provide a lag-free experience to the players.

Overall, this solution is quite elegant. We just need to implement the propagation of the actions of the player and once it’s done, ta-da, we can focus on implementing the gameplay and don’t need to touch the networking code at all!

There is one big downside, though. To make sure that the clients and the server arrives at the same game state after processing an action, we must ensure that they both possess exactly the same game state initially. At first, this might make you think that it would be impossible to have secret state. Indeed, how could we have state that is only kept server-side if our networking solution relies on the game state being the same between all actors?

Handling secret state

We can solve this issue quite elegantly by allowing the clients to slightly differ from the server. If an action requires state that was previously hidden to one or multiple clients, we can make the server reconciliates the difference by sending this specific part of the game state to the clients.

Let’s illustrate this with an example from Swords & Ravens. When a player moves their army into the territory of another player, they trigger a combat. Resolving a combat in S&R involves both players simultaneously choosing, from their hand, a general of their house to lead their armies. This mechanic leads to intense mind-games where both players try to guess which general their opponent will take so they can pick the appropriate counter, while wondering if their opponent will not plan for this and take the counter of the counter, requiring you to pick the counter of the counter of the counter, and so on.

Obviously, it is important to keep secret the choice of one of the opposing players if the other player has not made their choice yet.

The following diagram explains how we could solve this.

When Client A sends their action to the server (Choosing Tywin Lannister), we propagate this action to both players, but not before filtering the chosen leader out of the message sent to Client B. At this point, Client B’s game state differs from Server’s game state since it does not know which leader A has chosen. When Client B sends their action (Choosing Margaery Tyrell), we apply the same logic and filter out the chosen leader out of the message sent to Client A. Since both players have chosen their leaders, we can reconciliate the differences in game state by sending out the choice of the other players. After this little manoeuver, all clients have the same game state and can resolve the rest of the combat deterministically.

Note that while we could have opted not to send anything to Client B after A had chosen their leader, sending this information makes it possible to display in the UI of B that A has already chosen their leader.

Conclusion

If I had to develop Swords & Ravens from scratch, I would do it using a deterministic method. Having to implement the networking only once, and be done with it, is quite elegant and appealing. Since AGoT:TBG is quite a complex game with a lot of different phases, having to network every interaction produced a lot of boilerplate code, which amounts to a big portion of the code. On top of that, I never managed to easily add animations (pieces moving, cards moving from hand to board, …) to the UI, which does not help a lot with AGoT:TBG where a single action can have a lot of state updates.

Another nice thing about using a deterministic method is that you can easily make a library that handles all the networking part of a turn-based game, letting the developer focus on developing the mechanics of the game itself. I’ve started working on such a library, Ravens. Unfortunately, due to external circumstances, I have not continued developing it.

If you’re actually in the process of implementing a turn-based multiplayer game, I hope that this article was able to help you on choosing a sound architecture. If not, then I hope the content and the writing was interesting enough!

Full Article: Longwelwind
Feb 2, 2022
Advertisement

Trending