Client side prediction

As I was finishing up this post, I realized Glen Fiedler already did a good piece on client side prediction as well, including a nice demo. His site is an excellent introduction to networked games, as well as some game physics, so be sure to check it out.

What it's all about

In a client-server set up, the server is the absolute authority how objects move in the game world, including all the player characters. This introduces a problem when playing over the internet vis-a-vis network latency, or lag. With round-trip times often a fair bit into the three digit range in milliseconds, it means whenever you turn or move, there'll be one or two tenths of a second delay before anything happens on screen. Such a delay is clearly noticeable and not at all acceptable for real-time/action games.

A second lag-related problem is that the clients view is actually not behind the server by a network delay. The server sends packets at a certain rate, often fairly low, let's say 10 packets per second for the sake of this discussion. Right after the server update arrives, the clients view will be behind the server's by a network delay, however, there will be another 100 ms before the next updates arrives, by that time, just before the next update arrives, it'll be behind by another 99 ms. We can't really get rid of the network delay, but we can in some cases compensate for the extra 10th of a second pretty easy, and we'll deal with this first to get it out of the way.

To counteract this delay, we turn to client-side prediction. The server is still the authority on everything in the game world, we just try to guess what the server will do next, and how it'll interpret our input.

Predicting autonomous movement

The second problem mentioned above, the easier of the two, is about compensating for the fact that the server is only issuing updates every so often, basically we have three choices of dealing with it

  1. Showing the latest data, updating when the next packet arrives. Objects will appear to teleport around the screen if moving fast, but it might be acceptable for really slow stuff.
  2. We can assume we'll receive updates at a constant rate (barring packet drops) and when we receive an update we start interpolating (linearly or otherwise) between the last update and the current one. If all goes well and the network delay doesn't fluctuate, we'll reach the new state just in time for the next update to arrive. With this approach we're constantly behind the server with the network delay plus the server frame time. It is also fairly easy to smooth out packet loss (or a higher latency) by letting the interpolation factor go beyond 1.0, effectively extrapolating.
  3. We can try to predict what the server will do the next frame.

In a multiplayer environment, we're pretty much stuck with option two (or variations thereof) for showing the other players, as there are generally no easy way to accurately predict their movement. One variation of option two would be to do linear extrapolation using the previous two frames (or by fitting a curve to the last three or more frames), rather than interpolate between them, as well as smoothing out the resulting prediction error. This may be preferable to interpolation for high paced games, assuming that a player in motion tends to stay in motion, and roughly in the same direction. There are other options, for example, if all you care about is that the player should hit what he's firing at in a first person shooter, the server could actually account for ping and check if the target was actually there at that point in time. But that's a completely different can of worms.

Non-player objects though are a lot easier to deal with. They're governed primarily by the rules of the game, and we simply need to run the same code on the client, as the server does for the same objects, and we'll have a rather accurate prediction of what the server will come up with. This obviously works well for rigid body dynamics, such as bouncing objects, but it can work similarly well for objects which are controlled by the game as well, such as missiles being guided towards a set (not user controlled) target, or even AI decisions. There might still be prediction errors that need to be smoothed out for a number of reasons, the most prominent being of course a player interacting with the object somehow.

Prediction of other players can be improved further by applying a similar schemes as with non player objects, although the movement is not completely controlled by the game, things like collision detection and gravity is, thus we wont let our predictions run through walls, and will probably reduce the prediction error in the process.

Predicting ourself

The most important kind of client side prediction is, at the same time, the trickiest one, and that's predicting how the server will react to our input, and basically show the player what we think will happen once the server reacts to the input.

Effectively, we disconnect the player object from the rest of the game world, which will only see our movement once the packets reach and are processed by the server. The server will then make up its own mind how our object actually behaves and tell us about it, adding one more network delay before the packet reaches us, so what we're actually showing one object which is a whole round-trip time out of sync (in this case, ahead of) the rest of the world we're showing.

Packet flow

Lets say we have a server running at 10 frames per second, which reads all incoming packets, runs the world one step forward, and at the end of the frame it sends a packet to each client with relevant data. Ideally, we want to get our inputs to the server as close to the beginning of the frame as possible, so the server works with the most recent data possible. Timing it perfectly so our packet arrives just before the server starts processing is futile of course, so what is typically done is the client sends packets to the server at a much higher rate, which are then processed in sequence by the server. We will of course need to compensate for packet loss in both directions, but that's a topic for a different post.

Packet flow
If we have 200 ms network delay (i.e. 400 ms round-trip), when the packet is halfway there, the server is already sending the next one. So the server is sending packets s1 and s2, by the time s1 reaches us, it's about to send s3. Reacting to the state represented in s1, the player starts to move and client fires off five packets (let's say it's at 50 fps to keep it simple), c1-c5, even before s2 arrives, which will reach the server in time to have an effect starting with s6. Only after s6 arrives will we know for certain what effects c1-c5 had in the eyes of the server, and by this time we've already issued 20 additional commands.

We now how a server update reflecting our inputs up to c5, snapping the object to this state would undo all effects of prediction, not to mention cause the motion to be really erratic. What we need to do is adapt our own state to correspond to state we would've had if we would've received the server update before transmitting c6, and we can achieve this by storing the inputs we issued to the server (and used to update our player object), take the new server state and replay our own commands c6-c25. We may at this point discard our stored inputs up to c6 as we definitely wont be needing them again. How do we know which inputs the server used? Well, the easiest way is to have it just tell us.

If the previous prediction was accurate, the result of our replay would precisely match what we're already showing the player. However, if, for whatever reason (and there are plenty), it doesn't match, we have a prediction error.

Dealing with prediction errors

When our new prediction doesn't match our previous one, or we receive a server update which doesn't match what we were expecting, we need to correct our own state. The first obvious choice is to simply snap the objects to their new location, which will probably work very well in a low-lag environment with only a few smaller prediction errors, which, incidentally, development environments usually are.

Prediction interpolation
Should latency start to increase — and for testing, it may very well be worth your while to introduce artificial latency — and you introduce more players to cause unpredictable interactions, your prediction errors will start to build up, and warping will soon be apparent. To combat this, the minimal effort should at least be to do a linear interpolation over the next server frame time, which means we'll have to keep predicting based on the new server update, but offsetting the result slightly in the direction of the previous misprediction to smooth out the return to an accurate prediction. Hopefully our prediction was spot on this time, and the next server update (and accompanying replay) will match what's already being displayed.

Causes for prediction errors

There are several causes for prediction errors, the most obvious is that we do not have all the information the server has, movement of the other players for example. It can be rather subtle too, a player blocking a line-of-sight query, affecting the decisions made for one object, which in turn nudges another object an so on.

A less obvious cause is floating point operations, as it turns out, different CPU architectures can produce slightly different results doing the same operations, this is especially true for hardware supported operations like trigonometric functions, where results might differ even between CPU manufacturers. Different compilers can also cause diverging results, and the subsequent headaches. Glen Fiedler has done some digging and put together a list of collective experiences on the subject, well worth checking out. Keeping this in mind, it might be worth considering doing calculations using fixed point arithmetic.

comments powered by Disqus