RTS Lockstep: How to deal with high latency and packet drops?

Question

In the lockstep RTS model, I understand how games can be made deterministic by sending across commands to run at designated frames in the future. Then, to keep everyone in sync, confirmations are sent back to confirm that the commands were properly received. If the confirmations wasn't received, the command wouldn't run and the game would pause.

My question is how do I keep the confirmation frames in sync? Given at least 2 players i.e. Player_A and Player_B:

It's entirely possible that Player_A might receive confirmation from Player_B but Player_B wouldn't from Player_A, so Player_A would run the command while Player_B would pause and be out of sync. How can this be dealt with? Confirmation for the confirmations?

Answer 1

I highly recommend you study the TCP model; it is very mature and has many features built in over the years, making it a jack-of-all-trades networking protocol. It will likely have features that address any follow-up concerns you may have.

The scenario you describe is also known as packet loss; Player_A has sent a confirmation to Player_B but Player_B hasn't received it; it may have been lost or delayed. There are a few ways to solve this; the method TCP uses (and is described in this SO question) is retransmission. Since Player_B is expecting a confirmation but hasn't received it, after a while it assumes that its original message was lost, so it retransmits that message. Player_A will see a duplicate message, and send the confirmation (a.k.a. acknowledgement). This process will repeat until the confirmation makes it to Player_B and the world can continue.

The specifics can be quite complex; for example, the amount of time Player_B waits until retransmission - the retransmission timeout - loosely depends on round-trip time; retransmission rates aren't constant, as TCP has a mechanism to throttle back in case the problem is congestion, and retransmitting duplicate packets would worsen the problem. You don't have to worry about any of this if your game uses TCP, but if you don't then it's helpful to look at TCP and how it solves these problems. Just be aware that you may end up re-inventing TCP.

Answer 2

It's been a while but I thought I'd answer for posterity.

The algorithm is simply:

• Each player sends his commands to all other players every turn. (If they have nothing to order in particular, the message could just say "I have 0 commands for turn X".)
• Each player waits for all other players' commands before executing the current turn.

So in the described scenario where PlayerA receives PlayerB's commands, but PlayerB does not receive PlayerA's commands, PlayerA executes the current turn, and then waits for PlayerB's commands before executing the next turn. Meanwhile, PlayerB is still waiting on PlayerA before executing the current turn. Since he is stuck at this turn, he won't be sending commands for the next one, and PlayerA will have to wait. The game is effectively paused for everyone until PlayerB gets the commands it is missing.

As this scenario illustrates (PlayerA is done executing the current turn, PlayerB hasn't), it is possible players aren't executing the same turns simultaneously; the synchronicity does not consist in simultaneity but that all players execute the same commands on the same turns.

The Baldur's Gate manual (Baldur's Gate is based on what was designed as an RTS engine originally) stated this:

Baldur’s Gate is an asynchronous game. If you happen to be playing with some body whose system is very close by, you still might see slightly different things happen on each system. The point to remember is that while things happen somewhat differently, the result of the actions is always the same.