Hello,

I’m creating a multiplayer game using the lockstep technique (i.e. deterministic, inputs are sent to the server, consolidated, and then back to clients). My game is similar to an RTS like WC3 / SC2 / AoE.

It’s working great so far; and, I’m now trying to reduce the latency, as my protocol has introduced ~200ms latency between the user issuing a command and it actually being executed - this is over and above network latency. I would like to remove it, and have a few ideas, but thought I would ask before undertaking them.

This is roughly how my protocol works (TCP part):

• User clicks to issue a command (e.g. tell a unit to move to a new location)
• Client sends a “command request” packet over TCP to the server
• Server takes this “command request”, combines it with requests from other clients (if there are any), gives it a sequence number and a designated “frame” (i.e. exactly which iteration of the lockstep engine it must be executed on) , and broadcasts it back to all clients
• Clients receive the commands(s), and execute them on exactly the specified frame in exactly the specified order

(note: I use my own fixed point library to guarantee determinism)

...so far so good: I get a round trip of about 10ms between the click and the command coming back from the server.

But you may notice an issue: what if the client has already proceeded past the designated “frame” of an incoming command? Presently I solve this as follows:

• A client cannot proceed to a frame unless it is certain there are no missed commands for previous frames. How?

(UDP part):

• Every 200 ms, the server broadcasts a packet containing 2 ints: (frameX, sequence number) to all clients
• This allows the clients to determine whether they have received all commands up to frameX. If they have, they commence, if not, they halt.

In order to ensure things look smooth (feel like 60fps) on the client, I need to run the client ~200ms behind.

Possible Solutions

Option 1 - More UDP

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?

Option 2 - Prediction & Roll back

This is a much more sophisticated solution.

Think of it this way: most of the time, it’s just fine for the client to assume that when it hasn’t received commands in the last ~ping ms, no commands were issued and it can commence its lockstep engine forward.

The problem is that if one TCP packet is delayed by 1 ms too much, the whole thing blows up because the client has made a wrong assumption and is now out of sync with the server and other clients.

This can be solved as follows:

• Keep snapshots of the full lockstep engine state every (let’s say 0.25 sec) for the past few seconds
• When the client realises it has made an incorrect assumption (i.e. it receives a command designated for a frame it has already proceeded past), it rolls back to a past state, then steps forward again up to real time executing all the commands on the correct frame
• ...and is back in sync again
• This should only happen by exception, as it will be costly to recover. So, dynamically adjust how far behind the client runs to ensure this condition is not being hit frequently
• Note this solution requires that I take a deep copy of the state very frequently. I would probably avoid using clone for performance reasons. I would probably achieve this without any garbage collection by cycling a number of cached copies, and by implementing my own deep copy for every game entity (i.e. it's a lot of work, and an on-going effort to maintain)

Note: this has a side-effect. On the occasions when the client gets it wrong and has to roll back, the player may briefly observe something that didn't happen. E.g. see a unit die, and then it suddenly is alive again.

Option 2 - You tell me

Any other techniques I’ve not thought of? Note - I need to stick with the lockstep technique because I have a lot of state / physics etc.

Additional information:

• I’m using Libgdx & Kryonet
• I’ve written my own Fixed Point library and physics engine on top of it to guarantee determinism on all machines
• By “lockstep engine” I'm referring to the deterministic world state of the game.
• I’m using the word “frame” to refer to an iteration of the lockstep engine. This doesn’t always correspond exactly to a render frame.
  
  

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.