11
\$\begingroup\$

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.

enter image description here

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

enter image description here

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:

enter image description here

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?

\$\endgroup\$
  • \$\begingroup\$ I've been doing the same and run into the exact same problem. As soon as I added velocities applying server state and re-applying inputs got rid of the already handled velocity changes. I've been trying to re-apply all updates since last received message but it's not very smooth yet. Have you ever found a solution to this? \$\endgroup\$ – MakuraYami Sep 12 '16 at 11:14
  • \$\begingroup\$ @MakuraYami Yes - I've started writing an article describing the solution. Will update soon! \$\endgroup\$ – OpherV Sep 12 '16 at 12:58
  • \$\begingroup\$ I've worked more on my project and found a usable solution and some more good resources talking about this issue. I'm interested to discuss further, compare solutions, etc. Let me know where I can contact you :) \$\endgroup\$ – MakuraYami Sep 14 '16 at 21:22
  • \$\begingroup\$ @makurayami my user name at Gmail \$\endgroup\$ – OpherV Sep 15 '16 at 5:26
5
\$\begingroup\$

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!): http://lance.gg

enter image description here

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 insertion, drag etc'

\$\endgroup\$
1
\$\begingroup\$

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 :)

\$\endgroup\$
  • \$\begingroup\$ Just to clarify - by "step" I mean "frame", which runs 60 times a second. I call it step (and not frame) to differentiate actual game progression from the rendering, and ideally they are both synched at 60 per second. I already implemented your version of server-side reconciliation which works brilliantly. This question only refers to the player ship - which is constantly moving regardless of player command (due to inertion). That is where my difficulty lies. Any thoughts on that? :) \$\endgroup\$ – OpherV Jun 15 '16 at 12:08
  • \$\begingroup\$ Frames are different than steps. Steps move in a constant, predictable order. Frames move a variable amount of time, so any progression has to be multiplied by the delta time for that frame. \$\endgroup\$ – Tealr Jun 15 '16 at 13:46
  • \$\begingroup\$ @Tealr indeed, which is why I used the term "step" to begin with - I just wanted to make it clearer that the use of "step" is not limited to turn-based games, and in my game a step takes exactly 1/60 of a second regardless of rendering. \$\endgroup\$ – OpherV Jun 15 '16 at 14:52
  • \$\begingroup\$ Just something I note for my own experimenting: 1/60s. is unusually fast and I'll wager that most online games with more than 1x1 participation work at 1/10s. updates or thereabouts. \$\endgroup\$ – Patrick Hughes Dec 12 '16 at 20:08

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.