Player acceleration formula and using it with authoritative server

Question

I know the theory behind authoritative client-server architecture, it works very well for character movement in a tile-based world: you send messages like "I moved one square to the right", the server double checks that and sends the correction. But what if I need acceleration-based system like for a race car game? You start slowly and gradualy increase your speed over time and when you release throtle, you loose speed depending on how fast you are moving right now.

When we tried implementing this system with our naive acceleration formula we ran into a problem: pawns move differently on server and client. That does NOT mean the sever's pawn (obviously) lags, that means after any movement action they end up in different places in the world. We only pass messages with the actions for the movement: that is if the player pressed "forward" we send "forwardON" and raise that flag on the server, similarly when the "forward" action key is released we send the appropriate message. I believe that is the way to do it for the acceleration system, right? You cannot send velocity as you will need to send 60 packets per second and you might still have trouble syncing everything.

So my question is: what sort of movement formula do you need to use for such scenarios and how do you send messages to make sure client and server are syncronized?

UPDATE: we already use smoothing, that is wenever the server and client is not far appart, we smooth the client's position to prevent client "jumping" from place to place. But the client's movement are often VERY different from the server's and that depends on how big lag is, that is why we need to improve our system.

Answer 1

Skew happens.

This is a clock synchronization problem.

Two nodes on a network can't know for sure what each other's clocks are. You can send the current time, but the receiver can't know for sure how old that value is. A good guess, though, is that it's stale by half the ping time. See http://en.wikipedia.org/wiki/Round-trip_delay_time.

One approach then, is to measure the ping time, and update it regularly. When the server gets a velocity-change message from the client, assume that the action occurred half the ping time in the past, and back compute it up to the present. The client must make similar assumptions about messages from the server. Include world time stamps on all the messages in both directions. Send regular "absolute position" updates as well, at whatever rate you can achieve.

And then your occasional smoothing-fixups, where absolute position is used, will be less pronounced.

Also relevant: http://en.wikipedia.org/wiki/Network_Time_Protocol

---

EDIT: Just saw this answer also, haven't viewed the answerer's link to a GDC presentation yet, but it sounds very interesting...

Why is there a huge update-delay in my client/server code?

GDC Presentation: http://www.gdcvault.com/play/1014345/I-Shot-You-First-Networking

Answer 2

Even in a fixed time-step environment(yes, you should use some sort of "turn based system" instead of timer, as you can easily slow down/up your turn duration), you will see math diverge.

This is a really trick problem called "determinism". Modern different hardware is non deterministic, especially when it comes to float math, due to specific acceleration adopted by HW.

One of the solution is to use flag or instruct your code-compiler-watever to stick to a less-fast-but-deterministic-math, like ieee745.

But sometimes this is not enught; on some system, specifically physic engine, there are a lot of things going on and sharing state and such, that in the end even on the same hardware, if the simulation is "replicated" and run you may see it diverge.

For example, in math z=x+y and then z+=k is the same as z=x+k, z+=y; but on computer work this is not true, as if the operation truncate parts of mantissa (see ieee754) you will get a (really small) difference. That will add up. Every step, and when an objects with a little error come touching another object with a little error... Here you have.

Technically, a full deterministic system (physic, AI, logic, same random seed) only need to synchronize user inputs, with a drastically reduction of needed bandwidth, and great smooth experience is case of great lag but low player density; but it comes with really enormous problem.

Already talked about using your own time system (aka turn) if the client hardware is fine and make a turn in 1ms, and youbwant logic run at 60fps, you have a lot of spare time. If timer are off, you can easily double the logic fps to catch up the missed frame, or slow it down to wait server.

Now talking about lag. One system is that server physic is old of about 200/300ms; when it get an action, if it is older than current state will be dropped, if newest put in queue, then execute the queue for that turn, and send, if needed, some info about what happened to client (like: at turn 10 x is dead) to be sure to have client synchronized about important things.

Client will have one world, synchronized from server, then every turn it will create a copy and step it for the missing turn (remember server is 200/300ms old) adding its own queue, and then display the results if that "estimation".

That is gonna prevent YOURSELF from jumping around, as long as your ping is < 200/300ms.

Smooth still need be applied to smooth out lag from others player, (their command may get to you with 200/300ms late worst case) but will be less visible, especially if in low-player density area, as the mob moves should be deterministic.

This is obviously only one way of doing it, there are a lot of great resource about this problematic, and one of the most complete I've found is the official valve engine's doc. Read about professional with a great knowledge and skill "solve" the problem here https://developer.valvesoftware.com/wiki/Source_Multiplayer_Networking

Answer 3

From what I understand your question can be boiled down to one simple problem: the input from each player is applied to the shared game state in different order.

In the image above I am illustrating this problem with the coloured dots (which represent the players' input). Assuming 3 players, their shared game state should be the one labeled "real order". This would be the case only if there was no lag. Because of the lag though, we end up with the last line of game state where the players' inputs are delayed and out of order.

I think that to solve this problem one has to think about the basic game loop: gather input -> update state -> render. The server's game loop would probably look like this: receive input -> update state -> send state. Storing the inputs and the states would provide the advantage of being able to "rewrite history":

• receive input with time info and store it
• update the corresponding state and store it
• update all subsequent states until the current one and store them
• send the current state to players

What this allows us not is to store multiple states and storing multiple states will allow us to solve the problem of applying player input at the wrong frames.

Let's take a simple example to illustrate my point:

• t1
  • Player 1 (no lag) inputs something (P1-t1)
  • Player 2 (1 frame lag) inputs something (P2-t1)
  • Player 3 (2 frames lag) inputs something (P3-t1)
  • server receives input P1-t1
  • server evaluates input P1-t1 on f0 producing f1
  • server sends f1 to players
• t2
  • server receives lagged input P2-t1
  • server evaluates input P1-t1 and P2-t1 on f0 producing a new f1
  • server evaluates no input on f1 producing f2
  • server sends f2 to players
• t3
  • Player 1 inputs something (P1-t3)
  • server receives input P1-t3 and lagged input P3-t1
  • server evaluates input P1-t1, P2-t1 and P3-t1 on f0 producing a new f1
  • server evaluates no input on f1 producing f2
  • server evaluates input P1-t3 on f2 producing f3
  • server sends f3 to players
• t4
  • server receives no input
  • server evaluates no input on f3 producing f4
  • server sends f4 to players

Using this technique on the server side would make sure that the game state is in sync on the server. Using the same technique on the client side would make sure the game state is in sync on the clients as well. All this though is assuming that the game is deterministic.

Of course some kind of housecleaning will have to be done to free some memory. I think a simple technique for that would be to force each client to send a "noop" whenever there has been no input from the player to know which states have been fully evaluated.

I hope this helps.