What kind of steering behaviour or logic can I use to get mobiles to surround another?

Question

I'm using path finding in my game to lead a mob to another player (to pursue them). This works to get them overtop of the player, but I want them to stop slightly before their destination (so picking the penultimate node works fine).

However, when multiple mobs are pursuing the mobile they sometimes "stack on top of each other". What's the best way to avoid this? I don't want to treat the mobs as opaque and blocked (because they're not, you can walk through them) but I want the mobs to have some sense of structure.

Example:

Imagine that each snake guided itself to me and should surround "Setsuna". Notice how both snakes have chosen to prong me? This is not a strict requirement; even being slightly offset is okay. But they should "surround" Setsuna.

Answer 1

Give your agents a weak "electrostatic charge" to make them repel each other, along the lines of Coulomb's law.

Assuming for simplicity that mobs should push each other away with equivalent strength, it should be enough to apply a force between every pair of mobs with a magnitude some_constant / distance^2, where some_constant is a configurable repulsion strength and distance is the distance separating them.

The repulsion strengths then fall off with the square of the distance.

Nature of Code has a great example (with a live demo) here. It looks like this:

Matching every element against every other is a quadratic-time (O(n^2)) operation. If you have really many agents, you may wish to optimise the force calculations with a Barnes-Hut approximation, which takes it down to log-linear (O(n log n)) but requires a quadtree.

Answer 2

My approach is similar to @Anko's, but based on the work by Millington and Funge from Artificial Intelligence for Games.

This is what a Separation behavior would look like, but you need to take into consideration that this velocity should be computed with the agent's speed in its Update function.

public Vector3 GetSeparationVel (float threshold, float decayCoefficient)
{
    threshold = threshold * threshold;
    Vector3 separationVelocity = Vector3.Zero;
    for (int i = 0; i < enemies.Length; i++) {
        if (enemies[i] == this) {
            continue;
        }
        Vector3 direction = this.position - enemies[i].position;
        float distance = direction.LengthSquared();
        float strenght = 0.0f;
        if (distance < (threshold)) {
            strenght = Math.Min(decayCoefficient / distance, this.maxAccel);
            direction.Normalize();
            separationVelocity += strenght * direction;
        }
    }
}