Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

enter image description here

share|improve this question
1  
Is the stacking only a concern at the destination or also while in transit? I'm guessing the latter. –  SpartanDonut Aug 18 at 19:00
    
It's the latter, @SpartanDonut –  Vaughan Hilts Aug 18 at 19:16
    
@KromStern I added a picture, hope it helps. –  Vaughan Hilts Aug 18 at 19:20

2 Answers 2

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:

combined follow and separate behaviours

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.

share|improve this answer
    
Great link, Anko. Much appreciated! I'll defintely have to give this entire site a read over. –  Vaughan Hilts Aug 18 at 19:59
    
Starcraft (1, at least) does something similar with its flying units. But it only does it when they stop moving, i.e. when they're on the move they clump on top of each other (completely ignore each other as obstacles), but when they stop they all start spreading out from what looks like to be the local center of some regular area (square/circle, probably) that encompasses them. This doesn't look as pretty as the example in the answer, but it probably uses less CPU resources, and it's possibly easier to code too... –  Shivan Dragon Aug 19 at 13:22
    
@ShivanDragon SC2 presents the same behaviour, they all converge to the destination in a crowd, then space out for kind-of-realistic and aestethically pleasing looks (so their parts don't clip around). –  Kroltan Aug 19 at 14:36
1  
Some kind of repelling force can be a good idea, but the details are tricky. I experimented with these in a space themed RTS and recommend not following physics too closely and rather modeling it so it behaves nicely. Some observations: 1) Since this is no physics simulation I'd only apply the force over short distances. 2) This can't prevent finite bodies from overlapping 3) The hard potential easily causes numerical errors, such as particles being refracted at high velocities. 4) Once you have a significant number of particles and pressure in the middle rises, things tend to get ugly. –  CodesInChaos Aug 19 at 16:55

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;
        }
    }
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.