Dead Reckoning

From BZFlagWiki
Revision as of 23:25, 21 February 2007 by Brad (Talk | contribs) (add category)

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 know point.

It is used in Distributed Interactive Simulation to save the bandwidth in the communication between two different network entities, when exchanging positional information of the object. It starts from a kinematic model of the object.

Let explain that with simple cases around the entity that own the object (A), and the entity that should receive the positional update (B). Name this object tank.

A is updating is tank position continuosly, taking into account the environment, the player wished, and the physics (virtual) laws that the game impose. Continuosly just means any frame. A is the master (driver) of the tank. B is following with A, using A provided info to update is local copy of the tank. B is a slave.

Let assume at first a 0 delay network.

First approach could be for A to communicate the tank position to B any time (frame) it is updating its internal tank representation. B uses these message to change its internal copy of the tank and uses the last arrived data, whenever tank info should be used. This is a bandwidth wasting!

To save bandwidth, A and B could share a DR model of the tank.

After having A updated is tank position, without taking into account the DR model, and just before sending, A compare the current tank position with a predicted tank position, taking now into account the DR model. If the two object representation are not so different, below a threshold, it just avoids sending data. B, when no data is arriving, uses the DR model to know the position of the tank. That is not a futured position. It is just the current position with an error maximized by the threshold. Tank position is however updated periodically, to allow for new player entering in the game. For this to work, we should add DR model parameters to the updated data.

This way we do not send tank update when the position can be accurately derived by the old data, saving bandwidth.

Let assume now a fixed delay network.

With the same behaviour described above, A send its data to B. B update is tank representation with just the same rules above. Forgetting the network delay, 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.

What happens with a jittered network?

With jitter, the fastest packets arrive with a delay that is near the minimum path route, while some other packets arrives later, due to some network bottleneck. Now the tank updates from A to B does not arrive just delayed, but sometimes there is an event time compression, sometimes a time expansion, without A knowing anything about it. If B takes into account this message without any time correction the two prediction algorithm, A & B, behave not the same. And DR is going to alter the perception of A tank in B, not just delaying his history, but changing its trajectory.

One of the most effect of this behaviour is when A cannot control its tank so the DR algorithm works saving much. Jumping! Probably, during jumping A send just few updates, let us assume that it will send 4 updates: beginning, half of the raise, top, half of descent, landing. So take an example.

Tank start to jump, so it send an update. The next update suffers from network congestion, so it is seen delayed at B side. In the mean time, B continue to predict the tank position. When tank is seen at B at half descent, the delayed message was received, so B put back is local view of the tank at the half raise point, where the local view of tank continue is raising. After a while a new update is received putting the tank again forward to his top and half descent position.

I see lot of time this while playing.

To correct this, we should compute the network jitter, and use this to correctly position the tank in time & space as view by the DR algorithm, so it can continue to work happily. The "fixed" (unknown) network delay still apply, 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.