Hit Can’t Miss

In the previous article we already lied to the player a little, and pretty shamelessly at that: we took a ground check that was perfectly correct from the physics point of view, stretched it out by a few milliseconds and let the character jump after it had actually left the platform. We did all that not because our physics programmer is too clumsy to write a proper collision check, but so that the player wouldn't have to know what's going on with our collisions at all… and they're under no obligation to know.

A networked game has roughly the same thing going on, except now we have to lie a little not about the character's position but about time. If coyote time was a small lie about where the platform ends, then lag compensation is a small lie about when exactly the game world existed.

It gets interesting here too: the server may be entirely right that the player missed, and the player will still be convinced the game stole a hit from them. Let's not disappoint players and lose money to bad reviews.

Hits that never happened

Picture a playtest of a multiplayer shooter where one of the players is sitting somewhere in Frankfurt with a 78 ms ping, which is actually a pretty decent ping and perfectly playable. During the test he lands two headshots, sees them on his screen, and twice the game tells him there was no hit.

When you start digging into the problem on the server, the logs really do show there was no headshot. The player thought (that's where the problem is), then clicked the mouse, then the shot packet went out over the network, the enemy kept moving all that time, the packet finally reached the server, the server looked at the current state of the world and found that the enemy's head was already about 0.4 meters to the left of where the player had fired.

From the server's point of view there's no problem at all: the raycast didn't cross the hitbox, so no hit. Close the bug, write something like "works as designed" in the ticket, except that the player, for some reason, disagrees. And this is a good moment to recall the previous article, because there we had the same problem: the computer saw one state and the human saw another. Now there's a network sitting between those two states as well.

In a local game we at least have one single world, but in a networked game the world starts existing in several versions in time at once, and each of those versions is the one true reality for its own part of the system.

For the player, the real world is the one on their screen; for the server, the real world is the one that exists on the current server tick. Between them sits the network, which takes two identical things and for a while convinces us that they're different.

As a result, for players with more than 40 ms of latency about 12% of shots in the test prototype don't intersect the hitbox on the server at all, while in a local game such cases are under 2%, and the phrase "your ping is just high" becomes your problem rather than the player's.

CLIENT                                  SERVER

   target                                 target
      O                                      O
      |                                      |
      |                                      |
      |                                      |
    SHOOT!                                   |
      |                                      |
      +---------- packet ------------------->|
                                             |
                                             v
                                        target moved

                                    RAYCAST
                                       |
                                       X MISS

Where is the enemy?

In a networked game the question "where is the enemy?" is actually quite tricky. If I'm looking at him right now, where is he? At the point I see on my screen, or at the point where he is on the server? Or at the point where he was a few dozen milliseconds ago, when my client received the corresponding snapshot of the world state?

Hmm… and it turns out all three answers can be correct at the same time. The client doesn't show the server's latest state exactly, because then remote players' movement would look very jerky: one snapshot arrives, the character is standing here; the next arrives, the character is suddenly a bit further on, with nothing in between. The picture starts stuttering, and instead of smooth movement the player gets a free demo of the network protocol at work. So the client interpolates the world state, gradually nudging objects' current positions toward the server's.

The server sent the player's positions for several adjacent ticks, the client received them with a delay and can now smoothly move the character between those states, and to do that it has to keep them in the past for a while. If the interpolation delay is 100 ms, then the positions you see on screen right now correspond to a world the server has already left behind.

This is the client-server pair working normally; more than that, it's exactly the behavior we want as developers. The problem shows up the moment the player clicks the mouse, because they want to shoot at the world they see, while the server receives your shot a bit later and checks it against a different world (its own). We end up in a strange situation where the shot was fired in the past, the server checks it in the present, and the player expects the server to somehow figure out that they were seeing an even earlier past.

TIME ------------------------------------------------------------>

SERVER     [100]------[101]------[102]------[103]------[104]
                                              ^
                                              |
                                         shot arrives

CLIENT          [100]------[101]
                              ^
                              |
                           SHOOT!

CLIENT SEES                    O
                                |
                              TARGET

SERVER NOW                         O
                                    |
                                  TARGET

And if the server doesn't do that, you get the classic "I hit him, but the game said no." (Try it yourself) Aim at what you see and watch latency turn a "naive" shot into a miss.

Building a time machine

The most obvious solution here is to make the server remember the past: on every server tick, save the positions of something "more or less persistent", for example the characters' hitboxes, and stash the snapshots in an array. Then instead of a single current state we have a small history of the world that we can walk back through, and if we keep 64 ticks at 60 Hz, the server gets roughly 1066 ms of history.

Now the server literally gets the ability to ask, "so where was this guy a second ago?" If a character has 18 collision boxes of 32 bytes each, one snapshot takes 576 bytes, and for 32 players and 64 ticks the whole history takes about 1MB, which for a modern server doesn't look scary at all.

The fun starts after that, because storing history is fairly easy, but figuring out which exact point of that history to use for a particular shot is harder. Roughly speaking, we end up with something like this (the code itself doesn't matter, it's just an example):

struct FHitboxSnapshot{
       uint32 Tick;
       Capsule Hitboxes[18];
};

Then, when processing a shot, we no longer just do Raycast(CurrentWorld); first we try to work out at which moment in the past our CurrentWorld should exist. So the task turns from did the ray hit the hitbox? into Did the ray hit the hitbox in the world state the shooter saw?. And we get roughly this:

                         NOW
                          |
                          v
SERVER   -----------------+----------------------------->
                          |
                       target
                          O
                         /   /   /   X    MISS

                         <---- REWIND ----

SERVER   -----------------+----------------------------->
                          |
                     old target
                          O
                         /   /   /   /   /      HIT

And a simple-looking time check turns into a task of an entirely different caliber. Try it yourself (toggle rewind compensation on and off to compare the hit rate).

How many ticks back do we go?

The first thing you want to do is just take the tick time and roll it back by the ping. Say the tick time is 100 ms and the ping is 78 ms, so let's rewind the world one tick back. But ping is the round-trip time, and what we care about first and foremost is the part of the latency it took the shot packet to reach the server, so this particular implementation uses the formula:

rewindTime = RTT / 2 + interpolationDelay;

With a 78 ms ping and a 100 ms interpolation delay we get:

                         REWIND
                            |
              +-------------+-------------+
              |                           |
           RTT / 2                 interpolation
              |                       delay
              |                           |
            39 ms                       100 ms
              |                           |
              +-------------+-------------+
                            |
                            v
                         139 ms

So the server checks the hit against roughly the hitbox state that existed 139 ms ago. There's a small catch here too: you can't just take the time from the client's message, because then all a client has to do is tell the server it supposedly interpolates the world with a two-second delay, and the server will helpfully rewind all the other players somewhere back to the age of the dinosaurs.

So the server measures the rewind time itself, but how to verify incoming data is a different story. Ping itself can't be treated as a constant either, because the network changes latency right in the middle of the game; in a system like this you can keep stats on the last 20 responses and take a value between the 25th and 75th percentiles, and when the spread is large, round the rewind rather than try to compensate for every random latency spike.

Because if you try to compensate for the player's actual ping, you'll very quickly discover there are players with genuinely bad ping who are shooting practically from the past, with a rewind of 500+ ms. Imagine another player who ran around a corner and crouched there, and then suddenly caught a headshot: that's roughly what overcompensated ping looks like.

Try it yourself (move RTT and interpolation delay separately and watch how they add up to rewindTime).

True lies

And here a very interesting question comes up: if we've already agreed to rewind the world for the player's sake, why not rewind it as far as needed? Why not give a player with 500 ms of ping the same conditions as a player with 20?

Because then latency starts turning from a handicap into a gameplay advantage, and at extremely high ping you start getting situations where an enemy stepped out from behind a wall, you saw him, fired, and he ducked right back. In your slow world he's still where you just saw him, but on the server he's long since been behind the wall.

And if the server trusts the past state, a high-latency player will regularly hit people who, from the server's point of view, have long since disappeared behind cover. So we seem to have fixed the sense of unfairness for the shooter, but at the same time created a new unfairness for the one being shot. That's why the maximum rewind window on the server has to be capped.

PAST                                                        NOW
 |                                                           |
 v                                                           v
 +-----------------------------------------------------------+
 |<-------------------- history ---------------------------->|
                         |
                         |<------ 200 ms ------>|
                         |
                         + MAX REWIND

Ideally the implementation shouldn't go beyond 200 ms… give or take, for our game. Where did that number come from? It's simply a compromise you derive from player complaints. At 250 ms, complaints about getting hit after already ducking behind cover go up; at 150 ms, headshots start dropping and a different set of players complains. So 200 ms turned out to be a reasonable compromise between two opposite problems. Lag compensation has no correct number.

Try it yourself (hide the target behind a wall and raise MAX_REWIND above the shooter's latency to catch an unfair hit).

Why rewind everyone?

There's also a more mundane problem once we've learned to time-travel. If the game has 32 players, on every shot we have to rewind all 32, and the server does this for every single shot. But we roughly know the direction of the shot, so we can first figure out which objects could possibly intersect the ray and only then bother with history. That way we can throw out the 90% that don't intersect and cut the check time.

                 SHOT RAY
                    v
        +-----------------------+
        |  32 players           |
        |  O  O     O           |
        |       O               |
        |    O       O          |
        |             O         |
        +-----------------------+
                    |
              spatial filter
                    v
                 O  O
                 2.3 avg.
ALL PLAYERS                    FILTERED
     |                              |
     v                              v
   0.9 ms                         0.08 ms

So here we didn't so much speed up the rewind itself as first make sure we don't need to do it for most objects at all. And it's quite likely that the bullet's ray doesn't come anywhere near anyone, in which case we don't need to run the hit logic at all.

Try it yourself (shoot into a crowd and watch the measured perf delta between checking all players and checking only the candidates).

And this is where a class of problems begins that shows how much all of this isn't really just about the network. Say we decided to save the hitbox every tick:

SaveHitboxSnapshot();
UpdateAnimation();

Now we have a problem: the visual model has already moved into a new pose, while the saved hitbox still matches the old one. For regular movement the player will most likely never notice, but for a fast-moving enemy (a plane, a car, a full sprint) a difference of a few centimeters can be quite enough to turn a hit into a miss.

Try it yourself (swap the order of SaveHitboxSnapshot()/UpdateAnimation() and watch the visible pose and the saved hitbox drift apart).

The server has to be honest

Up to this point we've mostly been trying to make the server kinder to the player, but now we need to think a bit about what happens if the player decides to take advantage of that kindness. Because ping lets the client tell the server: I fired on tick 123456

and effectively ask the server to look into the past, which means the time parameter itself becomes part of the logic and can no longer simply be trusted. The server has to cap the rewind depth on its own and check how much the claimed tick even looks like a normal continuation of that particular connection's timeline, for example by comparing it with a moving average of the last 32 packets and rejecting requests that deviate by more than roughly 60 ms. Otherwise the compensation mechanism very quickly turns from a handy game mechanic into yet another frag-farming tool. So suspicious requests are best not only dropped but also logged.

And that's also pretty typical for networked games: as soon as the system starts trusting the client even a little more than necessary, it turns out clients find ways to exploit it.

Try it yourself (you can lie to the server about your latency and see when the claim gets accepted and when it gets rejected).

What if the player is already dead?

There's one more small edge case: the player fired, then the packet flew off to the server. While the packet was in flight, the player died, and the packet arrived after death. What do you do? You could look at the player's current state and say "The player is dead, so there was no shot", but then a high-ping player gets rather strange behavior, where their bullets only exist up until their character dies on the server. So it makes sense to check not only the current state but also the shooter's state at the moment the shot belongs to. And that gives us another wonderful situation, where the server can say at the same time:

Yes, you're dead now. And you killed someone
Because when you fired, you were still alive.

Try it yourself (fire a split second before dying and watch how the naive and the honest alive checks behave).

Time compensation really can't be considered separately from running ahead into the future (client prediction), because in the end all these systems are trying to solve the same problem from different sides. The client has to keep living while the server is somewhere far away, and then both versions of the world somehow have to agree again on what exactly happened, so they need a shared timeline.

People also often confuse time compensation with rollback (plain rewinding of time), because both approaches use words like "roll back", "go back" and "check the past", but under the hood they're completely different systems.

Rollback returns the simulation to the past and then replays it to get a new world state.

LAG COMPENSATION

PAST                                  NOW
 |                                     |
 v                                     v
[old hitboxes] -------------------- [world]
      |
      +--> raycast
      |
      +--> restore


ROLLBACK

PAST                                  NOW
 |                                     |
 v                                     v
[whole world] ---- replay ----------> [world]
      |
      +--> physics
      +--> AI
      +--> projectiles
      +--> inputs

Time compensation in this form is simpler: we don't roll back all the physics, don't rewind bullet traces, don't rerun the AI and don't recompute all 32 players. We temporarily take the old positions of the hitboxes we need, do the hit check, and then put everything back.

So the same phrase "we take the game back into the past" can mean two completely different architectures: one keeps a few dozen kilobytes of hitbox history, and the other suddenly starts re-simulating half the game.

Try it yourself (the same shot, but rewinding one hitbox versus replaying the whole world, so you can see what each costs; the red dots are the whole-world replay).

A good game should lie about time

Looked at from the outside, a lag compensation system seems pretty odd. We deliberately store the past, deliberately rewind the world, deliberately check the hit not against the state that exists on the server right now but against the state the client saw a while ago, and we do all this so that the player gets a result that looks natural from their point of view.

So the server knowingly checks not quite the world that exists at this moment. That's a lot like coyote time, and again, from the standpoint of ordinary physics it looks a bit insane, but a game is under no obligation to be a rigorous physical model.

That's why coyote time and lag compensation are really two flavors of the same idea (bending the game to fit the quirks of human perception), even though they live in completely different parts of the engine. The player has no idea that their client lives 100 ms in the past, that the shot packet arrived late, that the server keeps 64 snapshots, that the hitbox was rewound by 139 ms, that one of them got filtered out and then restored back. They shouldn't have to know any of it.

In the end it's a theater for an audience of one. A good game should lie a little; what matters is that the player enjoys playing.

P.S. The esteemed Klavdiy and Fublya helped build the examples for this article, because writing all of this in C++ and making you compile it on your own machine felt somewhere beyond good and evil. I've also added examples to the previous article, if anyone's interested.