Now that we have a simple movement algorithm and a list of unit collisions, what else do we need to get decent unit cooperation? Position prediction.
Predicted positions are simply a set of positions (with associated orientations and time stamps) that indicate where an object will be in the future (see Figure 4 below). A movement system can calculate these positions using the same movement algorithm that's used to move the object. The more accurate these positions are, the more useful they are. Position prediction isn't immediately free, though, so let's look at how to offset the additional CPU usage.
The most obvious optimization is to avoid recalculating all of your predicted positions at every frame. A simple rolling list works well (see Figure 5 below); you can roll off the positions that are now in the past and add a few new positions each frame to keep the prediction envelope at the same scale. While this optimization doesn't get rid of the start-up cost of creating a complete set of prediction positions the first time you move, it does have constant time for the remainder of the movement.
Figure 4. A closer look at the predicted positions.
The next optimization is to create a prediction system that handles both points and lines. Because our collision determination system already supports points and lines, it should be easy to add this support to our prediction system. If a unit is traveling in a straight line, we can designate an enclosed volume by using the current position, a future position, and the unit's soft movement radius. However, if the object has a turn radius, things get a little more complicated. You can try to store the curve as a function, but that's too costly. Instead, you're better off doing point sampling to create the right predicted points (see Figure 6 below). In the end, you really want a system that seamlessly supports both point and line predictions, using the lines wherever possible to cut down on the CPU cost.
Figure 5. Rolling list of predicted positions.
The last optimization we'll cover is important and perhaps a little nonintuitive. If we're going to get this predicted system with as little overhead as possible, we don't want to duplicate our calculations for every unit by predicting its position and then doing another calculation to move it. Thus, the solution is to predict positions accurately, and then use those positions to move the object. This way, we're only calculating each move once, so there's no extra cost aside from the aforementioned extra start-up time.
Figure 6. Using predicted positions with a turn radius.
In the actual implementation, you'll probably just pick a single update length to do the prediction. Of course, it's fairly unlikely that all of the future updates will be consistent. If you blindly move the unit from one predicted position to the next without any regard to what the actual update length currently is, you're bound to run into some problems. Some games (or some subset of objects in a game) can accept this inaccuracy. Those of us developing all the other games will end up adding some interpolation so that can quickly adjust a series of predicted points that isn't completely accurate. You also need to recognize when you're continually adjusting a series of predicted positions so that you cut your losses and just recalculate the entire series.
Most of the rest of the implementation difficulties arise from the fact that we use these predicted positions in collision detection just as we do for the object's actual current position. You should easily see the combinatorial explosion that's created by comparing predicted positions for all units in a given area. However, in order to have good coordinated unit movement, we have to know where units are going to be in the near future and what other units they're likely to hit. This takes a good, fast collision determination system. As with most aspects of a 3D engine, the big optimizations come from quickly eliminating potential interactions, thus allowing you to spend more CPU cycles on the most probable interactions.