Netcode Architectures Part 1: Lockstep
In the first part of this series, we’ll be taking a look at an architecture commonly referred to as “lockstep”. It is one of the earliest methods used for synchronizing gameplay on a network and is still frequently used today. Although this architecture comes in many flavors, we will focus on the most common implementation before discussing the prerequisites, limitations, and possible variants.
Architecture
In a lockstep architecture, each player sends their input to everyone else and then advances their simulation once they’ve received input from all players. That’s it! The game is fully synchronized over the Internet, uses very little bandwidth, and every player always sees events unfold the exact same way as everyone else.
An overview of the player experience and how it differs from local multiplayer can be seen in the following video:
Under the Hood
In the following video, you can see what this might look like for a 1v1 match where the players are connected directly to each other i.e., peer-to-peer without a dedicated server:
You can see that, although the players sample their input for frame 1 of the game immediately (and send it to the other player), the remote player’s input for frame 1 does not arrive until local input has already been sampled for frame 3. Once the remote player’s input for frame 1 is received, the game can advance and render the first tick of the match. Because multiple frames go by between when the input is sampled for frame 1 and when the result is executed and displayed, this results in input delay. In this specific example (and assuming zero jitter), the player will always see the result of pushing a button two frames after they’ve actually pushed it.
Note that in real-world conditions packet delivery is unreliable. Packets will arrive at irregular intervals—if they arrive at all. To compensate for this, the netcode must add additional delay as a buffer to weather these conditions. There will need to be a trade-off between added input delay and the risk of the game halting because the next remote input hasn’t yet been received.
Prerequisites
There are a few prerequisites that must be satisfied in order for a game to be compatible with a lockstep architecture.
Determinism
The primary requirement for a lockstep architecture is that the game simulation needs to maintain strict bitwise determinism. Since the netcode only synchronizes inputs, the game simulation must calculate identical results on each machine each frame given identical inputs. Otherwise, the game simulations will desynchronize, diverge, and drift apart, eventually resulting in games that look entirely different from one another.
This is typically a difficult prerequisite to satisfy and games need to be carefully architected to maintain determinism. Developers often checksum the game state each frame or at several points during a frame and compare those checksums between peers to help track down and fix sources of indeterminism when desynchronization occurs during playtesting.
Any game that makes use of floating-point arithmetic (i.e. most modern games) will need additional consideration. Glenn Fiedler’s article on floating-point determinism is a good starting point. If your game is cross-platform, floating-point determinism can be especially difficult to achieve due to differences between platforms and compilers. Each compiler may use a different set of instructions, reorder instructions, or perform automatic vectorization. Each system may implement transcendental functions such as cosine, sine, and tangent differently. All of these can lead to desynchronization between platforms or even between builds. Some developers implement their game simulation exclusively using fixed-point or software-emulated floating-point arithmetic to sidestep indeterminism arising from floating-point usage.
Other sources of indeterminism include generating random numbers with different seeds or processing items in different orders e.g., physics contacts. All of these considerations also greatly limit the third-party libraries that can be used as part of the game simulation such as collision detection libraries, physics engines, etc. As a result, it may be prohibitive for many game genres and engines.
Fixed Tick Rate
Lockstep requires that all players agree on the unit of time that each input and tick represents which means that the game will progress at a fixed tick rate. Some games lock the rendering frame rate to match the fixed tick rate of the simulation. Others allow rendering at an arbitrary frame rate and display an interpolation between the fixed tick results.
Challenges and Limitations
Although the lockstep architecture is one of the simplest and has no visual artifacts, there are a number of challenges and limitations. In some cases, these limitations can be overcome by making particular trade-offs in a game’s implementation. In other cases, these limitations may simply limit the viability of this architecture for a given game.
Input Delay
Lockstep prevents any visual artifacts due to latency by waiting until it has all the relevant information before advancing. The downside to this waiting is that there is a delay between when a player presses a button and when the result of that button press can be seen on screen. This delay is directly proportional to latency i.e., matches with higher latency will observe more input delay.
For many genres, such as real-time strategy games, input delay doesn’t negatively impact the experience very much. In other genres where controls need to feel responsive, such as fighting games and shooters, input delay is undesirable or even unacceptable. Depending on the genre, input delay is often a good reason to consider other netcode architectures.
Determinism
As described above, maintaining determinism is often difficult if not impossible for a given game. When discussing a lockstep architecture, most people assume a peer-to-peer topology where only inputs are transmitted as previously described. However, this doesn’t have to be the case. Consider a client-server topology where the clients send their inputs to the server, the server advances the game state once it receives inputs from all players, and then sends this newly calculated state back to all the clients:
The benefit of this variant is that determinism is no longer required. The server is the only one calculating the results of the next tick and clients simply display the results sent to them by the server. In fact, the clients don’t even need any of the simulation code! The downside, however, is that the entire game state needs to be transmitted and doing so efficiently is outside the scope of this article. Even with an efficient encoding, it requires significantly more bandwidth than just sending inputs and may be prohibitive depending on the game e.g., a sufficiently complex real-time strategy game with a high volume of units in motion.
Join in Progress
With a lockstep architecture it can be challenging to support players joining mid-match but there are a couple of options:
The first is that, if a full history of all inputs is maintained, then this history can be sent to the newly connecting client and the client can simulate all frames in sequence until reaching the current frame. This is difficult because the longer a match goes on, the more expensive this operation is in the memory to store the full history, the bandwidth to transmit it, and the time it takes to simulate all of those frames and catch up. If the CPU time to simulate a frame approaches the actual time step in real-time e.g., near 16.66ms to simulate a frame with a 60 Hz tick rate, the time for the client to catch up will be as long as the match up to this point!
The second option is to send the current game state to the connecting client. This is likely the best option but it means that developers need to implement a way to serialize the relevant game state, transmit it, and deserialize it on the other end. Because this code path is only used when joining in progress, it can be difficult to keep it operational and bug-free.
In either case, other clients may need to pause and wait for this new client to receive all the necessary data before they can continue which adds additional complexity to the system and may not be acceptable depending on the desired player experience.
3+ Players
Because the game only advances once input has been received from all players, input delay will be dictated by whichever player has the highest latency. This problem becomes exponentially worse as player count grows.
As a simplified example, let’s say that for any given match 90% of players have an acceptable network connection and the remaining 10% of players have what we consider to be a poor or unstable network connection. That gives us the following equation to determine the probability p that a match with n players has at least one player with a poor connection:
$$p = {1 - {0.9^n}}$$
In this scenario, in a 4 player match, roughly 35% of the matches will have significant input delay. In an 8 player match, it’s roughly 57% of matches!
Many developers attempt to solve this at the matchmaking level i.e., prevent players with high latency from joining in the first place. Unfortunately, connection quality tends to vary over time and so while the connection may seem acceptable when measured during matchmaking, it can often change during gameplay. This is especially the case with players who use an intermittent Wi-Fi or cellular connection.
One potential solution to this is to have players with high latency or poor connection quality apply more input delay than others. That way, other players are able to receive their inputs sooner and experience less input delay overall. Whether it makes sense to push the burden of latency to those with poorer connections in order to improve the experience of others is subjective and depends on the game design, genre, and desired overall experience.
Conclusion
Lockstep can be an excellent choice for networking games that are not particularly sensitive to input latency and can be made deterministic. This makes it a popular choice for real-time strategy games. Though many fighting games have used lockstep in the past, most modern fighting games utilize a rollback architecture that provides many of the same benefits but trades off accuracy and consistency for more responsive controls. To learn more about rollback, stay tuned for part two of this series!
Jay Mattis is a founder of High Horse Entertainment and author of SnapNet.
SnapNet delivers AAA netcode for real-time multiplayer games.
Additional Reading
Deterministic Lockstep
Glenn Fiedler
1500 Archers on a 28.8: Network Programming in Age of Empires and Beyond
Mark Terrano, Paul Bettner