Dead Reckoning

From BZFlagWiki
Revision as of 17:52, 27 January 2009 by RatOmeter (Talk | contribs)

Jump to: navigation, search

This page should give information and suggestion on what Dead Reckoning (DR) is, how it is implemented, what it should be.

DR is a method to find the current position by measuring the course and distance from a past known point. It is used in Distributed Interactive Simulation to conserve bandwidth in the communication between two different network entities, when exchanging position information of a moving object. It starts with a kinematic model of the object.

Let's explain with a simple case including an object which we'll call "Tank" that is owned by entity (A). There is a second entity (B) that should receive position updates for Tank. A is updating Tank's position continuously, taking into account the environment, the Tank driver's control inputs, and the physics (virtual) laws that the game imposes. "Continuously" means at some periodic rate. A is the master (driver) of the tank. B recreates the position and orientation of A's Tank locally using data provided by A. B's tank is a slave.

Let's first assume a 0 delay network.

One approach could be for A to communicate the tank position and orientation to B any time it updates its own internal tank representation. B uses these messages to update its internal copy of the tank, using the newest data to have arrived. Unfortunately, this wastes bandwidth!

To conserve bandwidth, A and B could share a Dead Reckoning (DR) model of the tank.

When A has updated its Tank position, instead of blindly sending a position update, A compares the current tank position to a predicted tank position that is calculated via the DR model. If the "real" and predicted object representations are the same (or nearly the same within a tolerance) it does not send an update message to B. With no update received from A, B uses its DR model to calculate the position of the tank. That is not a future position. It is the actual current tank position with no more error than is allowed by the tolerance. However, the true tank position *is* updated periodically, to allow for new player's entering in the game. To enable all players' DR models to remain synchronized, we must add DR model parameters to the update messages. In this way we only send tank updates when the position cannot be accurately derived by the old data, thus saving bandwidth.

Now let's assume a fixed delay network.

With the same behavior described above, A send its data to B. B updates its tank representation with the same rules outlined above. B has the "correct" representation of the object, and its history, but just delayed by the network. Here Dead reckoning is not going to "predict" any position, B behaves the same as if DR is not used, (i.e. A send tank updates any frames). Data futuring is not in the game.

Now let's consider a network with jitter.

With jitter, the fastest packets arrive with a delay that is near the minimum path route, while some other packets arrive later, due to some network bottleneck. Now the tank updates from A to B not only arrive delayed, but sometimes with a change in that delay, causing effects of time compression and expansion that A is not aware of. If B uses these update messages without any time correction between the two entity's prediction algorithms, A & B will not behave the same. The result is that DR is going to alter the perception of A 's tank at B, not just by (network) delay of its history, but also by potentially changing its trajectory. The adverse effects are increased with increasing jitter.

One of the most serious effects of this is seen when A's driver is not in control of its tank (e.g. jumping or falling). With no other input, it is only the world "physics" and the DR algorithm operating and relatively few updates are sent to B. Using a jump as an example, A may send just a few updates, perhaps just at the jump start, halfway through the rising arc, top, halfway through the descent and then upon landing. So take an example.

Tank starts to jump, so A sends an update. The next update suffers from network congestion, so it is seen delayed at the B side. In the meantime, B continues to predict the tank position. When the tank is seen at B at half descent, the delayed message was received, so B reverts its local view back to the half rise point, where the local view of the tank is continuing to rise. Later, a new update is received, suddenly putting the tank in a new forward, descending position. The visual effect at player B's perspective is a tank that rapidly jumps between different positions and trajectories.

This is currently a problem that is often viewable while playing.

To correct this, we should compute the network jitter, and use this to correctly position the tank in time & space as viewed by the DR algorithm, so it can continue to work happily. The "fixed" (unknown) network delay still applies, so our local tank representation is still delayed and, apart the network congestion event, where we blindly predict the future, truely reflect the remote one.