Most forums told me that pathfinding is a difficult problem, and A* wasn’t easy, but it was straightforward. No one mentioned the absolute morass of complexity in pathfollowing. Secret knowledge only available in the archives of Starcraft II GDC talks and research papers.

I want to recount what I built so that others can have an easier time with pathfollowing.

My A* pathfinding and simple raycast-skip pathfollowing worked okay, but it performed poorly in groups and narrow spaces.

Mages snag on walls, rarely reach their destination, overrun each other, and if any obstacles exist, they are caught forever on them.

For a game in a close-quarters castle, this is not acceptable for gameplay.

Corvids of a feather flock together

Games like Warcraft III and Age of Empires used A*, but put a substantial amount of logic into what paths were chosen and when. Units would often recalculate paths during movement to ensure they wouldn’t run into anything, they would select different points (based on an offset from a group leader and their size) to walk to. Collisions had special code for waiting, queueing, and other explicit behaviors.

Starcraft II took a different approach by looking to the skies.

Craig Reynolds, in 1987, published a paper about simulating the behavior of flocks of birds. Birds are independent actors, but in a flock, they manage to move together smoothly through obstacles, congestion, and other issues seen in RTS games. He called his simulation Boids (“Bird-oid”), which I love.

You can see modern recreations of the simulation, I like this one.

Boids are governed by four primary forces, typically called steering behaviors:

• Seek: The desire to move towards your destination.
• Separation: The desire to keep a certain minimal distance from neighbors.
• Cohesion: The desire to stay close enough to the flock you’re in.
• Alignment: The desire to be moving the same direction as your neighbors to avoid collisions.

There are other forces/behaviors, but they are typically for specific cases:

• Avoidance: Negotiating with another boid to avoid a head-on collision.
• Fleeing: Rather than seeking, try to escape a target in any way possible.
• Chasing: Following another actor, trying to mirror their movements and predict.

Before diving into using Boids for my mages pathfollowing, I considered a few alternatives. Modern RTS games and crowd simulations also use strategies like Continuum Crowds and Flow Fields. These strategies precalculate density and pathing for each area, like water rushing out, and are far more performant for large groups of units.

Given that I have relatively small unit counts (less than 20 total units onscreen in most cases), I suspected my performance and development time would be best spent building boids.

A complete movement overhaul

Currently, I have a MovementSystem and PathFindSystem. I chose to separate these concerns because a unit could move without pathfinding, and pathfinding can be expense (and best put on a separate thread), so I wanted the MovementSystem to be independent. It also made it easy to ensure units start moving immediately before path finding calculates, and then the path component is added afterward.

My MovementSystem only deals with velocity. I avoided acceleration because it seemed unnecessary for skymagi.

However, acceleration is necessary for Boids. Each of the forces (seek, separation, cohesion, alignment) are literal forces that are calculated on each update, and they drive acceleration. In a flock, units need to be able to slow down and speed up in various directions.

The end goal is to be able to write code roughly like this:

// calculate the individual forces affecting the unit currently
Vector2 seek = steeringSeek(...);
Vector2 separation = steeringSeparation(neighbors, ...);
Vector2 cohesion = steeringCohesion(neighbors, ...);
Vector2 alignment = steeringAlignment(neighbors, ...);

// Add up all the vectors
Vector2 total = seek.add(separation, cohesion, alignment);
// some code that ensures we have a limit to what force can be exerted
capMaxForce(total);

// apply force to velocity, ensure it doesn't pass unit's max speed
unit.vx += total.x * dt;
unit.vy += total.y * dt;
capMaxVelocity(unit.vx, unit.vy);

Pathfollowing is pretty expensive. A unit must figure out who its neighbors are, and despite having the same neighbors variable in the sample, I actually had two different sets for separation and cohesion/alignment. Separation has a much smaller radius since you mostly just don’t want other units running over you.

Also, you want to separate from anyone, but you might not want cohesion/alignment for enemy units.

It might make sense to have a hash/quadtree for position eventually to improve performance of finding neighbors. Box2D already has one, so I can just query overlap and rely on theirs.

Here’s some abbreviated/annotated pseudocode of what I actually did for each force:

// Seek: Go to your destination
Vector2 steeringSeek(Vector2 position, Vector2 velocity, float maxSpeed, float maxForce, Vector2 destination) {
  // seek *desires* to go maximum velocity toward the destination
  Vector2 desiredVelocity = (destination - position) / distance(position, destination) * maxSpeed;
  // so we want to apply a force that will change our current velocity to be maximum
  // first, find the difference between cur to desired, then scale by maximum we can accelerate
  Vector2 force = desiredVelocity.sub(velocity).scl(maxForce / maxSpeed);
  return force;
}

// Separation: Move away from others that are too close
// this force *only applies* if you have any neighbors that are too close. If neighbors is 0, don't calculate it.
Vector2 steeringSeparation(Vector2 position, float personalSpaceRadius, float maxForce, Array<Entity> neighbors) {
  Vector2 force = (0, 0);    // leaving out memory pooling for pseudocode :)

  // we want to figure out how much each neighbor should *push* us
  // If we are invading personal space, exert a force to move away.
  for (Entity neighbor : neighbors) {
    // the *closer* we are to them, the higher magnitude we should move away.
    Vector2 push = (position - neighbor.position) / personalSpaceRadius;
  }

  // Since we might have a thousand neighbors, we want the average force normalized
  force.scl(1 / neighbors.size * maxForce);
  return force;
}

// Cohesion: Be one with the flock, neighbors should be *friendly*
Vector2 steeringCohesion(Vector2 position, Array<Entity> neighbors) {
  // we want to be part of the flock, so we find the center of the flock
  // (the average position) and add a force pulling us to it.
  Vector2 center = (position + sumPositions(neighbors)) / (neighbors.size + 1);
  // rather than duplicating code, this is just *seek*, but our destination is the center
  return steeringSeek(..., center);
}

And last, but not least, alignment. It’s similar to cohesion, but with velocity instead of position.

// Alignment: Align direction to match the flock
Vector2 steeringAlignment(Vector2 position, Vector2 velocity, float maxSpeed, float maxForce, Array<Entity> neighbors) {
  // find the average direction the group is traveling.
  Vector2 avgVelocity = velocity;
  for (Entity neighbor : neighbors) {
    // I only included neighbors who were moving, so filter out any velocity at 0.
    // I added together all normalized velocitys, our goal is direction
    avgVelocity.add(neighbor.velocity.normalize());
  }
  // calculate actual avg
  avgVelocity.scl(1 / (neighbors.size+ 1));

  // now apply a force towards matching that vector. Find the difference between our velocity and avg.
  Vector2 force = avgVelocity.scl(maxSpeed).sub(velocity).scl(maxForce);
  return force;
}

Put it all together and…

Acceleration is way too slow. The broad strokes are correct, though.

We can see separation in action during a head-on collision.

I spent about an hour playing around with force magnitudes, acceleration speeds, and I added weights to all the various forces so that some applied harder than others. Separation is a strong force (1.5x) when it occurs. Cohesion and alignment are weaker forces (~0.2-0.3).

The behavior was much better:

So can we play nicely in the hallway now?

Spoiler alert: No.

Unlike the original system, they do all make it there… eventually.

However, they scrap over waypoints. This issue didn’t arise previously because they didn’t care about separation, so they’d just run over each other. Now they play a game of chicken to see who can claim the waypoint.

I have a few ideas to solve this issue:

• Adding a tolerance to reaching a waypoint.
• Reduce the amount of waypoints by adding a navmesh.
• Improve pushing behavior.

Before I tackle that, there are still mages who run into things that could be easily avoided.

Let’s add avoidance.

Actually, let’s not add avoidance.

-Kittems from the future, coding avoidance