322 18.BelievableDeadReckoningforNetworkedGames
■ When working with lots of actors, consider adjusting the ground clamping
based on distance to improve performance. You can replace the three-point
ray multicast with a single point and adjust the height directly using the inter-
section normal for orientation. Further, you can clamp intermittently and use
the offset from prior ground clamps.
■ For character models, it is probably sufficient to use single-point ground
clamping. Single-point clamping is faster, and you don’t need to adjust the
orientation.
■ Consider supporting several ground clamp modes. For flying or underwater
actors, there should be a “no clamping” mode. For vehicles that can jump,
consider an “only clamp up” mode. The last mode, “always clamp to
ground,” would force the clamp both up and down.
18.7Orientation
Orientation is a critical part of dead reckoning. Fortunately, the basics of orienta-
tion are similar to what was discussed for position. We still have two realities to
resolve: the current drawn orientation and the last known orientation we just re-
ceived. And, instead of velocity, there is angular velocity. But that’s where the
similarities end.
Hypothetically, orientation should have the same problems that location had.
In reality, actors generally turn in simpler patterns than they move. Some actors
turn slowly (e.g., cars) and others turn extremely quickly (e.g., characters). Either
way, the turns are fairly simplistic, and oscillations are rarely a problem. This
means
1
C
and
2
C
continuity is less important and explains why many engines
don’t bother with angular acceleration.
MythBusting—Quaternions
Your engine might use HPR (heading, pitch, roll), XYZ vectors, or full rota-
tion matrices to define an orientation. However, when it comes to dead reck-
oning, you’ll be rotating and blending angles in three dimensions, and there is
simply no getting around quaternions [Hanson 2006]. Fortunately, quaterni-
ons are easier to implement than they are to understand [Van Verth and Bish-
op 2008]. So, if your engine doesn’t support them, do yourself a favor and
code up a quaternion class. Make sure it has the ability to create a quaternion
from an axis/angle pair and can perform spherical linear interpolations
(slerp). A basic implementation of quaternions is provided with the demo
code on the website.
18.7Orientation 323
Vec3 angVelAxis(mLastKnownAngularVelocityVector);
// normalize() returns length.
float angVelMagnitude = angVelAxis.normalize();
// Rotation around the axis is magnitude of ang vel * time.
float rotationAngle = angVelMagnitude * actualRotationTime;
Quat rotationFromAngVel(rotationAngle, angVelAxis);
Listing 18.3. Computing rotational change.
With this in mind, dead reckoning the orientation becomes pretty simple:
project both realities and then blend between them. To project the orientation, we
need to calculate the rotational change from the angular velocity. Angular veloci-
ty is just like linear velocity; it is the amount of change per unit time and is usual-
ly represented as an axis of rotation whose magnitude corresponds to the rate of
rotation about that axis. It typically comes from the physics engine, but it can be
calculated by dividing the change in orientation by time. In either case, once you
have the angular velocity vector, the rotational change
Δt
R
is computed as shown
in Listing 18.3.
If you also have angular acceleration, just add it to
rotationAngle. Next,
compute the two projections and blend using a spherical linear interpolation. Use
the last known angular velocity in both projections, just as the last known accel-
eration was used for both equations in the projective velocity blending technique:
Δ mag dir
quat ,
tt
R
RTR
(impact of angular velocity),
Δ 0tt
R
RR
(rotated from where we were),
Δ 0tt
R
RR
(rotated from last known),
ˆ
slerp , ,
ttt
STRR
(combined).
This holds true for
ˆ
1.0
T
. Once again,
ˆ
T
is clamped at one, so the math simpli-
fies when
ˆ
1.0
T
:
Δ 0tt
SRR
(rotated from last known).
324 18.BelievableDeadReckoningforNetworkedGames
TwoWrongTurnsDon’tMakeaRight
This technique may not be sufficient for some types of actors. For example, the
orientation of a car and its direction of movement are directly linked. Unfortu-
nately, the dead-reckoned version is just an approximation with two sources of
error. The first is that the orientation is obviously a blended approximation that
will be behind and slightly off. But, even if you had a perfect orientation, the re-
mote vehicle is following a dead-reckoned path that is already an approximation.
Hopefully, you can publish fast enough that neither of these becomes a problem.
If not, you may need some custom actor logic that can reverse engineer the orien-
tation from the dead-reckoned values; that is, estimate an orientation that would
make sense given the dead-reckoned velocity. Another possible trick is to publish
multiple points along your vehicle (e.g., one at front and one in back). Then, dead
reckon the points and use them to orient the vehicle (e.g., bind the points to a
joint).
18.8AdvancedTopics
This last section introduces a variety of advanced topics that impact dead reckon-
ing. The details of these topics are generally outside the scope of this gem, but, in
each case, there are specific considerations that are relevant to dead reckoning.
IntegratingPhysicswithDeadReckoning
Some engines use physics for both the local and the remote objects. The idea is to
improve believability by re-creating the physics for remote actors, either as a re-
placement for or in addition to the dead reckoning. There are even a few tech-
niques that take this a step further by allowing clients to take ownership of actors
so that the remote actors become local actors, and vice versa [Feidler 2009]. In
either of these cases, combining physics with dead reckoning gets pretty com-
plex. However, the take away is that even with great physics, you’ll end up with
cases where the two kinematic states don’t perfectly match. At that point, use the
techniques in this gem to resolve the two realities.
ServerValidation
Dead reckoning can be very useful for server validation of client behavior. The
server should always maintain a dead-reckoned state for each player or actor.
With each update from the clients, the server can use the previous last known
state, the current last known state, and the ongoing results of dead reckoning as
18.8AdvancedTopics 325
input for its validation check. Compare those values against the actor’s expected
behavior to help identify cheaters.
WhoHitWho?
Imagine player A (local) shoots a pistol at player B (remote, slow update). If im-
plemented poorly, player A has to “lead” the shot ahead or behind player B based
on the ping time to the server. A good dead reckoning algorithm can really help
here. As an example, client A can use the current dead-reckoned location to de-
termine that player B was hit and then send a hit request over to the server. In
turn, the server can use the dead-reckoned information for both players, along
with ping times, to validate that client A’s hit request is valid from client A’s per-
spective. This technique can be combined with server validation to prevent
abuse. For player A, the game feels responsive, seems dependent on skill, and
plays well regardless of server lag.
Articulations
Complex actors often have articulations, which are attached objects that have
their own independent range of motion and rotation. Articulations can generally
be lumped into one of two groups: real or fake. Real articulations are objects
whose state has significant meaning, such as the turret that’s pointing directly at
you! For real articulations, use the same techniques as if it were a full actor. For-
tunately, many articulations, such as turrets, can only rotate, which removes the
overhead of positional blending and ground clamping. Fake articulations are
things like tires and steering wheels, where the state is either less precise or
changes to match the dead-reckoned state. For those, you may need to implement
custom behaviors, such as for turning the front tires to approximate the velocity
calculated by the dead reckoning.
Path‐BasedDeadReckoning
Some actors just need to follow a specified path, such as a road, a predefined
route, or the results of an artificial intelligence plan. In essence, this is not much
different from the techniques described above. Except, instead of curving be-
tween two points, the actor is moving between the beginning and end of a speci-
fied path. If the client knows how to recreate the path, then the actor just needs to
publish how far along the path it is,
ˆ
T
, as well as how fast time is changing,
v
T
.
When applicable, this technique can significantly reduce bandwidth. Moyer and
Speicher [2005] have a detailed exploration of this topic.
326 18.BelievableDeadReckoningforNetworkedGames
DelayedDeadReckoning
The first myth this gem addresses is that there is no ground truth. However, one
technique, delayed dead reckoning, can nearly re-create it, albeit by working in
the past. With delayed dead reckoning, the client buffers network updates until it
has enough future data to re-create a path. This eliminates the need to project into
the future because the future has already arrived. It simplifies to a basic curve
problem. The upside is that actors can almost perfectly re-create the original path.
The obvious downside is that everything is late, making it a poor choice for most
real-time actors. This technique can be useful when interactive response time is
not the critical factor, such as with distant objects (e.g., missiles), slow-moving
system actors (e.g., merchant NPCs), or when playing back a recording. Note that
delayed dead reckoning can also be useful for articulations.
SubscriptionZones
Online games that support thousands of actors sometimes use a subscription-
zoning technique to reduce rendering time, network traffic, and CPU load [Cado
2007]. Zoning is quite complex but has several impacts on dead reckoning. One
significant difference is the addition of dead reckoning modes that swap between
simpler or more complex dead reckoning algorithms. Actors that are far away or
unimportant can use a low-priority mode with infrequent updates, minimized
ground clamping, quantized data, or simpler math and may take advantage of
delayed dead reckoning. The high-priority actors are the only ones doing frequent
updates, articulations, and projective velocity blending. Clients are still responsi-
ble for publishing normally, but the server needs to be aware of which clients are
receiving what information for which modes and publish data accordingly.
18.9Conclusion
Dead reckoning becomes a major consideration the moment your game becomes
networked. Unfortunately, there is no one-size-fits-all technique. The games in-
dustry is incredibly diverse and the needs of a first-person MMO, a top-down
RPG, and a high-speed racing game are all different. Even within a single game,
different types of actors might require different techniques.
The underlying concepts described in this gem should provide a solid foun-
dation for adding dead reckoning to your own game regardless of the genre. Even
so, dead reckoning is full of traps and can be difficult to debug. Errors can occur
anywhere, including the basic math, the publishing process, the data sent over the
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.