KSchuilenburg

Posted on Jan 23 • Edited on Jan 27

Simulating Realistic Group Behaviour using Couzin's Model in C++

#groupbehaviour #couzinsmodel #cpp #buas

Group Behaviour from Local Rules

Imagine moving in perfect sync with thousands of others - no leaders, no commands, you're just aware of your own peripheral and what happens in it. Think of birds twisting and turning as a group, fish scattering and regrouping in an instant, or millions of wildebeest migrating hundreds of kilometers as one group, all fascinating examples of decentralized group behaviour.

Decentralized in this context means; 'without a singular leader'. All these animals are not aware of what is happening outside of their perception, yet from an outsider's perspective it looks like they move as a single unit. Scientists have been researching the workings of these behaviours for years now, and computer simulation has helped significantly in that process. In this blogpost I aim to show you how complex group behaviour is formed from simple local rules and give you the handholds to implement a similar system with code.

A Model for group behaviour

There have been multiple models for simulating group behaviour for years now. The most famous arguably being Craig Reynolds' Boids Model, where complex group behaviour is achieved through three simple rules: Separation, Alignment, Cohesion. The Boids Model is not meant to simulate realistic group behaviour, instead it aims to approximate the behaviour. If we want to simulate realistic group behaviour, however, we need to look for alternatives.
Couzin's Model is such an alternative. Developed by Iain Couzin, Couzin's Model aims to simulate more realistic animal group behaviour, while still adhering to relatively simple rules.

Prerequisites:

Given I implemented this project for Buas Games where I am a 2nd year student following the programming course, I can't give you the full code since it was made in a custom game engine. I can, however, give you the concepts needed to implement your own version of Couzin's Model.
Since this blogpost will not give you the full code, some coding (C++) knowledge is recommended, but I will try my best to explain the code as we go. I will give you code showing a possible way to implement the given behaviour in a general sense.
Be warned if you are not comfortable with math, Couzin's Model involves a lot of vector mathematics and trigonometry.
The code uses mostly standard C++, but glm is used frequently for vector related logic.

The model:

Couzin's Model is based on the following three zones:

Zone of Repulsion (ZoR)
Zone of Orientation (ZoO)
Zone of Attraction (ZoA)

Credit: Couzin et al. (2002)

Zone of Repulsion
The Zone of Repulsion is the smallest sphere around the agent and takes the highest priority. Its goal is to check if other agents are within the ZoR, and if there are any, move away from them.
If there are no other agents in the ZoR, only then do the other zones get checked.

In the video above, the white cones in the scene are the agents, and the red circles around them are the zones of repulsion. As the zone of repulsion increases, you can see the agents start leaving more space in between them.

Formula for Zone of Repulsion:
d_r(t + tau) = -sum( r_ij(t) / |r_ij(t)| ) --> for all j != i

Where:

d_r(t + tau): The change in position (repulsion vector) for agent i at time t+τ.
sum: Sum of all neighbours j within the Zone of Repulsion.
r_ij(t): The vector pointing from agent i to neighbour j at time t.
|r_ij(t)|: The magnitude (distance) of the vector r_ij(t).

The formula effectively means:

For every neighbour j within the repulsion zone, calculate a unit vector pointing away from j.
Sum up all these unit vectors to get the total repulsion vector.
The negative sign ensures the agent moves away from its neighbours.

Code implementation

// neighbours = sum of all neighbours present in the scene
for (const auto& [neighbour, position] : neighbours)
{
    if (entity == neighbour) continue;

    // Assume currentBody & position are of type glm::vec3
    glm::vec3 vectorToNeighbour = currentBody.position - position;

    // Call ApplyRepulsion function that calculates the repulsion vector
    agentRepulsion += ApplyRepulsion(vectorToNeighbour, glm::length(vectorToNeighbour), agent.repulsionradius);
}

// ApplyRepulsion function
glm::vec3 ApplyRepulsion(const glm::vec3& vectorToTarget, float distance, float radius)
{
    if (distance > 0.0f && distance < radius)
    {
        float strength = 1.0f / (distance * distance);
        return strength * glm::normalize(vectorToTarget);
    }
    return glm::vec3(0.0f);
}

The above code is almost a direct translation of the formula mentioned before. Noteworthy is the line float strength = 1.0f / (distance * distance) which calculates the strength of the repulsion vector. 1.0f / (distance * distance) ensures that the strength increases as the distance decreases, meaning the agents will try to move away more from neighbours that are closer.

Zone of Orientation
Starting with the Zone of Orientation, which is the second sphere in the model. The ZoO checks if any agents are in the radius, and if they are, the agent will try to match the direction the other agent is moving in.

The above video shows repulsion combined with orientation. The green circle shows the zone of orientation, and agents that are in each other's zone of orientation will start aligning themselves in the same direction.

Formula for Zone of Orientation:
d_o(t + tau) = sum( v_j(t) / |v_j(t)| ) --> for all j in the set of neighbours within the orientation

Where:

d_o(t + tau): The orientation vector for agent i at time t + tau, resulting from aligning with neighbours.
sum: Sum of all neighbours j with the Zone of Orientation.
v_j(t): The velocity vector of neighbour j at time t.
|v_j(t)|: The magnitude of the direction of motion of neighbour j.

The formula effectively means:

For every neighbour j within the orientation zone, calculate a unit vector pointing in the direction of their motion.
Sum up all these normalized velocity vectors to get the total orientation vector.
The resulting vector represents the average direction of motion of the neighbours within the Zone of Orientation.

Code implementation

// neighbours = sum of all neighbours present in the scene
for (const auto& [neighbour, position] : neighbours)
{
    if (entity == neighbour) continue;

    // Get velocity of neighbour
    glm::vec3 neighbourVelocity = neighbour.velocity;

    // Ensure neighbour is not directly on top of current agent
    if (glm::length(neighbourVelocity) > 0.0f)
    {
        // Calculate unit vector pointing in the direction of motion
        orientation += glm::normalize(neighbourVelocity);
    }
}

Zone of Attraction
After the Zone of Orientation, the final rule is the Zone of Attraction. The ZoA checks if any agents are in the third sphere, and if they are, it will try to move towards these agents.

The above video shows the zone of attraction, indicated by the blue circle. When agents are within each other's zone of attraction, they start moving towards their neighbours, the zone of repulsion prevents them from overlapping however.

Formula for Zone of Attraction:
d_a(t + tau) = sum( r_ij(t) / |r_ij(t)| ) --> for all j != i

Where:

da(t+ tau): The attraction vector for agent i at time t + tau.
sum: The sum of all neighbours within the Zone of Attraction
r_ij(t): The vector pointing from agent i to neighbour j at time t.
|r_ij(t)|: The magnitude of vector r_ij(t).

The formula effectively means:

For every neighbour j within the attraction zone, calculate a unit vector pointing toward j.
Sum up all these unit vectors to get the total attraction vector.
The resulting vector represents the agent's tendency to move closer to its neighbours, encouraging cohesion within the group.

Code implementation

// neighbours = sum of all neighbours present in the scene
for (const auto& [neighbour, position] : neighbours)
{
    // Skip itself
    if (entity == neighbour)
    {
        continue;
    }

    // Calculate the vector from the agent to the neighbour
    auto vectorToNeighbour = position - currentBody.position();

    // Normalize and add to the attraction vector
    attraction += glm::normalize(vectorToNeighbour);
}

These three simple local rules form surprisingly complex group behaviour. Agents form a large group, while staying a certain distance away from each other, and if they encounter an obstacle or predator, the group can split up to avoid the obstacle, and form a group again afterwards.
Mainly this last part sets Couzin's Model apart from the Boids Model, since this behaviour is just not possible with Boids.

Conclusion:

Couzin's Model is a great starting point for simulating realistic group behaviour and through this blogpost, you have the handholds for implementing your own version of it. Where do you go after this? The great thing about Couzin's Model being relatively simple is that you can add your own behaviour on top of it. As long as you keep in mind to balance your resulting velocities, you can expand on this behaviour as you see fit.
Some ideas: Leader-Follower Dynamics, Dynamic Leaders, Predator Avoidance, and to a lesser extent agent communication.
A very big thing to consider regarding Couzin's Model is the following: since all three zones need to check ALL available neighbours to see if they are within one of the three zones, it can get very slow when more agents are introduced. To use this model in a real-time setting with thousands of agents, I highly recommend considering spatial partitioning optimizations like a Quadtree (or Octree in 3D).
All in all, Couzin's Model is a great alternative to the Boids Model, while still using relatively simple rules, and displaying more realistic group behaviour. Through this blogpost, I hope to have shown you the fundamentals for implementing a system like this, upon which you can implement your own, more advanced behaviours on top.

Discussion:

Given this research was for a university project, I had a clear deadline and had to make informed decisions about what to implement, and what to leave out. Unfortunately, this also means I did not implement everything I would have liked.
One of those things is a 3D implementation of Couzin's Model. I intended to start with a 2D implementation, and scale up to 3D in a later week. Because I had plans to implement more advanced behaviour on top of Couzin's Model, I ultimately decided to give those priority over a 3D implementation.
While outside the scope of this article, I thought I would give you a tiny look in what I implemented after Couzin's Model. Couzin's Model was the foundation for the rest of my project, like I discussed in the conclusion, one of the things to add on top of this model is Leader-Follower Dynamics and Agent Communication. I implemented both those things, but one thing I did not consider was how fundamentally different Couzin's Model and agent communication are.
Hence why I did not include it in this blogpost. I will however leave you with my implementation of agent communication; simulating wandering ants that leave a pheromone trail from a found resource to their nest.

And Couzin's Model combined with obstacle avoidance and more agents:

References

Couzin, I. D., Krause, J., James, R., Ruxton, G. D., & Franks, N. R. (2002). Collective Memory and Spatial Sorting in Animal Groups. Journal Of Theoretical Biology, 218(1), 1–11. https://doi.org/10.1006/jtbi.2002.3065