Unit to Unit Cooperation
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).
Case 1. If both units are not moving:
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:
Figure 7. Resolving a collision between a moving unit and a stopped unit.
Case 4. If we're moving and the other unit is moving:
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.