Deterministic Lockstep

By Jules Tijburg – 500804340

A networking solution that requires very little bandwidth. A unique and intelligent way of sending data and to keep clients in sync. The same amount of packets being sent from, and to the server, regardless whether you control 1 unit, or 1.000.000 units. For this R&D, I will be researching and implementing deterministic lockstep.

Introduction

Around one and a half years ago, I worked on Hero’s Crucible for Game Studio. During that time I was assigned to work on the back-end with a few other people and one of our jobs was to improve the performance and stability of the multiplayer implementation. To do this, we wanted to implement deterministic lockstep with a new multiplayer framework, as the current one used (Photon) could not support this.

To do this we first had to research what deterministic lockstep was, and what multiplayer framework we were going to use. After doing so we started working on a prototype, but we weren’t successful because of the limited knowledge/experience and time. This time, I wanted to retry implementing deterministic lockstep, but on a smaller scale as I have a lot less time and people to work with.

Table of Contents

1.0 Lockstep

2.0 Deterministic lockstep

3.0 Implementation

• 3.1 Base game

• 3.2 Nakama Prototyping

• 3.3 Deterministic lockstep implementation

• 3.4 Input delay

4.0 Rollback

• 4.1 Rollback

5.0 Replay implementation

6.0 Future Thoughts

1.0 Lockstep

As it has been a while, I first had to do research on what deterministic lockstep exactly is and what features go along with it. I found multiple sites which explained this, but a certain site had an author which showed plenty of visuals which helped me understand it better. This is how the author visualized the basic form of lockstep:

The idea is that all players sent their update packet to every other player and wait to have received an update from every player, and then process them all at once. This update packet contains the action the player has executed. For example: “Sent move command for unit(s) to: x,y,z”. Usually, the position and rotation of a unit would just be constantly sent over the network to keep everything in sync, but with this technique it would be done with just one packet per action.

The challenge however is to keep every client exactly in sync as only actions are being sent over the network. The slightest change in a client can snowball to a huge change later on. Every client has to process every packet the same way, which seemed more challenging than one would think. Just having a non-deterministic physics engine (which Unity has), is more than enough to keep things out of sync.

This design also has some very obvious limitations, such as that the player needs to wait for every player to sent their update, so that will be addressed with deterministic lockstep.

2.0 Deterministic lockstep

Deterministic lockstep is visualized by the same author as followed:

This looks a bit chaotic, but the idea is as followed: Each player still sends their update packet, but this time it’s scheduled to be executed 3 ticks into the future. In the illustration above for example you can see that “Send input 4” is being sent before tick 1 is executed and that it only gets executed once the players arrive at tick 4. The advantage of this is, is that players no longer need to constantly wait for updates from other players, as they can be processed during the delay. To help the game feel more responsive with this delay, we make use of client side prediction and rollback, which I will cover later on.

For example, in the meantime input 5,6 and 7 could be processed before input 4 was even executed. The downside is that every action is delayed for 3 ticks. To visualize how useful deterministic lockstep is however, this is how it would like if one player is lagging:

Starting from input 6, player orange starts to lag. The packets arrive to player blue way later than the packets before, but it had no impact. Input 6 for example arrive at tick 5 for player blue, which is still in time for tick 6, this means that the game wouldn’t need to pause despite the lag. Even if this lag would continue throughout the entire game, it would still be unnoticeable and the lag can stop at any point to let player orange catch up again.

3.0 Implementation

3.1 Base game

To start off with, I wanted a simple “game” to work with so I can test the deterministic lockstep implementation with that. What I wanted was just a basic singular unit that can move around and attack another enemy unit. I want to implement this in a way where I structure the code in such a way that I can call a single function to perform an action.

For example, I want a MoveTo and Attack function. So that when I work on the multiplayer side and receive a packet, that I only need to execute the corresponding function on the right unit. This is how the implementation looks:

These functions are in a script called “Unit”. I made it so that if the unit isn’t in range to attack, that it first moves in range before performing the attack. For the movement, I decided to handle that in a different script. I did this because the current implementation is very simple (Vector3.MoveTowards), but in the future I need proper pathfinding. I didn’t want to use unity’s navmesh, because I read it is not deterministic, and could not find a quick other solution.

I made a script called “Input Handler”, which will process every input for now. At the moment I just want the user to make the unit move/attack with right so I implemented that in the script. I linked the unit and input handler by an event so the unit is controllable.

I made a simple unit for a cylinder and a cube, and gave it the unit component and tested it :

It’s a bit in the ground, but that’s easy to fix. I can’t test the attack with just one unit, so I was considering making a dummy target to test it out on. But I decided against it as I was fairly confident it does work, so I’ll test it once I have the multiplayer set up.

3.2 Nakama Prototyping

To start off with multiplayer, I decided to once again use the same multiplayer framework we decided to try with Hero’s Crucible. This multiplayer framework is called Nakama. One of reasons to use this is because you have access to the server-side code of it, unlike a framework like Photon. Having this is necessary to implement deterministic lockstep so I wanted to give it another try so I could form a proper opinion on it.

Nakama has a well documented page of how to get started with Nakama in Unity. They also have a YouTube tutorial series which not only describes how to set everything up, but also how to work with it. To get started with actually using it, I made a script to test out the features of Nakama.

In this temporary script I plan on implementing basic multiplayer features such as: creating a lobby, starting a match, being able to send packets and so on. It was fairly simple to create a match and connect with the server, but one thing that surprised me is that I have to manually keep track of which users leave and join.

To do this I have to subscribe to the “ReceivedMatchPresence” event from Nakama, which gets invoked everytime a player joins/leaves. I keep track of the users in the match in a list.

Next I have to create the a function that will start the match and instantiate a unit for every player. I loop through the player list and instantiate a gameobject for every player in that list. I also made some spawnpoints in the scene for the units to spawn on to.

I also made a “Team” enum so I know which units are enemies or allies. For my implementation it’s important that the players in the list are in the same order for both players, otherwise they would have a difference in assigned teams. Now I just need to let the other player know the match has started, which I can do with Nakama as followed:

The SendMatchStateAsync function sends a packet to every player in the match. The first parameter is the Id of the match, which I saved as a global variable. The second is an “Opcode” which is a unique identifier describing what kind of packet it is. This is how I defined the opcodes:

It unfortunately seemed I could not use an enum from this, as Nakama needs the opcode to be a “long” type. I could convert it but in existing Nakama projects, which are used as examples ,this is how they handle it.

The next step is to properly receive the packet. Nakama invokes the “ReceivedMatchState” event when a packet is received. I subscribe on that and handle the packet according to it’s opcode using a switch statement:

I think I got everything necessary to have everything working now, so I’ll test it out:

The players spawned in properly so that’s a good start. The next step is to allow the players to move. For now I just want to constantly send the position of a unit. This is how I sent the packet:

To send data, it has to be in string format, so I format it into JSON by using Nakama’s JsonWriter class. This is how I receive the packet:

To get a class instance from the JSON data I use Nakama’s JsonParser. After doing so I set the position of the unit to the given position. One issue I got stuck on for some time is that nothing would happen even if i properly received the packet. You can for example see the Debug.Log that says “Received…”, but the unit would not move.

After doing some research, and testing with try catches, it seems that Unity does not display errors from anything but the main thread. And when Nakama fires an event it’s not on the main thread. I found this out from using a try catch on almost everything, and the error was that a gameobject’s transform could not be accessed from outside the main thread. To fix this I made a “mainThreadCalls” queue of “Actions” and let them get executed in the Update function.

Now everything works as it should:

Now that I understand the basics of Nakama, I want to start actually working on implementing deterministic lockstep. The knowledge I have acquired will help me do this.

3.3 Deterministic lockstep implementation

The first step for me is to think of how I want to structure my code. Everything is currently in a “NakamaTest” file, which gets very messy very quickly. I want a structure of where every file has their own specific responsibility. I am for example thinking of separating the connection the server, the creation of a match, starting of a match, the different actions a player can take, etc…

The most important thing for me is to separate the different actions. I separate them by making each file subscribe to the input handler and socket. I call these files “Commands”. This is how I handle moving units now for example:

By directly subscribing to the input handler, I could also very easily achieve sending the actions of player over the network. Now I don’t need to constantly update the position of the unit, as I execute the MoveTo command on the unit as seen at the end of HandleMoveCommand. I also define the structure of every packet and how it should get serialized/deserialized. Serializing and deserializing means how I can format it into a string and how to get it back to a class instance from a string.

I call these “States” and this is how the PositionState looks like:

Now I every time I want to add an action that the players want to do, I just need to add a corresponding command and state. With adding the attack command however, I quickly ran into the issue of how I should know which unit was being targeted with the attack. Beforehand, I just synced the hp of the units, but I have to format the packets as an action now.

I tried to make use of GetInstanceId() on an object, but different clients give different id’s to gameobjects. The only solution I could think of is to let other clients know a unit is made alongside a certain generated id. Then every client stores each unit alongside that id so it can be accessed later. I made a CreateUnit command for this:

I generate an Id using Guid and sent a packet to every other client. When it’s received I instantiate the unit and I set the unit’s guid. I store every unit in a dictionary so that I can easily access it:

Now I can easily implement the attack command by sending over the guid of the unit in the packet and access it again from this list. I got the basics of deterministic lockstep done, now I want to implement the input delay I mentioned at the start.

3.4 Input delay

I now want to implement the input delay I mentioned at the start of this article. To start with this, I’d need a way to keep track of the current turn and even define how long turn lasts. I want this to happen server-side because I want to implement a client-server authoritative type of model, or a “dumb client” model. This means the client is fully dependent on the server to be functional, which among other things means it can’t make any important decisions itself. Handling the turn timer is part of this.

To start working with the server-side code of Nakama I had to choose the environment to work in. Nakama supports TypeScript, Lua and Go. From the documentation it seemed like most code examples were using TypeScript, so I chose that to work with as I have experience with JavaScript as well. I set everything up according to the documentation and video tutorials. I tried to test if it worked by logging “Hello World!” in the server console on start up:

That works fine, so now I want try to send the turn timer every x seconds. I had to do some research to figure this out, but it appears that I can register a match by name and connect it with related functions:

I define these functions in another script. They needed to have specific parameters which is documented on the website, so I made sure to match that. I also found out that in the “matchInit” function, I can define the tickrate of the server, which will also be the amount of turns per second. I chose 10 for now, so a single turn lasts 100ms:

The matchLoop functions get executed every tick, so I want to send a message every tick to let the client now a turn has passed. I can do this with the broadcastMessage function:

It automatically sends a message to every user in the match if I set the last parameter to null, which was very helpful. Now I just need to receive this message on the client side. I did research to find out how I could properly receive this message coming from the server and found out the ReceivedMatchState event gets invoked for this. I created a script that handles receiving these packets:

In the NakamaServerManager I store the current tick. I can use this so the clients can let the server know for which turn a packet is supposed to get executed for. Doing this was actually very easy with the way I structured my code. As mentioned before I use “States” to define the structure for the packet, so in the base State class I can define the turn the packet is for:

Now in every class that inherits from State, the tick to queue to is automatically in the packet. I wanted to test this out by reading this value from the server. I can do this in the matchLoop function as one of the parameters is “messages”, which contains all packets sent since the last tick.

It took some trial and error to figure out how the object is structured and how I could find the value, but managed to figure it out. I tested it and it seems to work fine. The next step is to schedule these packets for in the future. At first, I was planning to have a global array of an array of objects where the index represents the turn and contains all the packets that need to be executed. But that doesn’t seem to be possible in this environment, which makes sense because if multiple matches were to be running there could not be a single global variable.

To fix this I decided to save the packets in the database Nakama provides. The database works like a key-value system, alongside having a collection name. For the collection name, I decided to use the matchId and as key the turn index. This is how I visualize it:

Now I can easily read from the database, as I already know the matchId and what turn I want to receive messages from. To write to the database, I need to prepare a “StorageWriteRequest” and then call storageWrite():

Reading from the database is very similar:

I loop through the results I have received from my query and send a message to every user with the corresponding data of the packet. With this input delay and the basic form of deterministic lockstep implementation is finished.

4.0 Rollback

I still had some time left for the R&D project, so I decided to expand on the current implementation. One of the ways to combat the delay that comes with the input delay is to make use of client-side prediction. The idea is that instead of waiting to receive input from the players, we predict what their input would be and process the tick that way. Once we actually receive the input, we rollback to the tick we started predicting from and reprocess every tick till of when we started the rollback. I most likely will default the predictions to that the player has done nothing.

4.1 Rollback

I will start with implementing being able to rollback to a certain state. After doing research I found out the way to implement this is to save the state of the game at each turn. The game state for my game is currently defined by the units, as that’s the only way to influence the state of the game. So my first step is to save the necessary information of the units at each turn.

I also want this to be easy to apply to future unit’s and other things that could influence the game state. So I made a separate script called “RollbackSubscriber” which I can put on any gameobject of which I need to save information from:

I save the information in a dictionary where the key represents the turn and the value is a list of “RollbackSave”. This is just a class that holds information such as the position and rotation. I also already had an event for when a new turn has passed, which I could easily use to implement this.

Now that I have this information, all I need to do this is to make use of this information for when I want to rollback. The packet that will be sent will have the tick that the server wants to rollback to.

I wanted to test this by making a custom editor where I can send the rollback packet manually. This is the result of me rollbacking to a state where I was moving:

That worked fine so now I want the server to automatically detect if a packet arrived too late, and if so to rollback to the turn the packet was meant for. I also need to reprocess every tick that was between the tick we rollbacked to and where we last ended.

Doing this was the hardest part so far. I did not structure my code in a way that would make this easily achievable. I couldn’t simulate frames by making use of Unity’s Physics.Simulate(), as I don’t make use of Unity’s physics engine, so I implement something similar myself. I changed the movement code so that every FixedUpdate call, a function gets called that moves the unit if necessary. This function takes a fixedDeltaTime as parameter, which is how many seconds has passed since the last frame (should be 0.2 by default). Now I can manually call this function myself when I want to simulate the movement and can set the amount of time passed equal to a turn’s length (0.1s).

I test this by manually sending a packet that is destined to arrive late. The packet contains a movement command to move to 0,0,0 and is meant for tick 150, but we’ll send it around tick 170. By that time the unit should already be at the spot he was destined to move to.

This was an extreme example but it shows that it automatically calculates where the unit is supposed to be if the packet was late. It also works if it’s for example 2 ticks late, and it’ll put the unit on the correct position of the path it takes moving to the center. With this rollback is finished,

5.0 Replay implementation

One of the advantages of deterministic lockstep is that it should be somewhat easy to implement a replay system. This is because we already store the actions every player does at a given time, so all we need to do is read these actions from the database and execute them in order. My first step is fetch all these items from the database and then sort them in some kind of list.

To do this, I make a RPC endpoint from which I can download the replay from. The Unity Nakama library also offers to read from the database client-side, but since the owner of those rows of data in the database is the server, only the server can access them. The endpoint requires a matchid, which it will use to get the contents of a match.

It was relatively hard to convert the packet I receive into an object that I can actually work with. I had to make my own classes and had to set the properties exactly as the packet was structured. I figured out how the packet was structured by debug logging it and formatting it in a temporary .json file. This is how it looks:

I can now deserialize the packet just as before by making use of the “StorageItem” class. I sort them by using the OrderBy function from System.Linq. The next hurdle was to figure out how to execute these packets. The way I designed my code was that the commands subscribe to an event from Nakama to get executed. I can’t manually invoke the event so I had call the functions that subscribe to the event itself.

The issue was that it requires an “IMatchState” as parameter, which I could not make an instance of since it’s an interface. To solve this I inherited from the interface and basically tried to make a copy of what the original would be:

And I invoke the functions as followed:

I created the corresponding UI for the replay system and I managed to find the match that I used to playtest with the entire guild inside of the database. This is how it looks:

It was very fun to show this to the guild the next week after this match took place. It was also an opportunity to show those that weren’t present to show how to playtest went. The replay system is working as expected so this is complete.

6.0 Future Thoughts

From this project I have learned a lot, from understanding how deterministic lockstep works, to how to implement it and gained a better understanding of how the Nakama framework. If I had more time I would have loved to expand on the game by allowing you to control multiple units for example and to make my deterministic lockstep implementation support that. But this might be a thing for me in the future.

I unfortunately couldn’t see the full strength of deterministic lockstep, as you only control a single unit. It would’ve been cool to see it perform with a large amount of units as the network traffic would stay the same.

I think I did a good job of doing a lot of research on deterministic lockstep before beginning my project. The way I initially structured my code made it easier to implement sending inputs over the network for example. I just needed to call a single function on the correct unit when I received a packet. It was also really easy to expand on my code by making a lot of use of events and having a decent code structure.

It was also really helpful to allow myself to first create a small prototype with Nakama. By doing this I understood the basics of it and I didn’t frustrate myself by trying to learn two things at once (Nakama & Deterministic Lockstep. By doing this I also had a good code structure in mind because I have already worked with it. I looked at things were messy or “hard” to expand on and thought of ways to do that better.

In general I thought this was a fun and good learning experience and has motivated me to consider working on multiplayer games a bit more. I used to not really want to work with it as it gets really complicated / hard to work on, but I gained a bit of confidence working with multiplayer because of this project.

References

Age of Empires and networking – Sam’s space. (n.d.). Retrieved November 1, 2022, from https://samu.space/age-of-empires-and-networking/

Bettner, P. (2001, March 22). 1500 Archers on a 28.8: Network Programming in Age of Empires and Beyond. Game Developer. https://www.gamedeveloper.com/programming/1500-archers-on-a-28-8-network-programming-in-age-of-empires-and-beyond

Gao, Y. (2020, June 22). Netcode Concepts Part 3: Lockstep and Rollback – Yuan Gao (Meseta). Medium. https://meseta.medium.com/netcode-concepts-part-3-lockstep-and-rollback-f70e9297271

Multiplayer Game Programming: An Overview of Networked Games | A Brief History of Multiplayer Games | InformIT. (n.d.). Informit. Retrieved November 1, 2022, from https://www.informit.com/articles/article.aspx?p=2461064

Rollback Netcode – HVA GPE Game Lab – Fall 2020. (2021, January 17). https://summit-2021-sem1.game-lab.nl/2021/01/17/rollback-netcode/

Young, R. (2021, July). Rollback Netcode Explained. Game Rant. https://gamerant.com/rollback-netcode-explained/