|
 Features
Discrete vs. Continuous Simulation
Most movement
algorithms are discrete in nature. That is, they move the unit from point
A to point B without considering what might be between those two points,
whereas a continuous simulation would consider the volume between the
two points as well. In a lag-ridden Internet game, fast moving units can
move quite a distance in a single game update. When discrete simulations
are coupled with these long updates, units can actually hop over other
objects with which they should have collided. In the case of a resource
gathering unit, no one really minds too much. But players rarely want
enemy units to be able to walk through a wall. While most games work around
this problem by limiting the length of a unit's move, this discrete simulation
problem is relatively easy to solve (see Figure 3 below).
Figure 3. Solving the problem with discrete movement simulation.
|
One
way to solve the problem is to sub-sample each move into a series of several
smaller moves. Taking the size of the moving unit into account, we make
the sampling interval small enough to guarantee that no other unit can
fit between two of the sample points. We then run each of those points
through the collision determination system. Calculating all of those points
and collisions may seem overly expensive, but later on we'll see a potential
way to offset most of that cost.
Another method is to create what we'll call a move line. A move line represents
the unit's move as a line segment starting at point A and ending at point
B. This system creates no extra data, but the collision check does have
an increase in complexity; we must convert from a simple spherical collision
check to a more expensive calculation that involves finding the distance
from a point to a line segment. Most 3D games have already implemented
a fast hierarchical system for visible object culling, so we can reuse
that for collision culling. By quickly narrowing down the number of potential
collisions, we can afford to spend more time checking collisions against
a small set of objects.
 Predicted
Positions
|
|
|
|
|
