Lockstep Protocol for Multiplayer - Reducing Latency

P.S. I would love to know how Wc3/SC2 does it, as these games are perfection in my view.

I'm guessing that they don't use option 2) because I have never seen the aforementioned side effect despite thousands of hours of play (though admittedly I have an exceptionally stable internet connection).

I'm pretty sure Clash Royale does do something like option 2) as I have observed exactly the type of side effects I've mentioned when playing it.

I believe it would be better for you to do your Option 2 (Prediction & Rollback). But, just saying I don't know much about this stuff, so this is just what I think would work the best.

Also, what is the name of the game? I would also like to know when the game is going to come out? And where is it going to come out on, like what website, if it is going to be on pc, if it isn't going to be on pc, then what will it be on?

browse through here: https://gamedev.net/forums/topic/708348-rollback-prediction-management/​

see if it guides u a bit or not;

I could optimise the hell out of my UDP packet (i.e. get it down to a handful of bits) and send it ~60 times per second. (i.e. twelve times as many UDP packets)

This might work, but I’m not sure it’s a good solution. It seems like a lot of UDP packets (though this is a gut feeling rather than based on any evidence or experience). This is where some guidance would be helpful. Is it normal for games to send packets at this sort of frequency?

This is where some guidance would be helpful. Is it normal for games to send packets at this sort of frequency?

not sure if u know, but first of all, with udp the max throughput is when there's no tcp on the same wire;

secondly, this max sending of udp (or tcp) data frequency is constrained by network layout (hops) and bandwidth (mbps);

so with these 2 points in mind, if u can fit 60hz-worth of data into an X mbps wire then you only need to watch out for how far this data is going to live. Usually after N number of hops, UDP throughput falls. I leave it as an exercise for u to work it out ?

i have seen sent 25hz to 50hz worth of udp timecoded datagrams from a server serving upto 12 udp channels in parallel on 10mbps/100mbps/1gbps based networks. Hardly observed significant drops (tcp was used to initially connect clients to this server then once established dropped to favour udp comms)

Having said all this, i can't tell you whether to choose Option 1 or 2… i think you'll have to work out what is best for your engine/game in test

Have fun ?

Reads for me as if your problems stem from sending commands without them being bound to a step?

IIRC the model I read about was:

- every client knows current step and collects commands for step+x in future and always sends one packet with all commands for that

- show some animation and sound so player thinks its done immediately, but don't move the units

- server collects/saves all command packets for the future, waits until packets for next step from all clients are there, sends one packet with all commands to all clients, advances step number

- client should get the server packet for next step just in time or a bit earlier (otherwise wait with stepping time) for movement between step and step+1

- if there is waits, x might need to be increased, some games did this on the fly, but that complicates everything

Thanks for the help.

browse through here: https://gamedev.net/forums/topic/708348-rollback-prediction-management/

Wow, I'm shocked (in a good way) to hear that ggpo is a thing, and it's basically identical to my proposed solution above (option 2). This is great, because it's evidence that it will probably work. It takes my suggestion a little further in that it uses local input to make predictions, but this is a direction that I considered as an extension anyway.

I can see how it’s a particularly effective solution for getting a feeling of near zero latency when user input is highly predictable, like in a fighting game.

...however, I’m not convinced that this is the solution used by Wc3 / Sc2.

I managed to find an article on Sc2 network traffic, and apparently the client sends / receives UDP packets at approximately 16Hz (that’s one every 60ms).

So, as a compromise for now, I’ve upped my UDP packet protocol from once every 200ms to once every 60ms… which, with a bit of client-side eye candy for immediate feedback, makes the game feel pretty good.

To optimise to the next level I’ll likely do the following:

• I will do something like my original proposal (option 2 in OP) rather than full ggpo. So, allow 2-3 lockstep frames of rollback, allowing the client to proceed unhindered by the delay in the UDP “keep going” packets.
• Consider removing the TCP and doing everything over UDP with a very basic retry protocol on top of UDP for the commands

Reads for me as if your problems stem from sending commands without them being bound to a step?

The thing is, bounding commands to a future step is exactly the same as the problem I’m trying to eliminate. I.e. latency between issuing a command, and seeing it happen. So, I don’t think not doing this is the source of the problem.

That said, I think that bounding command requests to a future step could be part of a good ggpo-style solution, where the client may be running a few frames ahead locally, and so the input being bound to a future step feels immediate because it’s applied immediately as a local “prediction”. I’ve not articulated that very well. :) Basically, I think you have a point, and it’s something to consider if I go further down the ggpo route.

Wc3/SC2

These games could have more than 200 ms latency and still work fine. The reason you don't notice, is that the units play an acknowledgement animation ("Yes, sir!") locally before they actually start moving in the game simulation. That animation is long enough to mask the latency before you get to the appropriate tick number to actually start executing.

allow 2-3 lockstep frames of rollback

Rollback is incompatible with lockstep. Rollback is used for a different model – baselining and prediction. If you do lockstep, you never roll back, ever. You queue commands to start taking effect at some future execution tick, typically “current tick plus round-trip time plus one.” You send those commands to everyone else. When you've received “my commands (if any) for tick X are …” from each other player, you execute tick X. If it takes longer than normal to get commands for tick X, you stop simulating. (Things on the screen can still animate, but the deterministic simulation doesn't progress.)

If you want to see the command “right away,” then you should not use lockstep unless the command can be animated locally on the screen before it's actually simulated. There are many kinds of animations you can run – if you shoot a weapon, you can show the muzzle flash, and the smoke, and play the sound. Whether you actually hit and do damage, will be shown once the simulation happens. Think of it as weapon travel time. If you think about it, you can probably figure out animations that take enough time to “acknowledge” and “wind up” and “initiate” each command, without having to know the outcome when you start it.

It's totally OK to have more ticks than you have packets – have ticks every 16.7 milliseconds, send packets every 50 milliseconds, including three separate ticks per packet. If you want lower latency, send packets more often, without having to update your simulation rate. It's also totally OK to include commands for the last few ticks in each packet, on the off chance that a single packet gets lost – the recipient can then “catch up” when they get the next packet. That being said, single packet loss is pretty rare – typically, you'll get many packets lost, or a single packet delayed, given the way current networking hardware actually works. But, on a bad day, or bad WiFi of the “right” kind, it's totally possible to still see occasional packets dropped.

These games could have more than 200 ms latency and still work fine. The reason you don't notice, is that the units play an acknowledgement animation ("Yes, sir!") locally before they actually start moving in the game simulation. That animation is long enough to mask the latency before you get to the appropriate tick number to actually start executing.

Yes , I'm well aware of the local immediate visual feedback to mask latency. ? As a diamond league Wc3/Sc2 player who always plays with ping diagnostics visible, I can tell you that you definitely notice > 100ms ping if you're playing competitively. Sure, you get the immediate visual/audio feedback, but infuriatingly things don't move!

Typically, Wc3/Sc2 run at <40ms ping for me, which usually translates to <100ms latency on commands (I would estimate).

Rollback is incompatible with lockstep. Rollback is used for a different model – baselining and prediction. If you do lockstep, you never roll back, ever. You queue commands to start taking effect at some future execution tick, typically “current tick plus round-trip time plus one.” You send those commands to everyone else. When you've received “my commands (if any) for tick X are …” from each other player, you execute tick X. If it takes longer than normal to get commands for tick X, you stop simulating. (Things on the screen can still animate, but the deterministic simulation doesn't progress.)

If lockstep is, by definition, incompatible with rollback then perhaps I'm not using the correct term. By lockstep, I mean a deterministic sim run on all clients (and server, as adjudicator), as described in the original post , with identical streams of input. There is no peer-to-peer, in the same way that Wc3/SC2 does not have peer-to-peer - all communication happens via the server.

I disagree that rollback does not have a part to play in this model. I think what you're talking about using rollback to allow immediate prediction of local state by predicting user commands. This is not what I'm trying to do.

hplus0603 said:
If you want lower latency, send packets more often

This is exactly my point: this need not be the case. There is a variant of lockstep (using rollback) where command latency is not bound by packet frequency but rather by network latency, as described in my OP.

The “prediction” is not a prediction of user input, it is a prediction that there has been no spike in network latency. Usually this prediction is going to be correct and the client will be perfectly in sync despite not being 100% certain. When the prediction is incorrect, we need rollback to get our deterministic world state back in sync.

If this is, by definition, not lockstep, then we need a new word. ? …though I really do think that it is still lockstep, as ultimately each client has the total world state and receives a stream of all input, even if there is a bit of rollback magic sprinkled on top to allow lower latency.

james_lohr said:

If lockstep is, by definition, incompatible with rollback then perhaps I'm not using the correct term. By lockstep, I mean a deterministic sim run on all clients (and server, as adjudicator), as described in the original post , with identical streams of input. There is no peer-to-peer, in the same way that Wc3/SC2 does not have peer-to-peer - all communication happens via the server.

…

If this is, by definition, not lockstep, then we need a new word. ? …though I really do think that it is still lockstep, as ultimately each client has the total world state and receives a stream of all input, even if there is a bit of rollback magic sprinkled on top to allow lower latency.

The confusion comes from most of the games networking world associating “lockstep” with deterministic lockstep, while some devs (fighting game devs in particular) associate the word with asynchronous lockstep, or sometimes with approaches that aren't lockstep at all. We're at an odd stage of games networking where the approaches are mature but the communication and language isn't yet, e.g. this medium article lumps the concepts of peer to peer topologies and deterministic lockstep into the term “lockstep”. It's worth noting that peer to peer vs client/server has nothing to do with this, you can have lockstep and non-lockstep approaches in either topology.

Your “Option 2” isn't lockstep (clients never wait for a tick to be fully resolved before proceeding). What it actually is called depends on some more details, but it's in the class of approaches where the clients aren't in lockstep, thus can be slightly ahead or behind eachother, and the server has to sort out what happens when.

In this class of approaches, there's a dichotomy of synchronized vs spontaneous. Synchronized approaches typically work with reference to a tick--some take client inputs and immediately apply them to the next tick, others make the clients tell the server what tick an input should be processed on and drop late inputs. Spontaneously enmeshed approaches are for things like chat servers, where the ordering doesn't matter as long as all of the state updates eventually occur.

There's another dichotomy between sending state to consumers vs sending inputs. I haven't thought about it much since I only do MMO dev (clients send inputs, server sends state), but RTS typically send inputs both ways afaik.

Now, with all that out of the way, on to what you should do. SC1 seems to use deterministic lockstep, where the experience is determined by “turn rate” (you can see the turn rate in online matches, it varies with connection quality). SC2 seems to also use a deterministic lockstep (you can see in this video that units pause during lag instead of continuing to move and rubberbanding), but the way they handle delay seems to be different. I'll leave a more thorough analysis as an exercise for you, though.

Deterministic lockstep is probably the way to go, since RTS players are more used to bad connections being characterized by lagged inputs and stuttering than by misprediction and rubberbanding. With that, your goal would be to optimize network latency, and to find any presentation-level tricks you can do for your particular game to mask latency. Maybe you can do some slight prediction, on the order of a single network tick or something, and play everything X ticks in the past.

Edit: That SC2 lag video I linked seems to have been a driver issue, not network lag. Iirc, lag in online matches behaves the same though.

james_lohr said:

If this is, by definition, not lockstep, then we need a new word. ? …though I really do think that it is still lockstep, as ultimately each client has the total world state and receives a stream of all input, even if there is a bit of rollback magic sprinkled on top to allow lower latency.

The point of lockstep is that every client does exactly the same thing, in lockstep. There is never a need to rollback because everybody already has the same state.

Almost all games have a deterministic “input → simulation → output” process, but that is not what makes it lockstep - the lockstep aspect is that all simulations in the network apply the same input to the same simulation, and thereby get the same outputs.

Normally RTS games are robust in the face of one client experiencing a bit of lag because it just means that their own input gets delayed slightly. No need for any prediction or rollback.

This seems to be a problem that has come from trying to use FPS networking mechanics in an RTS context.

This seems to be a problem that has come from trying to use FPS networking mechanics in an RTS context.

Not really, this “problem” has come about from me seeking to reduce the latency that comes with lockstep. Ordinarily, when using lockstep, command latency is bound by packet frequency. I'm seeking to break this constraint.

Almost all games have a deterministic “input → simulation → output” process, but that is not what makes it lockstep - the lockstep aspect is that all simulations in the network apply the same input to the same simulation, and thereby get the same outputs.

I literally, right now, have a classic lockstep engine, as described in the OP, where all clients (and the server for that matter) have identical state, and an identical sequence of commands is executed on all of them. There is no rollback, because, as you say, it's not required.

However, I have spotted an opportunity to reduce command latency further by introducing rollback (as described in OP).

Normally RTS games are robust in the face of one client experiencing a bit of lag because it just means that their own input gets delayed slightly. No need for any prediction or rollback.

Yes, yes, this is exactly what I have now; however, the latency optimisation introduces the need for rollback.

So, in essence, I'm left with something that is exactly like a classic client-server lockstep i.e.
1) The latency of a command round trip (to the sever and back again) is masked by immediate local feedback
2) Large spikes in lag will result in a delay to the commands and the game “halting”
3) (Except in exceptional circumstances), no rollback is happening and all clients are executing an identical sequence of commands on identical world state

The difference is that:

1) I'll have shaved off 30-100ms off command latency. (Some might argue the price of implementing rollback is not worth it, but as a eSporter I disagree)
2) Rollback will occur when latency spikes happen. This may come with minor visual (a few frames at most) rubber banding before the client halts


I think I'm continuing to suffer being caught between two definitions.

james_lohr said:

I think I'm continuing to suffer being caught between two definitions.

Then ignore the semantics and get to the meat. As I was hinting at in my other reply, it really isn't an unsolved problem. Look at existing games, see how they do things, then ask targeted questions.

SC1/SC2 (and probably most RTS) seem to work only with known data (lag == pause). MOBAs, iirc, use prediction (lag == extrapolated movement). You can run through the steps of doing something different, but it's at least worth questioning why those decisions were made before reinventing the wheel. For an RTS, how does SC mask latency, despite working only with known data? What is the input delay? Does the input delay vary? etc etc

If you have a traditional deterministic lockstep implementation and it performs worse than existing RTS that seem to use the same approach, the next step would be to experimentally determine what they're doing better than you, not to start off in a separate direction. You could also question whether they are actually using a deterministic lockstep implementation, and see if you can find contrary evidence.

If you have a traditional deterministic lockstep implementation and it performs worse than existing RTS that seem to use the same approach, the next step would be to experimentally determine what they're doing better than you, not to start off in a separate direction. You could also question whether they are actually using a deterministic lockstep implementation, and see if you can find contrary evidence.

I was able to achieve similar performance to SC2/WC2 by upping my packet frequency from every 200ms to every 60ms.

However, I believe that I can achieve better performance (and less traffic) with option 2.). So, I'm now in the process of implementing it. We'll see what results I get. Perhaps it'll fall flat on its face.

SC1/SC2 (and probably most RTS) seem to work only with known data (lag == pause). MOBAs, iirc, use prediction (lag == extrapolated movement). You can run through the steps of doing something different, but it's at least worth questioning why those decisions were made before reinventing the wheel.

SC2/WC3 use lockstep because of the huge amount of state, and because the nature of the game (controlling many units, performing macro alongside micro, and queuing up actions) is such that a bit of extra latency is not a big deal.

The original MOBAs were lockstep (they were custom maps on SC1 and Wc3) so they used lockstep. Recent MOBAs probably use prediction because generally it provides:

1) Lower latency (you're controlling a single unit, so you really care a lot about latency)
2) Better security (can't map-hack)
3) Easier to implement (no need for strict determinism)

I'm basically going for a hybrid because I want the best of both worlds:
1) Lots of state
2) Low latency

Hi i am too interested in making a RTS game, tough i am totally newbie in multiplayer. Have read this tread so at least i know direction i should go but am also interested how your hybrid worked out so please share ?