3
\$\begingroup\$

Edit

After reading some more questions on this board, I've come up with this potential scheme. Feel free to give any suggestions / criticisms on the scheme I show in the box below.

ct = client time, snap { server timestamp on received snapshot }
ct: 0.00    snap { 0.20 }
ct: 0.00    snap { 0.30 }
ct: 0.00    snap { 0.40 } // set ct: 0.40 expecting every 10ms - delay by 20ms
ct: 0.45    draw 0.25
ct: 0.50    snap { 0.50 } // on time
ct: 0.55    draw 0.35
ct: 0.63    snap { 0.60 } // 3ms late 
            draw 0.43
ct: 0.78    snap { 0.70 } // 8ms late (40% of delay) - trigger slight slow (20%)
                            (for every game tick, 'reverse' the clock by 20% of the tick length)
                            (if 5ms has passed, pull the clock back 1ms so you only draw 4ms worth of updates)
            draw 0.58
ct: 0.83    delay ct: 0.82
            draw 0.82
ct: 0.87    delay ct: 0.86
            snap { 0.80 } // 6ms late - still slow (20%) 
            draw 0.66
ct: 0.91    delay ct: 0.90
            draw 0.70
ct: 0.95    delay ct: 0.94
            snap { 0.90 } // 4ms late - normal speed
            draw 0.74
ct: 1.04    snap { 1.0 }
                draw 0.84

when received 3 snaps (or 2 but that the difference in sequence number is 2), take the time between sequence numbered timestamps as update rate.
set delay to update time * 2. set client clock to time of most recent snap
when receiving snap, determine how late/early it arrived.
if lateness is 25% of delay, slow down time slightly. 40% delay, slightly more. etc.
to implement 'slow down time', when updating the game, calculate the time it has been and multiply it by 50-90% to get the 'slower' time 
    update clock offset accordingly.
do similar for earliness 
if packet lateness results in 25% extrapolation 2-3 packets in a row, jump back in time to the newest packet time keeping the same original delay
packet earliness can afford to take longer on its speed ups without needing to do a jump forward.

Original Post

For the last month or so, I've been reading about and working on the networking side of video games. Specifically the authoritative server model.

I've read some really great resources on the topic and feel like I have a really solid understanding of the theory behind most of the common solutions to the core issues. However there is one specific case that needs to be handled on the implementation side that I have been stuck on for the last two weeks.

The issue lies within the implementation of Delayed Entity Interpolation. Some good resources on the topic are:

https://gafferongames.com/post/snapshot_interpolation/

http://www.gabrielgambetta.com/entity-interpolation.html

https://developer.valvesoftware.com/wiki/Source_Multiplayer_Networking#Entity_interpolation

Here is my explanation of the motivation and theory behind it. Feel free to skip to the examples if you're familiar.

Essentially, the client is receiving game state updates (snapshots) from the server at a fairly regular interval. This interval is almost always longer than the game's internal update or draw rate. The client could display those updates as soon as they received them, but then the client would have to wait for the next snapshot to move all of the entities again which would result in really jittery and erratic animation.

One thing the client could do to get around this is extrapolation. This is essentially using the history of each entity to predict where it will be next. Extrapolation could be used to smooth out the movements, however with entities that aren't very predictable (such as player controlled entities), these predictions would be wrong a lot and the corrections would lead to the jittery / erratic animation.

What most games use is delayed interpolation. The idea is that if the client waits until it has 2 snapshots from the server, it can start rendering snapshot 1 then on each successive render frame, have all of the entities move towards their snapshot 2 positions. This allows the client to update the game at its own rate independent of the server's snapshot rate while keeping smooth and (fairly) accurate positions.

If the client only waits for 2 snapshots to begin interpolating, by the time the client's render time reaches the 2nd snapshot, another server snapshot should be arriving. If the snapshot arrives late (or was dropped on transit) then the client won't have a snapshot to interpolate towards and they will need to choose how to handle that (extrapolation would usually be used).

One thing the client can do to reduce the likelihood of having to extrapolate is to wait for 3 snapshots instead of only 2. This allows for a dropped / late packet as long as the packets aren't too late or 2+ packets aren't dropped in a row.

The more snapshots that the client 'buffers', the further behind the server it will be. (This is also affected by the server's snapshot rate and client latency. More frequent snapshots = client not as far behind the server. Higher latency = further behind server.)

What I can't seem to wrap my mind around is how this is actually implemented to account for changes in latency.

Example

Say for example the client has 10ms latency and the server is sending snapshots every 20ms.

The client clock and server clock are not synchronized off the start. ct = client_timestamp, st = server_timestamp.

Client side receives/draws:
ct: 0.00    snap { st: 0.40 } client waiting for 3 snapshots to begin
ct: 0.00    snap { st: 0.60 }
ct: 0.00    snap { st: 0.80 } client set clock to first snapshot time (0.40) and start drawing
ct: 0.41    draw 0.41           
ct: 0.50    draw 0.50
ct: 0.60    snap { st: 1.00 }
            draw 0.60       
ct: 0.70    draw 0.70

The client started drawing 40ms behind what it received however with 10ms latency (server->client travel time 5ms), that puts the client 45ms behind the server.

This will work properly with stable latency, but let's look at what happens with a short ping spike.

ct: 0.80    snap { st: 1.20 }
            draw 0.80
ct: 0.95    draw 0.95
ct: 1.00    draw 1.00   //  expected snap here, but it's late
ct: 1.10    draw 1.10
ct: 1.15    draw 1.15   //  we should have received snap 1.40 15ms ago and we only have 0.05s left of interp buffer
ct: 1.20    draw 1.20   //  expected snap 1.60 here, but it's late as well and we haven't even received snap 1.40 so we no longer have a snapshot to interpolate towards
ct: 1.22    draw 1.22 (extrapolated)
ct: 1.25    draw 1.25 (extrapolated)
ct: 1.26    snap { st: 1.40 }   //  received snap 26ms late which means the server->client travel time went from 5ms to 31ms (61ms latency)
ct: 1.30    draw 1.30
ct: 1.32    draw 1.32
ct: 1.33    snap { st: 1.60 }   //  packet arrived 13ms late, server->client travel time 18ms (latency 36ms)
            draw 1.33
ct: 1.40    snap { st: 1.80 }   //  expected snap 1.80 here so server->client travel time is back to 5ms (latency 10ms)

Thanks to waiting for 3 snapshots to start interpolating, the client was able to maintain its 45ms distance behind the server and only had to extrapolate for 0.05s.

But what happens when the client's ping spikes and stays there?

ct: 1.50    draw 1.50
ct: 1.60    snap { st: 2.00 }   //  on time
            draw 1.60
ct: 1.80    draw 1.80   //  expected snap 2.20
ct: 2.00    draw 2.00   //  expected snap 2.40. last snap received was 2.00 so we have nothing left to interpolate towards
ct: 2.05    draw 2.05 (extrapolated)
ct: 2.06    snap { st: 2.20 }   //  26ms late
            draw 2.06 (interpolated)
ct: 2.20    draw 2.20   //  expected snap 2.60. last snap received 2.20 so must extrapolate again.
ct: 2.25    draw 2.25 (extrapolated)
ct: 2.26    snap { st: 2.40 }   //  26ms late
            draw 2.26 (interpolated)
ct: 2.40    draw 2.40   //  expected snap 2.80. last snap received 2.40 so must extrapolate again.
ct: 2.45    draw 2.45 (extrapolated)
ct: 2.46    snap { st: 2.60 }   //  26ms late

The client-server latency jumped up to the point of requiring extrapolation, but hasn't gone back to normal so now the client is forced to extrapolate 5ms out of every 20ms. If the latency stays here for an extended period of time, this extrapolation could lead to a worse experience.

Three snapshots in a row arrived significantly late so I would think that the client would have some mechanism of adjusting (resynchronizing) how far behind the server it is rendering.

One option could be to pause all client side updates until it has 3 snapshots again.

ct: 2.47    draw 2.45 (extrapolated)    //  3 late snapshots so we pause render time
ct: 2.60    draw 2.45 (extrapolated)
ct: 2.66    snap { st: 2.80 }   //  we now have snaps 2.40, 2.60, 2.80 so we can set clock to 2.40 and start rendering again
ct: 2.40    draw 2.40
ct: 2.55    draw 2.55
ct: 2.60    snap { st: 3.00 }   //  on time based on our new synchronization

This option re-synchronizes the client to be appropriately behind the server, however it required the client updates to be paused at the 2.45 (extrapolated) point for 21ms and then jumped 'backwards' to 2.40.

This wouldn't be the smoothest solution to an increase in latency, but it would work. However we'd also need it to adjust for reduced latency.

ct: 2.65    draw 2.65
ct: 2.70    snap { st: 3.20 }   //  10ms early
            draw 2.70
ct: 2.80    draw 2.80   //  expected snap 3.20 but already received
ct: 2.85    snap { st: 3.40 }   //  15ms early
            draw 2.85
ct: 2.97    snap { st: 3.60 }   //  23ms early
                                //  3 snaps in a row early. we now have snaps 2.80, 3.00, 3.20, 3.40, 3.60. set clock to 3.20 and continue rendering.
ct: 3.20    draw 3.20
ct: 3.30    draw 3.30
ct: 3.40    snap { st: 3.80 }   //  on time based on new synchronization
            draw 3.40
ct: 3.60    snap { st: 4.00 }   //  on time based on new synchronization
            draw 3.60

Here, the latency fell back down which resulted in receiving 3 snapshots early. When the client received the 3rd early snap, it resulted in 5 snapshots in its buffer so it readjusted its clock to be 3 snapshots behind.

Like the option to temporarily pause rendering due to increased latency, this 'solution' will result in an instantaneous jump in time (when the clock gets adjusted) which isn't very smooth but it does seem to work.

Another approach that I've considered is slowing down / speeding up the interpolation time compared to the client time whenever a series of snapshots arrive late/early. Going back up to ct: 2.47 from above:

ct: 2.47    draw 2.47   //  snap buffer: 2.40, 2.60. 3 late snaps in a row so slow down interp time to 50% (move forward along the snapshots 0.01s every 0.02s of client time)
ct: 2.51    draw 2.49
ct: 2.59    draw 2.53
ct: 2.65    draw 2.56   //  we'd normally have to be extrapolating here, but since we slowed down interp time, we still have a snapshot to interpolate towards
ct: 2.66    snap { st: 2.80 }
            draw 2.57   //  snap buffer: 2.40, 2.60, 2.80. we now have 3 snapshots in the buffer again so return to normal speed and set client clock to interp time. expecting snap 3.00 at ct: 2.77
ct: 2.58    draw 2.58
ct: 2.75    draw 2.75
ct: 2.77    snap { st: 3.00 }   //  on time based on new synchronization

This results in the animations moving slower/faster for a short period of time to 'resynchronize' the client to the incoming snapshots, but it might result in a better experience than instantaneous jumps in time / pauses.

I'm thinking there must be a more elegant solution to this problem that can handle changes in latency. Dropped packets / latency spikes are quite common in online gaming, yet most games are able to keep the amount of jitters/teleporting to a minimum.

I've tried reading through the Quake 3 source code to see how they did it, but couldn't track down the relevant pieces of code and haven't been able to find any resources with actual implementation examples.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.