Deterministic lockstep
Deterministic lockstep is a networking protocol for communication and synchronization. The key aspect to achieve deterministic behaviour is to allow sending only input across the network. All parties of communication can reproduce the state in a deterministic way by using the same input.
Lockstep protocol is a way to achieve consistency on both multiplayer parties. If your game is a fighting game for 2 players, lockstep represents the timeline with fixed steps along the way. Both players then keep sending input across the network and that input is applied at the same fixed time step.
In this example client0 is sending input on the 1st frame which gets delivered to client1 on the 3rd frame. This means that the client0 needs to wait for delivery to proceed with the local input. Same applies for client1, when sending a message on the 2nd frame we need to wait until it gets delivered to client1 at frame 7.
This is pretty much all what we need to send in a single frame across the network. Input can usually fit within 1 byte, frame can be up to maximum number of frames during the game.
Every frame message needs to be acknowledged by opposite network player.
Since UDP is not reliable network protocol we need to keep sending all un-acked frames until we get all Acks back. And then and only then we can consume the input and update the game.
Example:
If the UDP packet is lost on the way we still can recover it, because the next frame had it covered. In the worst case when all frames within synchronization window are lost, the frame is locked and we keep sending all 10 frames until they are acknowledged.
The total amount of frames sending in a single message ultimately depends on the size of the synchronization window. If for example size of the window is 10 frames, then the maximum amount of data in a single message would be:
Together with 10 Ack packets we would have to send maximum 90 bytes per frame. In a 60 FPS game it would mean to send around 5.4 Kilobytes per second which is pretty reasonable. This is however the worst case scenario, the data can be more packed and optimized for smaller throughput. For example we don't have to send 4 bytes of data just to identify the frame number since most of the frames could fit within a smaller space, etc.
This “waiting for delivery” explains the locking behaviour of this protocol. If the network conditions are suboptimal, the locked frame can drastically reduce the frame rate of the game.
Another important detail is that both clients start updating the timeline at the same time. Achieving and maintaining exact time synchronization can be difficult, so it is common to leave a synchronization window. An example would be to have a window with a size of 5 frames, where each frame represents 20 ms. Then both clients can be out of sync for at most 100 ms (or 5 frames).
Picking the right network protocol for the job.
This area is already pretty much covered by Glen Fiedler. While TCP represents the whole package and it is convenient to work with, during the packet loss the internal parts of the protocol can slow down the delivery significantly. On the other hand UDP is a freestyle (connection-less) protocol which does no extra work and it’s up to application to handle all the work that TCP does for free. With extra work we can leverage UDP and write custom messaging that fits our application need.TCP
- convenient to work with
- continuous stream of data
- ordered packets
- reliable packets
UDP
- connection-less protocol
- unordered packets
- unreliable packets
- unsecure
UDP and lockstep
The idea is to keep sending unreliable UDP packets every frame with input along with all previous frames until the opposite party sends acknowledged packet.struct Frame { uint32 frameID; byte input; }
This is pretty much all what we need to send in a single frame across the network. Input can usually fit within 1 byte, frame can be up to maximum number of frames during the game.
Every frame message needs to be acknowledged by opposite network player.
struct Ack { uint32 frameID; }
Since UDP is not reliable network protocol we need to keep sending all un-acked frames until we get all Acks back. And then and only then we can consume the input and update the game.
Example:
If the UDP packet is lost on the way we still can recover it, because the next frame had it covered. In the worst case when all frames within synchronization window are lost, the frame is locked and we keep sending all 10 frames until they are acknowledged.
The total amount of frames sending in a single message ultimately depends on the size of the synchronization window. If for example size of the window is 10 frames, then the maximum amount of data in a single message would be:
10 * (sizeof(uint32) + sizeof(byte)) = 50
Together with 10 Ack packets we would have to send maximum 90 bytes per frame. In a 60 FPS game it would mean to send around 5.4 Kilobytes per second which is pretty reasonable. This is however the worst case scenario, the data can be more packed and optimized for smaller throughput. For example we don't have to send 4 bytes of data just to identify the frame number since most of the frames could fit within a smaller space, etc.