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

We've created a complex system for determining where an object is going to be in the future. It supports 3D movement, it doesn't take up much more CPU time than a simple system, and it provides an accurate list of everything we expected a unit to run into in the near future. Now we get to the fun part.

If we do our job well, most of the collisions that we must deal with are future collisions (because we avoid most of the immediate collisions before they even happen). While the baseline approach for any future collision is to stop and repath, it's important to avoid firing up the pathfinder as much as possible.

This set of collision resolution rules is a complete breakdown of how to approach the problem of unit-to-unit collision resolution (from a unit's frame of reference).

Unresolved collisions

Case 1. If both units are not moving:

1. If we're the lower-priority unit, don't do anything of our own volition.
   
   
2. If we're the higher-priority unit, figure out which unit (if any) is going to move and tell that unit to make the shortest move possible to resolve the hard collision. Change the collision state to resolving.

Case 2. If we're not moving, and the other unit is moving, we don't do anything.

Case 3. If we're moving and the other unit is stopped:

1. If we're the higher-priority unit, and the lower priority unit can get out of the way, calculate our "get-to point" (the point we need to get to in order to be past the collision) and tell the lower-priority unit to move out of our way (see Figure 7 below). Change the collision state to resolving.
   
   

   Figure 7 Resolving a collision between a moving unit and a stopped unit.

   
   
2. Else, if we can avoid the other unit, avoid the other unit and resolve the collision.
   
   
3. Else, if we're the higher-priority unit and we can push the lower-priority unit along our path, push the lower priority-unit. Change the collision state to resolving.
   
   
4. Else, stop, repath, and resolve the collision.
   

Case 4. If we're moving and the other unit is moving:

1. If we're the lower-priority unit, don't do anything.
   
   
2. If collision with hard radius overlap is inevitable and we're the higher-priority unit, tell the lower-priority unit to pause, and go to Case 3.
   
   
3. Else, if we're the higher-priority unit, calculate our get-to point and tell the lower-priority unit to slow down enough to avoid the collision.

Resolving collisions

• If we're the unit that's moving in order to resolve a Case 1 collision and we've reached our desired point, resolve the collision.
  
  
• If we're the Case 3.1 lower-priority unit and the higher- priority unit has passed its get-to point, start returning to the previous position and resolve the collision.
  
  
• If we're the Case 3.1 higher-priority unit, wait (slow down or stop) until the lower-priority unit has gotten out of the way, then continue.
  
  
• If we're the Case 3.3 higher-priority unit and the lower-priority unit can now get out of the way, go to Case 3.1.
  
  
• If we're the Case 4.3 lower-priority unit and the higher-priority unit has passed its get-to point, resume normal speed and resolve the collision.
  

One of the key components of coordinated unit movement is to prioritize and resolve disputes. Without a solid, well-defined priority system, you're likely to see units doing a merry-go-round dance as each demands that the other move out of its way; no one unit has the ability to say no to a demand. The priority system also has to take the collision severity into account. A simple heuristic is to take the highest-priority hard collision and resolve down through all of the other hard collisions before considering any soft collisions. If the hard collisions are far enough in the future, though, you might want to spend some time resolving more immediate soft collisions. Depending on the game, the resolution mechanism might also need to scale based on unit density. If a huge melee battle is creating several compound hard collisions between some swordsmen, you're better served spending your CPU time resolving all of those combat collisions than resolving a soft collision between two of your resource gatherers on a distant area of the map. An added bonus to tracking these areas of high collision density is that you can influence the pathfinding of other units away from those areas.