How to implement dead reckoning when turning is involved?

Question

"Dead reckoning is the process of estimating one's current position based upon a previously determined position and advancing that position based upon known or estimated speeds over elapsed time, and course." (Wikipedia)

I'm currently implementing a simple server that makes use of dead reckoning optimization, which minimizes the updates required by making logical assumptions on both the clients and the server.

The objects controlled by users can be said to be turning, or not turning. This presents an issue with dead reckoning (the way I see it.)

For example, say you have point A in time defined by [position, velocity, turning: left/right/no]. Now you want point B after t amount of time. When not turning, the new position is easy to extrapolate. The resulting direction is also easy to extrapolate. But what about when these two factors are combined? The direction of the velocity will be changing along a curve as the object is turning over t amount of time.

Should I perhaps go with another solution (such as making the client send an update for every new direction rather than just telling the server "I'm turning left now")?

This is in a 2D space, by the way, for the sake of simplicity.

Answer 1

Well, I think "turning: left/right/no" is insufficient to determine position B - you also need to know the arc at which the turn is being made. If you are turning left along a circular path of radius 1, you will end up at a different place than if you are turning along a circular path of radius 10, even though your initial position, velocity, and direction of turn will all be the same.

If making the client send an update for every new direction and treating them as linear segments is an option, that is going to be a much easier calculation to make. You can simply treat each new report from the client as a vector, and sum them. Calculating a bunch of curves is going to be more complex.

Answer 2

For simplicity let's say that your vehicles have a turning radius r that's independant of speed. So to compute the new position given the initial coords and the time:

• compute the distance (that's velocity * time)
• compute how much you turned (that's distance / (2*pi*r))
• add that arc to the original position.

The last steps needs elaboration.

Given the angle a computed in step 2, if you started at (0,0) with a due north heading (i.e. pi/2 radians) and are turning left then your new positions is: (r*cos(a)-1, r*sin(a)).

If your original heading was different, say it was "b", then simply rotate the new position accordingly, i.e. multiply by this rotation matric:

 [ cos b , -sin b ]
 [ sin(b), cos(b) ]

Finally, add the initial position and you're done. Now you only need to send an update if you change the velocity or turning direction.