310 18.BelievableDeadReckoningforNetworkedGames
18.3PickanAlgorithm,AnyAlgorithm
If you crack open any good 3D math textbook, you’ll find a variety of algorithms
for defining a curve. Fortunately, we can discard most of them right away be-
cause they are too CPU intensive or are not appropriate (e.g., B-splines do not
pass through the control points). For dead reckoning, we have the additional re-
quirement that the algorithm must work well for a single segment of a curve
passing through two points: our current location
0
P
and the estimated future loca-
tion
1
P
. Given all these requirements, we can narrow the selection down to a few
types of curves: cubic Bézier splines, Catmull-Rom splines, and Hermite curves
[Lengyel 2004, Van Verth and Bishop 2008].
These curves perform pretty well and follow smooth, continuous paths.
However, they also tend to create minor repetitive oscillations. The oscillations
are relatively small, but noticeable, especially when the actor is making a lot of
changes (e.g., moving in a circle). In addition, the oscillations tend to become
worse when running at inconsistent frame rates or when network updates don’t
come at regular intervals. In short, they are too wiggly.
ProjectiveVelocityBlending
Let’s try a different approach. Our basic problem is that we need to resolve two
realities (the current
0
P
and the last known
0
P
). Instead of creating a spline seg-
ment, let’s try a straightforward blend. We create two projections, one with the
current and one with the last known kinematic state. Then, we simply blend the
two together using a standard linear interpolation (lerp). The first attempt looks
like this:
2
00 0
1
2
ttt
TT
PPV A
(projecting from where we were),
2
00 0
1
2
ttt
TT
PPV A
(projecting from last known),
ˆ
tt tt
PPP
(combined).
This gives
t
, the dead-reckoned location at a specified time. (Time values
such as
t
and
ˆ
are explained in Section 18.4.) Note that both projection equa-
tions above use the last known value of acceleration
0
A
. In theory, the current
projection
t
P
should use the previous acceleration
0
A
to maintain
2
C
continuity.
However, in practice,
0
A
converges to the true path much quicker and reduces
oscillation.