I recently implemented cross-platform deterministic lockstep for a 2d project. I aim here to document the process and theory behind deterministic lockstep, as well as some of the specifics of implementing it in Unity. Most of the steps can also be applied to Unreal Engine but different fixed-point math, navigation, and physics libraries would need to be sourced.
Why/When should I use deterministic lockstep?
- Deterministic lockstep’s network usage scales purely with the number of players and their inputs. This means that games using deterministic lockstep can have a massive amount of units without putting any extra strain on the network. This comes with two major costs however. One, input needs to be delayed in order to build a buffer that can be used to prevent freezes if input isn’t received from another player in time for the next tick. Two, if any player has very poor ping or a generally unstable connection, with a deterministic lockstep model they will cause freezes for all the players. This makes it impossible to have a large number of players in a single match when using this networking model.
- Deterministic lockstep lends itself very well to peer-to-peer network architecture. There’s no strict need for any simulation to run on a server with deterministic lockstep. Because players only send inputs to each other it’s inherently very hard to cheat, at least in ways that directly alter the game state.
- Once the physics engine, navigation, and animation are ensured to be deterministic, and as long as fixed point math is used instead of regular floating point math in all game systems, there is in most cases very little extra work related to networking that needs to be done during development. Variables don’t need to be synced, and typically all that’s required is to use your overridden LockstepUpdate instead of the default Update (called at the appropriate time by your LockstepManager). Doing the initial work of ensuring that the core systems typically provided by the game engine are deterministic can, however, be highly time-consuming if existing libraries either already using fixed-point math or able to be easily converted to fixed-point math can’t be found. Race conditions can also cause desync and need to be avoided.
- Deterministic lockstep guarantees a frame-perfect sync between players. This is crucial for fighting games where moves have specific frame timings, although most modern fighting games use deterministic rollback now, which is effectively an extension/evolution of deterministic lockstep. We discuss deterministic rollback later in the article.
How do I ensure cross-platform determinism?
- Regular floats should be avoided when building cross-platform deterministic lockstep. Everything needs to use fixed-point math. This means most of the built-in systems relating to gameplay in your game engine of choice can’t be used, at least in the cases of Unity and Unreal. This includes animation with transitions, physics, navigation, etc. Anything that relies on floating point math. There are some ways that you can use floats with some very specific compiler settings, however that’s outside the scope of this article and I personally wouldn’t recommend it. Additionally, any race conditions in multi-threading can also cause a lack of determinism and subsequent desyncs. So, in the case of a 2d Unity game, what systems can we use instead of Unity’s defaults?
- Volatile Physics to handle deterministic collisions and collision querying: https://github.com/cathei/VolatilePhysics-FixedMath
- Dotsnav with all its math replaced with fixed-point math for navigation: https://github.com/dotsnav/dotsnav
- And finally Spritedow, a very simple sprite animator. https://assetstore.unity.com/packages/tools/sprite-management/spritedow-animator-82525 For sprite animation you have a lot of options and in cases where it’s not already deterministic it’s typically very easy to make it deterministic.
- From here we have all the core deterministic systems for a basic 2d game, which we can build on top of however we like (as long as we use fixed-point math instead of regular floats!)
Implementing deterministic lockstep
In deterministic lockstep the first thing you need to do when players are all ready to start the match is build an input buffer for each player. This is essentially a very short period of polling input and not doing anything with it. Once you have your base input buffer, the game is ready to start and the flow is going to look like this: For each player, each update loop:
- Have I (the player) sent my new inputs for the buffer to all other players? (Remember, the goal is to maintain a workable buffer of inputs at all times. We’re constantly adding to this buffer and taking from it. The player’s input is necessarily delayed). If not, I send them.
- Do I have the buffered inputs from every other player for the current tick? If yes, then the manager can send out its Lockstep Update event for the game to move to the next tick. If no, then the game freezes until we receive the inputs that we’re waiting for.
This is why a significant buffer of inputs and input delay is necessary. As long as everyone has decent ping and a stable connection, the input buffer should be large enough that we don’t need to freeze the game and everything can move smoothly. Sadly, this sometimes isn’t the case. Because of this, many games have started using deterministic rollback. In deterministic rollback, instead of freezing when we don’t have inputs for the next tick, we instead let the local clients predict forward using the last inputs they received. When the local client finally receives the real inputs we instantly rollback to where we first started predicting. Then, in the blink of an eye we simulate forward to the point where these received inputs brought us to, except in this forward simulation we combine the inputs that the local client performed while they were predicting with the inputs that we just received from the other remote player, instead of using the inputs the local client predicted we would receive from the remote player. From our players perspective they would typically see only a slight jitter or teleport, or no difference at all if the predicted inputs were correct or very close to correct. Deterministic rollback allows us to no longer delay input by such a substantial amount, or even necessarily delay it at all. A major downside to deterministic rollback is that rapid serialization and deserialization of all the game’s data becomes critical, which in certain types of games can become a substantial technical hurdle. Being able to simulate forward many frames in milliseconds also becomes very important, which is oftentimes an even larger hurdle. Using ECS instead of object-oriented programming can make both these hurdles much smaller, but it also forces a significantly different way of programming. For more information on deterministic rollback and ECS I highly recommend the GDC talk Blizzard gave on their implementation: https://www.gdcvault.com/play/1024001/-Overwatch-Gameplay-Architecture-and