Starcraft AI blog

Until the 1980s, most scholars believed that in a flock of birds, or a school of fish, or a herd of antelopes, one animal was the leader and the group moved together because they followed the leader—even though nobody could figure out which animal it was.

Today we know that animal groups commonly self-organize by simple rules. Craig Reynolds’ boids flocking rules from 1986 are still the prototype today: Each boid looks at its local flockmates (and nothing else) and aims for separation from them to avoid crowding, alignment with the direction they’re heading, and cohesion, or keeping toward the center of mass so the flock holds together.

Flocking algorithms are reactive algorithms for local collision avoidance and group behavior, not very different in idea from potential fields. From what I read, it seems common in games to use A* for pathfinding plus something in the flocking family for steering along the way, where “steering” means detailed movement in reaction to the immediate surroundings.

OpprimoBot can be configured to use a boids algorithm as an alternative to potential fields, and the boids algorithm is turned on for SSCAIT, supposedly because it performs better. So I looked at the source in NavigationAgent::computeBoidsMove() which is called to move one unit a step toward a chosen destination.

Lotsa stuff in there! It’s a long sweep of straight-line code and easy to read. It computes dx and dy relative to the current position of a unit and decides whether to move or attack, and then records the order it computed: From the current position (x, y) to (x+dx, y+dy). I see these steps, in order:

1. add a delta in the direction of the specified goal
2. add a delta toward the center of mass of the squad (cohesion)
3. add a delta tending to keep squad units moving in the same direction (alignment)
4. for ground units only, add a delta away from the closest squadmates if they’re too close (separation)
5. make a more complicated check about whether to retreat from enemies; if so, add a delta for that
6. add a delta away from terrain obstacles that are too close
7. if retreating, record a move to the new location, otherwise an attack move

I think the retreat implements kiting for ranged units and escape for units that have no attack. I couldn’t find any case where one delta depended on earlier ones, so I think they’re independent and the order doesn’t matter.

That seems simpler overall than potential fields, and OpprimoBot’s author Johan Hagelbäck seems to believe it works better. It certainly doesn’t have the local optimum problem.

OpprimoBot’s boids movement algorithm produces only the simplest attack-move micro. If you want something fancier, it seems to me that a flocking algorithm could be adapted to create movement toward weakly-defended targets, flight from strong enemies, and focus-fire to kill chosen enemies efficiently. Or you could say that’s no longer pathfinding and code it separately.

Next: The terrain analysis libraries.