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

Before we dive into coordinated unit movement, let's take a look at some of the movement issues facing game developers today. Most of these have to do with minimizing CPU load versus maximizing the accuracy and intelligence of the movement.

Moving one unit versus moving multiple units. Moving one unit is generally pretty simple, but methods that work well for one unit rarely scale up effortlessly for application to hundreds of units. If you're designing a system for hundreds of units, it will need to be very conservative in its CPU use.

Some movement features are CPU intensive. Very few games that move hundreds of units support advanced behavior such as modeling the acceleration and deceleration of these units. The movement of large ships and heavily armored units has a lot more realism with acceleration and deceleration, but that realism comes at a high cost in terms of extra CPU usage. The actual movement calculation becomes more complicated because you have to apply the time differential to the acceleration to create the new velocity. As we extend our movement system to handle prediction, we'll see that acceleration and deceleration complicate these calculations as well. Modeling a turn radius is also difficult because many pathfinding algorithms are not able to take turn radii into account at all. Thus, even though a unit can find a path, it may not be able to follow that path because of turn radius restrictions. Most systems overcome this deficiency by slowing the unit down to make a sharp turn, but this involves an extra set of calculations.

Different lengths for the main game update loop. Most games use the length of the last pass through update loop as some indication of how much time to simulate during the next update pass. But such a solution creates a problem for unit movement systems because these lengths vary from one update to the next (see Figure 1 below). Unit movement algorithms work much better with nice, consistent simulation intervals. A good update smoothing system can alleviate this problem quite a bit.

Figure 1 Varied update lengths cause units to move differing distances each update.

Sorting out unit collisions. Once units come into contact with one another, how do you get them apart again? The naïve solution is just never to allow units to collide in the first place. In practice, though, this requirement enforces exacting code that is difficult to write. No matter how much code you write, your units will always find a way to overlap. More importantly, this solution simply isn't practical for good game play; in many cases, units should be allowed to overlap a little. Hand-to-hand combat in Ensemble Studios' recent title Age of Empires should have been just such a case. The restriction for zero collision overlap often makes units walk well out of their way to fight other units, exposing them to needless (not to mention frustrating) additional damage. You'll have to decide how much collision overlap is acceptable for your game and resolve accordingly.

Map complexity. The more complex the map is, the more complicated and difficult good movement will be to create. As game worlds and maps are only getting more intricate and realistic, the requirement for movement that can handle those worlds goes up, too.

Random maps or controlled scenarios? Because you can't hard-code feasible paths, random maps are obviously more difficult to deal with in many cases, including pathfinding. When pathfinding becomes too CPU intensive, the only choice (aside from reducing map complexity or removing random maps) is to decrease the quality of the pathfinding. As the quality of the pathfinding decreases, the quality of the movement system needs to increase to pick up the slack.

Maximum object density. This issue, more than anything, dictates how accurate the movement system must be. If your game has only a handful of moving objects that never really come into contact with one another (as is the case with most any first-person shooter), then you can get away with a relatively simple movement system. However, if you have hundreds of moving objects that need to have collision and movement resolution on the scale of the smallest object (for example, a unit can walk through a small gap between two other units), then the quality and accuracy requirements of your movement system are dramatically raised.