2. Dead Reckoning –
Extrapolation
Early
distributed simulation projects, such as Distributed
Interactive Simulation
(DIS), dealt with moving objects having high-inertia movements. In
this aircraft simulation context, uniform rectilinear movements are
the norm, and variation from these occur in a gradual way. It is then
possible to replicate the movements by simulating a replica of an
actuated entity, and applying behaviour change events.
For example,
if the actuated entity reduces its speed by s, an update is
sent to the replica to make it reduce its speed by s as well.
Of course, the update can take a non-negligible time to transit from
the actuator to the observer. The position of the replica is
extrapolated until the update is received, leading to a position
correction, thus the actual path observed on the replica may be
slightly different than the original one.
This positional inaccuracy
may be lowered by introducing additional information in the update
message: for example a timestamp stating from which point the speed
change was done will make the replicated path finally rejoin the
original one, although the temporary phase during when the update
message is transitting will have a different path.
Then,
we need to implement an algorithm that will blend the temporary
inaccurate path with the corrected path, the result of which will
depend on the depth of the blending (using the history of previously
received positions, for example [Bernier]).
Figure 1: Dead Reckoning: sending an
update
when the replicated path differs too much
from the
original path [Aronson]
To reduce the frequency
of updates, we can send an update only when the original path and the
replicated path diverge by a defined amount (Figure 1) (it may then
be necessary to run both the master entity and the replicate by the
master process to compare them). We now have a dead
reckoning system
(see prototype screenshot on Figure 2), named after the ancient naval
navigation techniques used when the stars were not visible.
Figure 2: Nevrax’ 2D Dead Reckoning
Prototype
from early 2000, showing
original and replicated path superimposed
This system may even
be made to deal with non-reliable but lightweight network protocols,
such as UDP: by regularly sending a 'keep-alive' update even when no
change has occurred, all observers tend to finally get up-to-date
information, even if a message has been lost. This keep-alive is also
useful to populate the list of known entities for a new connecting
client, and to notify the disconnection of an entity (disconnection
is assumed when no keep-alive is received for a predetermined amount
of time).
However, in most
MMORPG the primary controlled avatar is a humanoid, which is not
known for high-inertia movements but random movements. Using Dead
Reckoning would lead to frequent state correction updates, increasing
both network traffic and visible jolts (because a quick position jump
is sometimes needed when the blended replicated path differs to much
from the original path).
Dead Reckoning may still be used for
vehicles, AI entities having steady movements (although too steady
movements for AI entities might not be wanted, because of their
unnatural feeling). To allow for a large number of player-controlled
entities, we focused on a different strategy: transmitting "good-old"
position updates, but simulating interpolated natural movement in a
virtual time space and maintaining total control of update frequency.
|
Printer-Friendly Version
