How to compensate for moving objects with client side prediction?

Question

I'm implementing a game server that supports Star Control-like melee. So you have ships flying and shooting, with super simple velocity/acceleration/dampening physics to drive movement.

I've read Valve, Gafferon and Gambetta and implemented Gambetta's algorithm for client prediction:

Client prediction works on the player ship by updating its position from the server as it comes and then reapplying the yet-unprocessed-by-the-server input to the player ship.

Unfortunately, it doesn't work well for my game. I believe it has to do with the fact that Gambetta's example doesn't take into account objects that are already moving, or commands that are updated on a step by step basis. (by "step" I mean frame). So in my game the player presses up to accelerate the (already moving) ship, which continues moving on the client, sends the command to the server and usually receives the world snapshot from the server on the next step. I get something more like:

The player command runs at client step 3, but on the server its only run at server step 5. By the time the world snapshot is received by the client at client step 6, the prediction is way off, especially in faster velocities.

The crux of the problem is that the client runs the command at step 5, but the server runs it at step 6. I thought about maybe sending the client step with the command, and have the server roll back and re-run the command with the client time step. That might lead to a slew of other problems though - like what happens to commands received since the rollback, or how cheating clients can exploit by changing the sent step.

Reading and watching videos like this one from Google mentions a different approach, where you gradually change player position to match that of of the snapshot over a few steps.

My questions:

• Can you make Gambetta's algorithm work with constant step movement? Or is it conceptually incompatible with my game?

• Is gradual interpolation over steps the correct way to go then? If so, how do you interpolate an already moving object from the client position to match that which was just received from the server?

• Can these methods, gradual interpolation and Gambetta's algorithm work in tandem, or are they mutually exclusive?

Answer 1

During the 6 months since I asked this question, I ended up developing a complete open source game server to deal with this exact issue (and many others!): https://lance-gg.github.io/

The R&D involved now allows me to answer my own questions:

• Can you make Gambetta's algorithm work with constant step movement? Or is it conceptually incompatible with my game?

Gambetta's algorithm will not work when the movement of the entity is not deterministic (from the client's POV). If an entity can be affected without input by physics or other players, for example a more elabroate approach needs to be taken.

• Is gradual interpolation over steps the correct way to go then? If so, how do you interpolate an already moving object from the client position to match that which was just received from the server?

This touches on a different topic, which is client reconciliation of server updates. Gradual interpolation works, but for very fast paced games like the one in the question it is better to actually implement extrapolation

• Can these methods, gradual interpolation and Gambetta's algorithm work in tandem, or are they mutually exclusive?

They can work together, but only if the entity movement is deterministic from the client POV. So it won't work if the the entity is affected by physics or psuedo-physics like inertion, drag etc'

Answer 2

Your game seems to be too "real-time" to think in terms of time steps. I'd only think in terms of "turns" if the game can be considered "turn-based". Otherwise, just abandon the idea of turns or steps. Everything becomes easier then :)

Note that you predict locally for your player, and interpolate only for other entities (as explained in the 3rd article in the series). The way to deal with server updates for objects that were already moving is server-side reconciliation, explained in the bottom half of the 2nd article (the one you linked towards).

Hope this helps :)