Linear Dead Reckoning in Winsock application

Question

I'm having a little difficulty understanding how I implement Dead Reckoning in my Server-Client Winsock game.

I've been looking on the internet for a decent explanation that explains exactly:

1. When a message should be sent from the server to the client

2. How the client should act if it doesn't receive update messages, does it keep using the predicted position as the current position in order to calculate the new predicted position?

The Dead Reckoning method I am using is:

path vector = oldPosition - oldestPosition
delta time = oldTime - oldestTime
delta velocity = path vector / delta time
new delta time = current time / oldest time
new prediction = oldPosition + new delta time * delta velocity

Hope this is the correct formula to use! :)

Should also note the connection type is UDP and that the game is played only on the server. The server sents update messages to the client.

Can anyone help by answering my questions please?

Thanks

Answer 1

Dead reckoning requires a group of variables to function - called a kinematic state - typically containing position, velocity, acceleration, orientation, and angular velocity of a given object. You can choose to ignore orientation and angular velocity if you are only looking for the position. Post a comment if you are looking to predict orientation as well as position, and I'll update my answer.

A standard dead reckoning algorithm for networked games is shown here:

The above variables are described like so:

P_t: The estimated location. Output

P_O: The most recent position update of the object

V_O: The most recent velocity update of the object

A_O: The most recent acceleration update of the object

T: The elapsed seconds between the current time and the timestamp of the last update - NOT the time the packet was received.

This can be used to move the object until an update is received from the server. Then, you have two kinematic states: the estimated position (the most recent output of the above algorithm), and the just received, actual position. Realistically blending these two states can be difficult.

---

One approach is to create a line, or even better, a curve such as Bézier splines Catmull-Rom splines and Hermite curves (a good list of other methods is here), between the two states while still projecting the old orientation into the future. So, continue using the old state until you get a new one - when the state you are blending into becomes the old state.

Another technique is to use projective velocity blending, which is the blending of two projections - last known state and current state - where the current rendered position is a blend of the last known and current velocity over a given time.

This web page, quoting the book "Game Engine Gems 2", is a gold mine for dead reckoning:

Believable Dead Reckoning for Networked Games

EDIT: All of the above is just for how the client should act when it doesn't get updates. As for "When a message should be sent from the server to the client", Valve says a good server should send out updates at approximately a 15 millisecond interval, about 66.6 per second.

Note: the "Valve says" link actually has some good networking tips on it as well, using Source Multiplayer Networking as the medium. Check it out if you've got time.

EDIT 2 (the code update!):

Here is how I would implement such an algorithm in a C++/DirectX environment:

struct kinematicState
{
     D3DXVECTOR3 position;
     D3DXVECTOR3 velocity;
     D3DXVECTOR3 acceleration;
};

void PredictPosition(kinematicState *old, kinematicState *prediction, float elapsedSeconds)
{
     prediction->position = old->position + (old->velocity * elapsedSeconds) + (0.5 * old->acceleration * (elapsedSeconds * elapsedSeconds));`
}

kinematicState *BlendKinematicStateLinear(kinematicState *olStated, kinematicState *newState, float percentageToNew)
{
     //Explanation of percentateToNew:
     //A value of 0.0 will return the exact same state as "oldState",
     //A value of 1.0 will return the exact same state as "newState",
     //A value of 0.5 will return a state with data exactly in the middle of that of "old" and "new".
     //Its value should never be outside of [0, 1].

     kinematicState *final = new kinematicState();

     //Many other interpolation algorithms would create a smoother blend,
     //But this is just a linear interpolation to keep it simple.

     //Implementation of a different algorithm should be straightforward.
     //I suggest starting with Catmull-Rom splines.

     float percentageToOld = 1.0 - percentageToNew;

     final->position = (percentageToOld * oldState->position) + (percentageToNew * new-State>position);
     final->velocity = (percentageToOld * oldState->velocity) + (percentageToNew * newState->velocity);
     final->acceleration = (percentageToOld * oldState->acceleration) + (percentageToNew * newState->acceleration);

     return final;
}

Good luck, and uh, if you happen to make millions on the game, try and put me in the credits ;)

Answer 2

This is a general and broad question to answer.

If you're implementing a game server with dead reckoning on the client side (as I assume you're doing), you should keep estimating the values as long as you don't get a new input from the server. At that point you should force a refresh of the new position / time / whatever you store. No server response means you'll have to estimate by yourself based on the most up-to-date estimate.

By the way it seems to me that the following

new delta time = current time / oldest time

should rather be something like

new delta time = current time - oldTime

in order to get the time elapsed before the last prediction. Otherwise you would assume that the system went faster when more time elapsed and slower when few time (compared to the oldest time used as a unit) elapsed. The linear motion equation (not accelerated) is new_s = s_0 + vel * t