deadreckoning.htm

3D游戏开发领域专家撰写的经典游戏开发启迪性文章之一

extrapolating position. More sophisticated algorithms used in DIS also consider
orientation (roll, pitch, and heading) of entities and even extrapolate moving
parts of entities. For example, a tank that scans its turret back and forth
while patrolling could make use of dead reckoning for both the tank's position
and the angle of the turret on the tank.

<H3><FONT COLOR=YELLOW><I>Putting Dead Reckoning to Work</I></FONT></H3>

<P><A href="#list1">Listing 1</A> shows a fragment of a program that receives
entity state PDUs from other programs on the network and displays all the
entities it knows about, using dead reckoning algorithm 2 from
<A href="#figure2">Figure 2</A>. The code is C++ style, though the class
definitions, program initialization, and other details are not shown.

<P>The program's primary loop first checks to see if there are any new packets
available from the network (<TT>#1</TT>). DIS uses UDP for its communications,
and so here we use a Java-like UDP socket class to access UDP packets. Next,
the raw packets are parsed and converted to entity state PDU objects, which
contain information about remote entities' position, velocity, and identity.

<P>If this entity is already known to the program (that is, its ID exists in
<TT>TankList</TT>), the position and velocity for the entity are updated.
Otherwise, a new entry in the <TT>TankList</TT> table is created
(<TT>#3</TT>). The time of receipt is stored in the remote vehicle table
(<TT>ctime</TT> is a function that returns the current time); this is required
for dead reckoning.

<P>After the new packet is received, the locations of all entities in
<TT>TankList</TT> are updated using dead reckoning (<TT>#4</TT>) and are
displayed on the screen (<TT>#5</TT>). Dead reckoning does not overwrite
the received position, which may be needed for further dead reckoning at
a later time.

<P><A href="#list2">Listing 2</A> shows a fragment of a program that sends
information to the network about a tank it's simulating. It follows the rules
of dead reckoning as well. The program repeatedly updates vehicle
<TT>myTank</TT> based on inputs from the joystick controller. After each
update, it checks to see if the dead reckoning threshold has been exceeded.
If it has, it sends out a new PDU describing the updated state. The program
sends one entity state PDU at startup to let other players on the network
know that the vehicle <TT>myTank</TT> exists and that the program must remember
the last state information and time it sent out.

<A NAME="list1">
<CENTER><P><TABLE WIDTH=65% CELLPADDING=0 CELLSPACING=0>
<TR><TD>
<TABLE><TR><TD>
<PRE><FONT COLOR=#FF0000 FACE=Courier SIZE=2>
main()
{
	//Receiving Simulation
	DataGramSocket socket1;
	DataGramPacket packet1;
	EntityStatePDU espdu1;
	TankList remoteTanks;
	int i;

	// Initialization code: open socket, etc.
	// ... (Not shown here)

	// Enter a loop, receiving and processing remote
	// information forever
	while(1)
	{
		//Receive a new packet
		if(socket1.packetAvailable()) //#1
		{
			socket1.receive(&amp;packet1);
			espdu1.convertFromRawPacket(&amp;packet1); //#2
			if(TankList.member(espdu1.entityID()) //#3
				TankList.update(espdu1,ctime());
			else
				TankList.addEntity(espdu1,ctime());
		}
	
		// Display all known vehicles
		for (i = 0; i < TankList.size(); i++) //#4
		{
			TankList[i].setDRposition(
				TankList[i].rcvdPosition() + 
				TankList[i].rcvdVelocity() * 
				(ctime() - TankList[i].rcvdTime);
			TankList[i].display(TankList[i].DRposition()); //#5
		}
	}
}
</FONT></PRE>
</TD></TR></TABLE>
</TD></TR>
</TABLE></CENTER></a>

<A NAME="list2">
<CENTER><P><TABLE WIDTH=65% CELLPADDING=0 CELLSPACING=0>
<TR><TD>
<TABLE><TR><TD>
<PRE><FONT COLOR=#FF0000 FACE=Courier SIZE=2>
main()
{
	//Sending Simulation
	Joystick stick1;
	DataGramSocket socket1;
	EntityStatePDU espdu1;
	tank myTank(initPosition);
	int i;

	// At init time, send a PDU and save info
	espdu1.initializeWithPosition(myTank.Position());
	socket1.send(espdu1.convertToRawPacket());
	lastStateSent = myTank;
	lastTimeSent = ctime();

	while(1)
	{
		//Update my tank based on joystick
		myTank.calcNewPosition(JoyStick.read());

		//Calculate Dead Reckoned Position
		myTank.setDRposition(lastStateSent.position() + 
			lastStateSent.velocity() * (ctime() - lastTimeSent);
		
		//Only send an update if DR threshold exceeded
		if(abs(myTank.position() - lastStateSent.position() &gt; thresh)
		{
			socket1.send(espdu1.convertToRawPacket());
			lastStateSent = myTank;
			lastTimeSent = ctime();
		}
	}
}
</FONT></PRE>
</TD></TR></TABLE>
</TD></TR>
</TABLE></CENTER></a>

<H3><FONT COLOR=YELLOW><I>Extensions to Dead Reckoning</I></FONT></H3>

<P>DIS uses dead reckoning primarily as a means to extrapolate position and
orientation of vehicles, and it does so via polynomial algorithms. DIS
applications have extended dead reckoning in one way to allow extrapolation
of articulated parts of vehicles (for example, turrets on tanks).

<P>The DARPA ADS architecture study recognized the value of dead reckoning and
extended the concept to apply to all attributes of objects on the network
and to a larger class of extrapolation. Extrapolations using these expanded
definitions are referred to as predictive contracts.

<P>For example, in a tank battle simulation, a predictive contract called "drive
along road to waypoint" could be defined. Under this predictive contract,
a computer simulating a tank would only have to send out one piece of information
about a vehicle: it was at a certain position on a road, and it was going
to drive down that road to a specified point.

<P>As long as all other computers on the network agree on what it means to "drive
down a road" (for example, that you drive on the right) and all the computers
on the network know the definition of the road the tank is on, all the computers
on the network can create consistent views of the tank without requiring
any network traffic. Of course, if the tank deviates from its planned path
or changes state in any other unpredictable way, new state information for
the tank would be sent out on the network. Additional predictive contracts
could define when the tank turns its sensors on and off, when it sends out
radio reports, and other attributes of the tank's behavior.

<P>The advent of the Java model of distributed object computing allows a further
refinement of predictive contracts. In the DIS model all dead reckoning
algorithms are defined at compile time; there is no way for a simulation
to create new dead reckoning algorithms at run time. With languages such
as Java, however, a simulation could distribute updated predictive contracts
across the network at will.

<H3><FONT COLOR=YELLOW><I>Make the Most of Dead Reckoning</I></FONT></H3>

<P>Dead reckoning and predictive contracts offer dual benefits for networked
simulations and games. They hide the latencies inherent in the network, and
they offer the additional benefit of keeping traffic off the network by allowing
simulations to transmit information only when really needed. In DIS, dead
reckoning also allows entity state information be transmitted via best-effort
communications (such as UDP/IP) rather than more expensive, reliable (such
as TCP/IP) mechanisms. This is because dead reckoning can be used to smooth
over gaps when packets are lost, albeit with some loss of synchronization
across the network.

<P>Dead reckoning is not free. It requires that every computer on the network
run an algorithm to extrapolate each entity in the simulation scenario. Also,
if all the entities in a simulation behave unpredictably all the time, dead
reckoning offers little gain. However, it has been the experience in DIS
that dead reckoning offers significant advantages in large scenarios with
many computer-generated entities. In such situations, and where processor
cycles can be traded off to reduce network use and apparent latency, dead
reckoning can be a very effective optimization technique.</P>

<!--Bottom Navigation-->
<A NAME="bottom"></A>
<!--End Bottom Navigation-->
</STRONG>
</FONT>
<!--End Body-->
<!--Bottom-->
<BR>
<IMG SRC="gradbar.jpg">
<BR>
<FONT SIZE=2 COLOR=#8B8B8B FACE=Helvetica>
<I><font color="#FBFBFB">T</font><font color="#F7F7F7">h</font><font color="#F3F3F3">e</font><font color="#EFEFEF"> </font><font color="#EBEBEB">G</font><font color="#E7E7E7">a</font><font color="#E3E3E3">m</font><font color="#DFDFDF">e</font><font color="#DBDBDB"> </font><font color="#D7D7D7">P</font><font color="#D3D3D3">r</font><font color="#CFCFCF">o</font><font color="#CBCBCB">g</font><font color="#C7C7C7">r</font><font color="#C3C3C3">a</font><font color="#BFBFBF">m</font><font color="#BBBBBB">m</font><font color="#B7B7B7">i</font><font color="#B3B3B3">n</font><font color="#AFAFAF">g</font><font color="#ABABAB"> </font><font color="#A7A7A7">M</font><font color="#A3A3A3">e</font><font color="#9F9F9F">g</font><font color="#9B9B9B">a</font><font color="#979797">S</font><font color="#939393">i</font><font color="#8F8F8F">t</font><font color="#8B8B8B">e</font> -