Written by Krystian Jarmicki
Published August 28, 2017

Developing Lag Compensated Multiplayer Game, pt. 4: The Lag Compensation

After we’ve dealt with setting up the server and the client, there’s one last thing to do in order to make the game smooth: how to compensate lags between them.

How to lag compensate java/libgdx game

This is the fourth and final part of the series that will show you how to make a lag compensated multiplayer mode for the arcade classic. In case you missed the previous ones, you can check them out below:

The Lag Compensation

Render-only client, that we came up with in the previous part, works nicely when network latency is close to 0, but that’s almost never the case on the internet. There’s no way to avoid lags, by the sheer laws of physics. Even in a perfect world, if you’d have an optical fiber connection set up between, say, Los Angeles and New York and your signal traveled at the speed of light, you’d still have latencies of about 13ms. Now add a bunch of network hops with all kinds of bridges, routers, gateways, proxies and whatnot and you’re realistically looking at 100ms lag at best, all the way up to barely playable 300+ms. It may not sound like much, but I’ll demonstrate to you that in fact, it is.

Introducing delays

We’ll make a class that lets us perform delayed actions. It will be capable of creating instances bound to a specific amount of delay time. By default we’ll use daemon threads for that, because we don’t care for delayed tasks after main thread has returned.
If we created this class, we wouldn’t know anything about the types of tasks that it will perform. We’ll put it in general core/util package.

Now let’s hook it up to both the SocketIoClient and the SocketIoServer:

We’ll inject both Delays with 100ms amount of time in AsteroidsServerGame and AsteroidsClientGame:

Combined delays along with cross-process communication, game loop computation lag etc. will sum up to about 210ms. Run the game and try to play it.

It’s quite awful, right? Well, it should be. 200+ms is a noticeable delay between a key press and things actually happening, and it’s super frustrating when you’re trying to shoot an enemy and he flees before the delayed bullet reaches him. But we’ll alleviate that.

General approach

There are three entity types that we can apply lag compensation techniques for: the local Player, other Players and Bullets. These techniques will differ in details, but they’ll also share a fundamental pattern: due to network latencies we cannot know the exact state of the entity when we need to render it, but we can give it our best guess and apply corrections later, if needed. In other words, we’re going to pretend that we know how things are, show that, hope our bluff isn’t way off, and if it is, fix it as soon as possible.
Before you move on, I highly recommend you read the excellent series on developing fast-paced multiplayer games by Gabriel Gambetta. A lot of techniques shown here will be implementations of concepts described there.

Players lag compensation

Lag compensation for a local Player is most likely to match the actual state because we have most data to do it correctly. Here’s the gist: we’ll continue to calculate Player‘s position based on Controls as if it was purely local and eventually reconcile state with the server response. Given that we’ll run the same game logic and physics on the client, and the server and there’ll be no randomness involved, we should be able to come up with correct position most of the time and the server will just confirm that. An exception might be a situation when Player was shot down, and we haven’t received its new position yet.

Local controls

Ok, so right now with the server calculating all the game logic and the client only rendering it we have something like this:

no compensation

But we really want the server to only confirm local state, so it can look seamless:

local controls compensation

That should be easy enough, right? We’ll just make localPlayer use localControls and then server state will be just confirmation of what we already have on the client side. Let’s do just that.

First, we’ll pass localControls rather than new NoopControls() when Player connects in AsteroidsClientScreen:

And we’ll also update playersContainer in the render in order to apply controls, right after they’re sent to the server:

Now let’s run the game and check out how our newly developed compensation works.

Well, does it? Nope, not at all. There’s hardly any change and now the ship is doing a weird little dance of going forward and backward before it finally moves.

The reason for that is we’re constantly updating based on the state from the server, but this state is from the past. By the time the server receives client input, processes it and sends it back it’s a whole other situation on the client side, but this past state gets accepted and applied. Let’s zoom in a bit on previous flow to get a better grasp of it:

bad compensation

To address this issue we’ll have to treat the server’s response as both validation of past state for everything that we can compute locally (like Player’s or Bullet’s next position), and as an update on everything that we can’t compute locally (like new Bullet being shot by other Player or new spawn position for the Ship).In order to achieve that we’ll need to keep indexed states locally – state 1, state 2, state N – and refer to them whenever server responds to check if our past state N is the same as server’s just received state N. If so then great, we can just move on, as illustrated below:

good compensation

From the client’s perspective:

  • At state 0 Ship was at 0x, 0y and the player pressed key up
  • At state 1 Ship moved to 0x, 1y
  • At state 2 nothing significant happened
  • At state 3 the client received server’s state 0, which said that Ship was then at 0x, y0
  • At state 4 the client received server’s state 1, which said that Ship was then at 0x, 1y

All the client states saved locally matched states sent by the server, so for the player it looked like the game was instantly responsive, even though it took 200ms for a whole state roundtrip and validation. That’s a win.

But what if there was a difference in states? Let’s say that due to some glitch one player’s render loop is called with slightly higher delta than others, resulting in a faster-perceived Ship movement – so every time he presses an arrow he locally goes forward not 1, but 1.5 unit. Of course, the server is oblivious to that, as it should be, but how is it going to get reconciled on the client side?

rerun compensation

…so in the end, Ship is at 2.5y at the client side. Wait, what? How did that happen?

  • At state 0 Ship was at 0x, 0y and the player pressed key up
  • At state 1 Ship moved to 0x, 1.5y
  • At state 2 player pressed key up again
  • At state 3 Ship moved to 0x, 3y
  • At state 4 the client received GameStateDto saying that at state 1 it’s Ship should’ve been at 0x 1y, not 0x 1.5y as it was computed locally. So local history was rewinded to state 1 according to the server (0x 1y) and then all the player actions from states 2 to 4 were reapplied and passed through game loop instantly. Through states 2 to 4 player has performed one action – an up key press, which locally means going 1.5 unit, therefore in the end Ship is seen on the client at (1 + 1.5)y. The client might be still glitchy, but it gets corrected as smoothly as possible.

From those examples we can extract an algorithm for dealing with Ship latencies:

  • Whenever ControlsDto is sent to the server, mark it using an index
  • Compute GameStateDto locally according to the Controls and save them both, along with index number and render’s delta
  • When GameStateDto with index matching one sent with ControlsDto comes from the server, discard all saved states with lower index and compare locally stored GameStateDto with arriving one
  • If they’re equal don’t do anything
  • If they’re not equal, apply GameStateDto from the server and run game logic locally from received server index until last saved local index, using saved ControlsDto and delta

Back to the code

Ok, so here’s the plan: we’ll need to add indexes to ControlsDto and GameStateDto, make GameStateDtos comparable by equality, keep some sort of local history that’s able to rewind and rerun game loop and also keep indexes per client on the server. Smooth sailing.

Indexed Dtos and Mappers

Let’s tackle indexing Dtos first. Specifically, we’ll need to wrap our already existing Dtos with indexes, so let’s create a wrapper that is also a Dto:

Having that, we’ll introduce missing IndexedControlsDto and IndexedGameStateDto with minimal effort:

You might be asking yourself, why do we need these concrete classes that just delegate to parent constructor, couldn’t we just use a generic type? Unfortunately no, because there’s no way to obtain .class property from a generic type, like IndexedDto<ControlsDto>.class, which we’ll need for mapping.

One last piece we’ll need to complete indexed Dtos puzzle is a Mapper for them. It won’t do anything else than just wrap existing Dtos with indexes:

Game State Dto equality

While we’re on the subject of Dtos, let’s introduce equality comparison to them. All we want is a standard equals and hashCode override. We’ll start with GameStateDto and work our way downwards from there, into types referred from GameStateDto: PlayerDto, ShipDto and BulletDto. I’ll omit the code here since it’s very rudimentary (and you’ll generate it with IDE anyway), but we’ll need it nonetheless.

Necessary adjustments

There are a couple of changes we’ll need to get out of the way before we can proceed.

First of all, our compensations will revolve around movement only. Right now we have both movement updates and other internal state updates entangled in update methods of Player, Ship and Container. We’ll need to refactor that in order to get more fine-grained control.
This is how our models and containers will change:

Remember to find usages of PlayersContainer and BulletsContainer update methods and change them to two calls: move and update so that our code still behaves like before. Look for update calls on both client and server side. This split will enable us to target movements for compensation in particular.

Next we’ll need to open the Ship a little bit more. Apart from position and rotation, we’ll also synchronize velocity and rotationVelocity. It will allow us to make better state predictions.

We’ll need to update a ShipDto accordingly to these properties. Below you’ll find type declarations, I’ll omit code for initialization and getters here since it’s trivial.

In order to put this additional data to some use we’ll need to include it in ShipMapper, when we’ll be mapping Dto from Ship and also when updating Ship by Dto:

The last thing we’ll need to do is to make Player’s controls mutable. Reason for that is when we’ll rewind and rerun game loop we’ll need to be able to set it’s Controls state to whatever ControlsDto says it was at that moment, and that’s not possible with regular Controls (KeyboardControls in our case). This will make a lot more sense to you when we get to client side synchronization. The code change is trivial: just remove final keyword for controls property in Player class, and give it a getter and a setter.

Server side synchronization

Server won’t be very involved in compensating for lags, it’ll just need to keep state indexes for clients. We’ll create the synchronization package inside of connection and put a StateIndexByClient class there that will do just that:

There will be a slight change in how server receives and sends data – it won’t receive ControlsDto and send GameStateDto anymore, but IndexedControlsDto and IndexedGameStateDto, since we need to know what GameStateDto was computed for which ControlsDto.

First, we’ll inject StateIndexByClient instance into SocketIoServer:

We’ll need some way of obtaining index for soon to be computed state. It will come with ControlsDto from the client side, so we need to store it then for a particular client:

Since we won’t broadcast to all the clients simultaneously anymore but rather do it in sequence, with index dedicated for each client, our SocketIoServer’s broadcast method will change the most:

Client side synchronization

This is where the most interesting things start to happen. We’ll introduce a bunch of trickery to pretend that the game reacts to player input instantly rather than waits for the server. First, let’s create package synchronization inside of connection and gather everything that encompasses local state (index, delta when game loop ran, ControlsDto sent to the server and GameStateDto computed locally according to these controls) in a value class:

Now we’ll move onto the actual synchronization. A class that we’re going to implement will keep track of previous locally computed states, and whenever a server state arrives it will compare it with what has been saved locally, thus apply corrections if needed, using callbacks to game loops.

Properties of this class deserve an explanation:

  • currentIndex is what we’ll use for indexing ControlsDto that will be sent to the server
  • recordedStates will hold, well, recorded LocalStates
  • synchronizationControls will be temporarily injected to the localPlayer in order to control it when we’ll rerun game loop
  • gameStateUpdater will be responsible for somewhat similar things that Client’s onGameStateReceived handler was – updating models according to newly arrived state
  • gameLogicRunner will be a portion of game loop taken from AsteroidServerScreen’s render method, the one that calls move on Containers
  • gameStateSupplier will be a way for us to obtain GameStateDto of current client state
  • localPlayer is pretty much self explanatory

Current index will be obtained before sending ControlsDto to the server.

State will be recorded right after computation according to Controls mentioned above.

If there are local states ahead of the server and latest server state is not equal to the corresponding state on the client side, we’ll need to instantly return to that state and rerun game logic based on that corrected state.

Client integration

So we have the tool for synchronization. Let’s move one layer up and use it in SocketIoClient to mark ControlsDto with appropriate index, and to perform state synchronization when the server responds. Remember when we’ve introduced IndexedDtos on the server? We’re going to use them now.
Additionally, we’ll keep track of indexes of received game states. There’s a chance that due to the network glitches, states might come out of order. If that happens (newly received state has lower index than one we’ve already seen) we’re going to ignore the state completely, since there’s no point in computing it anymore.

That’s all good, but it feels incomplete, doesn’t it? I mean, what about gameStateUpdater, gameLogicRunner and gameStateSupplier? All of that will be handled by the layer above, where our game logic related code lives. One more time we need to move up, into AsteroidsClientScreen.

Players lag compensation: the final round

It seems that we’re ahead of the final step now – plugging it all together in AsteroidsClientScreen. Most significant change here will be that we’ll pass executable code into localStateSynchronizer so it can actually perform game actions. The way we’ll be handling Players in Client event listeners will also change because we’ll have to take lag compensation into account.

Note that now when we receive GameStateDto we’ll immediately deal with Bullets only as they’re not lag compensated.

This method will be similar to the one above, but it will be run by the LocalStateSynchronizer as a start of synchronization process (set last known server state, then apply local states).

Next method will be a way for LocalStateSynchronizer to get to current game state.

Here we’ll instruct synchronizer how to run game logic after applying server state. We’ll use method reference because that’s the exact same logic that we’ll also run when computing local predicted state.

Here’s how our state recording will fit in the middle of the render method: we’ll run the game logic, and then save resulting state with delta and Controls data that was used to compute it.

Only thing left to do is to inject new dependencies at AsteroidsClientGame

Sweet! Let’s spin it up and see our newly developed synchronizer in action!

flickering game

What the…

Bonus level: threads synchronization

Ok, it was supposed to be smooth, what’s with all the flickering?
Turns out we have mutable state shared between threads (also known as “debugging this crap was an ordeal”). Event handlers attached to SocketIoClient are running on different threads than rendering loop, so at any given moment we can be in the middle of updating/synchronizing state according to events and rendering the exact same state. Even worse, we’re performing loops in LocalStateSynchronizer.rerunGameLogic, so it’s not as easy as “just use immutable or concurrent data types”. State synchronization should either be applied fully or not at all, like a transaction.

Fortunately, there’s an easy way out of it without sacrificing too much performance.
We know that render loop has to run once every 16ms. We should not mutate state elsewhere when it happens, but locking for a few ms once every 16ms isn’t that bad. We’ll receive game state events from the server at about same pace, and we should also process one at a time, that’s the second constraint. Between local game loop and events there should be plenty of time for event handlers to compute everything and be ready to render next frame, so we’ll take that.

First, let’s extend Client interface with method for locking event handlers:

Then we’ll need to implement them in our SocketIoClient:

In order to lock event handlers while render loop is going and open it up again when it finishes, we’ll need to use these new methods inside of AsteroidsClientScreen.render:

And we can’t forget to inject some Lock implementation into SocketIoClient in AsteroidsClientGame:

After all is said and done, our game should look way smoother:

smoother game

The funny thing is, we’re getting other Players lag compensation for free. We cannot know their Controls state in the present, but we do know their velocities from the past, and based on that we can make good enough predictions about where they will be next.

So this is it. You’ve reached the final paragraphs in these series, congrats. I presume you’re a reasonable human being and you’d stop reading a long time ago if you didn’t enjoy it, so I’m glad and flattered that you’ve made it all the way to the end. As always, you can check out the finished code in the reference repository.

Wait, what about lag compensation for bullets? Or threads synchronization on the server? Or…

That’s true, we haven’t covered these. In fact, we haven’t covered a lot more than just these. But you’re a big boy (or girl) now. You don’t need me to show you things anymore. You’re well equipped to explore and experiment on your own. Go do it, be bold, learn as much as you can and have fun while you’re at it! 🙂

I’d like to thank Agnieszka Bień for meticulously going through the code of each part in these series and correcting a few things along the way, and Patryk Mrukot for valuable suggestions regarding descriptions.

Written by Krystian Jarmicki
Published August 28, 2017