15
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ how is it complicated? It's a request and response each with timestamps of transmission and arrival, then a bit of math to get the delta \$\endgroup\$ – ratchet freak Feb 5 '15 at 8:44
  • \$\begingroup\$ @ratchetfreak: According to (mine-control.com/zack/timesync/timesync.html), "Unfortunately, NTP is very complicated and, more importantly, slow to converge on the accurate time delta. This makes NTP less than ideal for network game play where the player expects a game to start immediately..." \$\endgroup\$ – Joncom Feb 5 '15 at 20:37
9
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ How did this prove to work for you then? I am in the same situation now. I am using a server framework that only supports TCP, hence I cannot use NTP, which sends UDP datagrams. I struggle to find any Time Synchronization Algorithms that claims to do reliable time synchronization over TCP. Synchronization within a second would be enough for my needs though. \$\endgroup\$ – dynamokaj Jan 18 '17 at 10:54
  • \$\begingroup\$ @dynamokaj Works fairly well. \$\endgroup\$ – Joncom Jan 18 '17 at 21:16
  • \$\begingroup\$ Cool. Is it possible that you could share the implementation? \$\endgroup\$ – dynamokaj Jan 18 '17 at 21:16
  • \$\begingroup\$ @dynamokaj Seems I cannot find such an implementation in any projects I can think of right now. Alternatively what works well enough for me is: 1) immediately use the latency you calculate from one ping request/response and then, 2) for all future such responses tween toward the new value gradually, not instantly. This has an "averaging" effect which has been plenty accurate for my purposes. \$\endgroup\$ – Joncom Jan 18 '17 at 22:15
  • \$\begingroup\$ No problem. I am running my backend service on Google App Engine, hence on Googles infrastructure where servers are synchronized using Google NTP Server: time.google.com (developers.google.com/time) I therefore uses the following NTP client for my Xamarin Mobile client to get the offset between the client and server. components.xamarin.com/view/rebex-time - Thanks for taking the time to answer. \$\endgroup\$ – dynamokaj Jan 18 '17 at 22:20
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.