Boid-based Grouping

What are boids

Boids were originally proposed by Craig Reynolds as a way to model flocking behaviour in birds.

Originally Reynolds proposed three behaviours:

• Coherence - Each boids tendency to steer towards the centre of the group.
• Separation - Each boids attempts to avoid other boids based on the distance they are from one another.
• Alignment - Where boids try to move in the same direction as other boids around them.

Many interactive examples exist:

• Ben Eater's boids example.
• Processing.org's boids example.
• Harmen de Weerd's boids example.

More can be found on boids here.

Similar methods were also considered for use in Evacu-agent, such as that of the social force model which seeks to model realistic human movement through applying a series of forces to a Pedestrian.

However boids were used due to their modular component-based architecture.

It was thought that by applying combinations of different boids components non-uniform and realistic movement could be mimicked more easily and dynamically at run time depending on the context.

Boid placement in Pedestrians

Boids are controlled via BoidManager which is placed on the EvacuAgentPedestrianBase.cs GameObject as seen below:

Boid components are placed in the same level as BoidManager:

Boid components

Boid components are responsible for calculating a Vector3 that will be summed with other boid components to form a force vector that will be applied to the pedestrian.

These forces form the basis each pedestrians ability to display grouping behaviour with its group members and avoid contact with non-group members.

Each boid component extends BoidComponentBase which can be seen below:

protected abstract bool IsDebuggingOn { get; }
public abstract Vector3 CalculateComponentVelocity(BoidBehaviourStrategyBase followerBoidBehaviour);

public bool DoesVectorContainNaN(Vector3 vector)
{
    return IsValueNaN(vector[0]) && IsValueNaN(vector[1]) && IsValueNaN(vector[2]);
}

private bool IsValueNaN(float value)
{
    return float.IsNaN(value);
}

The most important method here is CalculateComponentVelocity which must be implemented by all children of BoidComponentBase and is where each components velocity vector logic is calculated.

The property IsDebuggingOn and the method DoesVectorContainNaN() are debugging tools:

1. IsDebuggingOn can be toggled in all children to display useful Gizmo-based debugging lines that will show the direction of the velocity vector calculated.
2. DoesVectorContainNaN() calls can be placed in each child to determine the source of any NaN errors.

Boid behaviour strategy base

BoidBehaviourStrategyBase is an abstract class extending BehaviourStrategy and is responsible for modelling all shared logic for boid behaviour types.

An example is that all boid beahviour types must maintain a current List<BoidBehaviourStrategyBase> of Neighbours, members of their own group in their FieldOfView, and NonGroupNeighbours which are non-group members in their FieldOfView.

An important method here is CalculateNewVelocity() which is where the summed velocity component is calculated and applied to the pedestrian.

protected void CalculateNewVelocity()
{
    UpdateNeighbours();
    CalculateNeighbourPoint();
    Vector3 newVelocity = BoidManager.CalculateNewVelocity();
    newVelocity = LimitVelocity(NavMeshAgent.velocity += newVelocity.normalized);
    NavMeshAgent.velocity = newVelocity;

    newVelocityCache = newVelocity;
    navMeshVelocityCahce = NavMeshAgent.velocity;
}

In CalculateNewVelocity(), BoidManager.CalculateNewVelocity() is called to calculate the sum of the boid component velocities. The magnitude of this velocity value is then limited to prevent pedestrians from moving too rapidly. The limited velocity value is then applied to the NavMeshAgent.velocity.

BoidBehaviourStrategyBase also declares a number of abstract properties so that different weights for different components can be set in child classes.

public abstract float CohesionWeight { get; }
public abstract float SeparationWeight { get; }
public abstract float TargetSeekingWeight { get; }
public abstract float InterGroupSeparationWeight { get; }

Boid components based on Pedestrian type

Each boid component calculates a velocity that is then multiplied by a weighting between 0 and 1. This weighting helps to increase or decrease the effect each component has on the final summed velocity value. To model the boid weightings of different pedestrian types BoidBehaviourStrategyBase can be extended as seen below.

Note that FriendGroupBoidBehaviour extends BoidBehaviourStrategyBase which extends BehaviourStrategy meaning that boid behaviour types are iterated over in pedestrian behaviour preference orders as explained in Behaviour structure.

Whilst more logic could be placed in these pedestrian type boid behaviour classes, the intent is that boid behaviours should be controlled by adding boid components and by altering weights to maintain a modular nature to grouping.

public class FriendGroupBoidBehaviour : BoidBehaviourStrategyBase
{
    public override float CohesionWeight => EvacuAgentSceneParamaters.FRIEND_GROUP_BOID_COHESION_WEIGHT;
    public override float SeparationWeight => EvacuAgentSceneParamaters.FRIEND_GROUP_BOID_SEPARATION_WEIGHT;
    public override float TargetSeekingWeight => EvacuAgentSceneParamaters.FRIEND_GROUP_BOID_TARGET_SEEKING_WEIGHT;
    public override float InterGroupSeparationWeight => EvacuAgentSceneParamaters.FRIEND_GROUP_BOID_INTER_GROUP_SEPARATION_WEIGHT;

    protected override bool IsDebuggingOn => false;

    void Start()
    {
        base.Start();
        shouldUpdateBoid = true;
        isDebuggingOn = false;
    }

    public override void PerformBehaviour()
    {
        CalculateNewVelocity();
    }

    public override bool ShouldTriggerBehaviour()
    {
        return shouldUpdateBoid;
    }
}

Example boid component

The below example is of BoidCohesionComponent which is used to produce a velocity component that pushes pedestrians towards the centre of their visible group members.

If no group members are visible this component returns Vector3.Zero which means this component will have no effect on the overall summed velocity.

This component then finds a directional vector from subtracting its own position from the centre of all visible group members.

Finally the velocity component is multiplied by a CohesionWeight to alter the effect this velocity component will have on the overall summed velocity.

public class BoidCohesionComponent : BoidComponentBase
{
    protected override bool IsDebuggingOn => false;

    public override Vector3 CalculateComponentVelocity(BoidBehaviourStrategyBase followerBoidBehaviour)
    {
        Vector3 velocity = Vector3.zero;

        if (followerBoidBehaviour.Neighbours.Count == 0)
            return velocity;

        velocity += followerBoidBehaviour.NeighbourCenter;
        velocity -= followerBoidBehaviour.transform.position;

        return velocity * followerBoidBehaviour.CohesionWeight;
    }
}

Adding a new boid component

1. Create a new script prefixed with Boid and suffixed with Component, for example BoidExampleComponent.
2. The new component should extend BoidComponentBase.
3. Implement the logic necessary for CalculateComponentVelocity() in the new component.
4. Add the new component to any pedestrian prefab at the same level as EvacuAgentPedestrianBase and BoidManager as seen above.
5. IsDebuggingOn should be set to false.

Limitations

As boid components are collected into List<BoidComponentBase> boidComponents in Start() of BoidManager to be iterated over, boid components cannot, currently, be dynamically added or removed at run time.