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).
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.