Coordinated Unit Movement

By
Dave C. Pottinger
Gamasutra
January 22, 1998
Vol. 3: Issue 3

Originally
Published in Game Developer Magazine, January, 1999.

Coordinated Unit Movement

Introduction Movement Issues Facing Game Developers Simple Movement Algorithm Collision Determination Discrete vs. Continuous Simulation Predicted Positions Unit to Unit Cooperation Basic Planning Basic Definitions

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.

Figure 4 A closer look at the predicted positions.

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 5 Rolling list of 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 6 Using predicted positions with a turn radius.

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.

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.