How to keep server-client clocks in-sync for precision networked games like Quake 3?

Question

I'm working on a 2D top-down-shooter and doing my best to copy concepts used in networked games like Quake 3.

• I have an authoritative server.
• The server sends snapshots to clients.
• Snapshots contain a timestamp and entity positions.
• Entities are interpolated between snapshot positions so movement looks smooth.
• By necessity, entity interpolation occurs slightly "in the past" so that we have multiple snapshots in which to interpolate between.

The problem I'm facing is "clock synchronization".

• For simplicity-sake, let's just pretend for a moment that there is zero latency when transferring packets to and from the server.
• If the server clock is 60 seconds ahead of the client clock, then a snapshot timestamp will be 60000ms ahead of the client local timestamp.
• Therefore, entity snapshots will collect and sit for about 60 seconds before the client sees any given entity make his moves, because it takes that long for the client clock to catch up.

I've managed to overcome this by calculating the difference between the server and client clock each time a snapshot is received.

// For simplicity, don't worry about latency for now...
client_server_clock_delta = snapshot.server_timestamp - client_timestamp;

When determining how far along into the interpolation the entity is, I simply add the difference to the client's current time. The problem with this however, is that it will cause jerkiness because the difference between the two clocks will abruptly fluctuate due to snapshots arriving quicker/slower than others.

How can I synchronize the clocks closely enough that the only perceivable delay is that which is hard-coded for interpolation, and that which is caused by ordinary network latency?

In other words, how can I prevent interpolation from starting too late or too soon when clocks are significantly desynchronized, without introducing jerkiness?

Edit: According to Wikipedia, NTP can be used to synchronize clocks over the internet to within a matter of a few milliseconds. However, the protocol seems complicated, and perhaps overkill for use in games?

Answer 1

After searching around, it seems that synchronizing the clocks of 2 or more computers is not a trivial task. A protocol like NTP does a good job but is supposedly slow and too complex to be practical in games. Also, it uses UDP which won't work for me because I'm working with web-sockets, which don't support UDP.

I found a method here however, which seems relatively simple:

It claims to synchronize clocks to within 150ms (or better) of each other.

I don't know if that will be good enough for my purposes, but I haven't been able to find a more precise alternative.

Here's the algorithm it provides:

A simple clock synchronization technique is required for games. Ideally, it should have the following properties: reasonably accurate (150ms or better), quick to converge, simple to implement, able to run on stream-based protocols such as TCP.

A simple algorithm with these properties is as follows:

1. Client stamps current local time on a "time request" packet and sends to server
2. Upon receipt by server, server stamps server-time and returns
3. Upon receipt by client, client subtracts current time from sent time and divides by two to compute latency. It subtracts current time from server time to determine client-server time delta and adds in the half-latency to get the correct clock delta. (So far this algothim is very similar to SNTP)
4. The first result should immediately be used to update the clock since it will get the local clock into at least the right ballpark (at least the right timezone!)
5. The client repeats steps 1 through 3 five or more times, pausing a few seconds each time. Other traffic may be allowed in the interim, but should be minimized for best results
6. The results of the packet receipts are accumulated and sorted in lowest-latency to highest-latency order. The median latency is determined by picking the mid-point sample from this ordered list.
7. All samples above approximately 1 standard-deviation from the median are discarded and the remaining samples are averaged using an arithmetic mean.

The only subtlety of this algorithm is that packets above one standard deviation above the median are discarded. The purpose of this is to eliminate packets that were retransmitted by TCP. To visualize this, imagine that a sample of five packets was sent over TCP and there happened to be no retransmission. In this case, the latency histogram will have a single mode (cluster) centered around the median latency. Now imagine that in another trial, a single packet of the five is retransmitted. The retransmission will cause this one sample to fall far to the right on the latency histogram, on average twice as far away as the median of the primary mode. By simply cutting out all samples that fall more than one standard deviation away from the median, these stray modes are easily eliminated assuming that they do not comprise the bulk of the statistics.

This solution appears to answer my question satisfactorily well, because it synchronizes the clock and then stops, allowing time to flow linearly. Whereas my initial method updated the clock constantly, causing time to jump around a bit as snapshots are received.

Answer 2

Basically, you cannot fix the [entire] world and, eventually, you will have to draw the line.

If the server and all clients share the same frame-rate, they just need to synchronize upon connecting, and occasionally, thereafter, especially after a latency event. Latency does not affect the flow of time or the PC's ability to measure it so, in many cases, rather than interpolate, you must extrapolate. This creates equally unwanted effects but, again, it is what it is and you must choose the least of all available evils.

Consider that in many popular MMO's, lagging players are visually obvious. If you see them running in place, directly into a wall, your client is extrapolating. When your client receive's new data, the player (on their client) may have moved a considerable distance and will "rubber-band" or teleport to a new location (the "jerkiness" you mentioned?). This happens even in major, name-brand games.

Technically, this is a problem with the player's network infrastructure, not your game. The point at which it goes from one to the other is the very line you have to draw. Your code, on 3 separate computers, should more-or-less record the same amount of elapsed time. If you don't receive an update, it should not affect your Update() frame-rate; if anything, it should be faster since there is probably less to update.

"If you have crummy internet, you cannot play this game competitively."
That is not passing-the-buck or a bug.

Answer 3

Synchronizing clocks is the wrong idea to take here. You really want to synchronize simulations. You do this by creating a simulation that has deterministic behavior on both the client and server. The first step to deterministic simulation is using a game loop with a fixed timestep see: https://gafferongames.com/post/fix_your_timestep/

Once you have a fixed timestep deterministic loop, each tick can be deterministically reproducible. You can then reset the client to a tick from the server and replay the same behavior on the client.

Answer 4

This is all very game specific, but in general:

Unless you're doing fixed timestep synchronized simulation like in fighting games where each frame is extremely important, there's no reason to synchronize clocks or state exactly between server and client. The client just needs to see something that's good enough for them to understand what's happening. The physical limit that latency introduces means they can never be perfectly synchronized unless everyone is viewing everything in the past, which again, is only useful for frame-dependent gameplay mechanics like Street Fighter et al have.

Even in a fast-paced shooter, it's not important to synchronize most state. It's only important that if you get a headshot, the server gives it to you in most or all cases. This is done via interpolating (ideally) or extrapolating (worst case, when snapshot not received in time, or for unimportant entities to save bandwidth) on the client-side, as you described in your question. The other half of the equation is server-side latency compensation to account for the fact that clients are seeing enemies in the past, and it decides if their attack should be successful based on a past world state, rather than the present one, to be fair to the client, up to some reasonable limit (i.e. max latency you support).

GafferOnGames has already been linked in an answer above, but +1 to the many great articles there.

In addition, Gabriel's series is one of, if not the, best resources currently available for explaining how this all works, with sample code.

So yeah.. asking "what's the best way to synchronize clocks in networked games" is essentially the XY problem, because the real answer is that you almost certaintly don't need to.

• In a fighting game, you sychronize frames, and you do it by simply making everyone wait until they received all of the data for a given frame before rendering (though modern fighting games are actually starting to move toward extrapolation by cleverly abusing the "charge up" frames of their animations, watch this talk about GGPO if you want to learn more about that).
• For real-time competitive games like CS:GO, Overwatch, etc. you do much more interpolation/extrapolation of basically everything in the scene, and "fix" the error on the server-side by calculating ray vs. hitbox in the past. Watch this talk about Overwatch if you want to learn more about FPS games).
• In most other games, you can most likely get away with interpolation, hardly any extrapolation, and no server-side compensation, because it's not fast enough or competitive enough for ~150ms of delay to matter as long as it renders some approximation smoothly.

The whole playlist that both of those video links are in is an excellent resource for more context about various types of games and how they're network architecture is laid out.