Flocking Vectors in Unity

Posted on November 6, 2014 by Evan Knowles — 1 Comment ↓

Contents

1 Introduction (aka, those flocking Vectors)
2 The Flying V: Structures We’ll Need
3 Who are we?
4 Alignment – where are we all going?
5 Cohesion and separation – can’t we all just get along?
6 And… it is done.

Introduction (aka, those flocking Vectors)

Those flocking Vectors. How I grow to hate them. Hate’s a strong word – how they irk me from time to time. But occasionally they come together to form something quite beautiful – especially (as well as literally) in the case of flocking.

Flocking is a technique originally invented by Craig Reynolds in 1986 and published in an unusually entertaining paper called “Flocks, Herds, and Schools: A Distributed Behavioral Model” in 1987. Well worth the read if you have the time. If not…

Craig Reynolds was attempting to simulate the behaviour of birds (or “boids”) flocking together, as opposed to attempting to design a path for each bird (which could obviously take some time).

He managed to produce a realistic set of motions through three basic ideas which he termed alignment, cohesion and separation. Basically, for any one boid, the ideas of trying to fly in the same direction as its neighbours, trying to keep as close as possible to the centre of of its neighbours, and trying not to overcrowd them.

There are indeed many different articles on flocking on the internet — unsurprisingly, given that it was published in 1987. I ran across one that was well written in a fairly accessible manner, but which unfortunately had some extra steps that complicated the process. It does have a nice implementation of flocking that you can play around with, so do have a look at it if you’re new to the topic.

That article, as well as this one, looked at the problem in two dimensions only. Primarily because this makes it easier to work with, although in my case it’s mostly because I am working on flocking pedestrians walking. Unity, with its convenient handling of 3D vectors, makes it especially easy to generalise to more dimensions.

We’ll tackle each concept one at a time, and provide relatively efficient Unity C# code as we go along. First off – before we can flock with a group, we need some idea of who our group is first. Let’s have a look at the structures we’ll lay out in Unity in order to represent our flock.

The Flying V: Structures We’ll Need

We’re going to have a whole bunch of game objects (the more the merrier) with scripts on them – that much is generally assured. In our case we’re going to have a PersonWalkScript which will be on each object that we wish to flock together.

This script will keep track of the current velocity for each flocking object, as well as who they consider to be part of their flock. Having every object flock with every other object is fairly dull as a lot of the dynamics are introduced when groups interact with one another.

First off, we’re guaranteed that we’ll be referring to the position of objects fairly often. To avoid relatively costly underlying GetComponent calls, we’ll cache a reference to the script’s GameObject ‘s transform at the start of the game.

    public new Transform transform {
        get;
        private set;
    }

    void Start() {
        transform = gameObject.transform;
    }

public new Transform transform {

get;

private set;

}

void Start() {

transform = gameObject.transform;

}

This is easy enough – a Transform that can be retrieved publicly, which is cached at the beginning of the game to avoid having to re-retrieve it later. What else do we need in this script?

We need to keep track of each object’s current velocity – we do not adjust any object’s position directly, but instead we keep track of what their velocity is, make changes to it, and apply that to the object each update. This allows for smooth motion instead of the jerky response that would result if we flung the game objects from side to side directly.

    private Vector3 velocity = new Vector3();

    void Update () {
        gameObject.transform.Translate (velocity * Time.deltaTime, Space.World);
    }

    public void AddVelocity(Vector3 force) {
        velocity += force;
        velocity.Normalize ();
    }

private Vector3 velocity = new Vector3();

void Update () {

gameObject.transform.Translate (velocity * Time.deltaTime, Space.World);

}

public void AddVelocity(Vector3 force) {

velocity += force;

velocity.Normalize ();

}

Each update we translate the game object’s current transform by our current velocity, adjusting accordingly by the amount of time that has passed since the last update.

The only way that outside code should affect our velocity is through the AddVelocity method, providing a force that should be applied to the current velocity. We normalise the velocity here, in order to keep all the boids moving at the same pace, but you could have different boids with different maximum speeds fairly easily.

The other code that is required for our walking scripts is a method to retrieve the velocity (for use in calculations involving the group) and an indication of what our boid is using as its neighbour radius — that is, the radius in which it will look for other boids to flock with.

The complete code for our walking script is:

using UnityEngine;
using System.Collections;

public class PersonWalkScript : MonoBehaviour {

    private Vector3 velocity = new Vector3();
    private float neighbourRadius = 10.0f;

    public new Transform transform {
        get;
        private set;
    }

    void Start() {
        transform = gameObject.transform;
    }

	void Update () {
        gameObject.transform.Translate (velocity * Time.deltaTime, Space.World);
	}

    public void AddVelocity(Vector3 force) {
        velocity += force;
        velocity.Normalize ();
    }

    public Vector3 GetVelocity() {
        return velocity;
    }

    public float GetNeighbourRadius() {
        return neighbourRadius;
    }
}

using UnityEngine;

using System.Collections;

public class PersonWalkScript : MonoBehaviour {

private Vector3 velocity = new Vector3();

private float neighbourRadius = 10.0f;

public new Transform transform {

get;

private set;

}

void Start() {

transform = gameObject.transform;

}

void Update () {

gameObject.transform.Translate (velocity * Time.deltaTime, Space.World);

}

public void AddVelocity(Vector3 force) {

velocity += force;

velocity.Normalize ();

}

public Vector3 GetVelocity() {

return velocity;

}

public float GetNeighbourRadius() {

return neighbourRadius;

}

This is all we need to keep track of for each individual boid — next up, let’s have a look at the group as a whole.

Who are we?

We’re going to look at the more trivial case where the number of objects in the group does not increase or decrease. Therefore, we can cache a list of all the involved objects at the beginning of the game. This could be extended to producing or destroying new objects relatively easily by maintaining this list as the objects are created and destroyed.

Our main script is the FlockingScript . At the beginning of the game we’ll find each instance of the PersonWalkScript defined earlier and store it for use in the Update s.

public class FlockingScript : MonoBehaviour {
    List<PersonWalkScript> walkScripts;

    void Start() {
        PersonWalkScript[] walkScriptsArray = FindObjectsOfType (typeof(PersonWalkScript)) as PersonWalkScript[];
        walkScripts = new List<PersonWalkScript> ();
        walkScripts.AddRange (walkScriptsArray);
    }

public class FlockingScript : MonoBehaviour {

List<PersonWalkScript> walkScripts;

void Start() {

PersonWalkScript[] walkScriptsArray = FindObjectsOfType (typeof(PersonWalkScript)) as PersonWalkScript[];

walkScripts = new List<PersonWalkScript> ();

walkScripts.AddRange (walkScriptsArray);

}

We store the objects in a List for two reasons – one, to keep the data structures we use fairly consistent across the code, and two to allow us to maintain the list of objects fairly easily later on should we wish to.

The code itself is fairly straightforward – we get all of the components of type PersonWalkScript in the game and store them in our list.

Next we need to work out, given this list of scripts, which are close enough to affect each other while flocking. Although if one object affects a different object we know that the affect will be mutual (given that they’re identical distances away from each other), it is not guaranteed that all objects in one group will affect all objects in another group. This brings out behaviours such as parts of one group splitting off to follow another, or just splitting off by themselves.

To calculate which boids are in a group with a particular boid, we look for all objects within a certain radius of that boid. We’re going to use a squared radius, which translates to the same thing but avoids an unnecessary square root.

    List<PersonWalkScript> GetNeighbours(PersonWalkScript person, List<PersonWalkScript> people) {
        List<PersonWalkScript> result = new List<PersonWalkScript> ();

        foreach (PersonWalkScript other in people) {
            if ((other.transform.position - person.transform.position).sqrMagnitude < person.GetNeighbourRadius()) {
                result.Add(other);
            }
        }

        return result;
    }

List<PersonWalkScript> GetNeighbours(PersonWalkScript person, List<PersonWalkScript> people) {

List<PersonWalkScript> result = new List<PersonWalkScript> ();

foreach (PersonWalkScript other in people) {

if ((other.transform.position - person.transform.position).sqrMagnitude < person.GetNeighbourRadius()) {

result.Add(other);

}

return result;

}

As can be seen from the signature of the method, we’re take in a person and a group of people. We iterate through each person in the group of people and calculate how far this other person is from our person.

If the distance is an acceptable amount away, as decided by the person’s neighbourhood radius, we add them to our neighbourhood list. Finally, we return the list of neighbours for the person.

Alignment – where are we all going?

Keeping the group moving is very important. If we simply bunch together or spread out, without a general direction, the group will appear to behave independently. This could be exploited in order to have the group suddenly scatter or push closely together, but in the general case of flocking we need to know where the rest of the group is headed and then try to head in the same direction.

This is actually very easy to work out — given a bunch of vectors, in order to work out their average heading, we can add them together and then divide by the number of vectors. This, conveniently and by definition, gives us their average heading. Unity handles vector manipulation quite well, making this fairly easy.

   Vector3 alignment = new Vector3 ();

   foreach (PersonWalkScript person in people) {
       alignment += person.GetVelocity();
   }

   int count = people.Count;
   alignment /= count;

Vector3 alignment = new Vector3 ();

foreach (PersonWalkScript person in people) {

alignment += person.GetVelocity();

}

int count = people.Count;

alignment /= count;

If we add this to our boid’s velocity, they will behind to tend to go in the same direction. They won’t tend to keep together, however, so they won’t veer in to form the nice close groups that we’re after.

What we need are the ideas of cohesion and separation, which are really two sides of the same flock.

Cohesion and separation – can’t we all just get along?

In the nicely laid out example linked above (and as pointed out in the comments), cohesion and separation are shown to be quite different. In reality, they’re just negations of one another, however. Let’s prove that. Disclaimer – you don’t really need to read through all of this. You can just skip down passed the math if you’re willing to trust me.

The calculation given by the linked article for cohesion is basically

$p = \frac{\sum_{n \in neighbours}n}{count(neighbours)}$

for each boid, $\mbox{boid}_v += p - \mbox{boid}_p$

That’s pretty much what we did for alignment, just using position instead of velocity. The calculation for $p$ is independent of who we’re applying the vectors to, so if we have a group of neighbours we can use the same result for everyone.

The article’s calculation for separation is not so convenient however. For a boid, $b$ ,

$v = \sum_{n \in neighbours}(n - \mbox{boid}_p)$

$v = -v$

$v = \frac{v}{count(neighbours)}$

for each boid, $\mbox{boid}_v = \mbox{boid}_v + p - \mbox{boid}_p$

This is dependent on the boid and a bit messier. Let’s see what we can do about that. If we take the first line and expand the sum a little…

$v = \sum_{n \in neighbours}(n) - count(neighbours) \times\mbox{boid}_p$

Let’s go ahead and combine all of the lines to see what we get.

$v = \frac{count(neighbours) \times \mbox{boid}_p - \sum_{n \in neighbours(n)}}{count(neighbours)}$

We can simplify this a bit…

$v =\mbox{boid}_p - \frac{\sum_{n \in neighbours(n)}}{count(neighbours)}$

Hold on – that term on the right looks familiar. That’s just the definition of $p$ that we had above. That means

for each boid, $\mbox{boid}_v = \mbox{boid}_v + \mbox{boid}_p - p$

The two components, cohesion and separation, are actually just negations of each other. This means that we can calculate them at the same time, which is convenient. Their actual influences are determined by the weights we place on each one.

But what do they do? In order to keep closer to the center of the group, we need to know exactly where the center of the group is. Likewise, to avoid crowding out the other members in the group, we need to move away from the center of the group.

Both factors need to know the center of the group – the center of mass. This center is also easy to calculate, in a similar way to how we calculated the alignment vector.

Instead of summing all of the velocities and then averaging them out, we sum all of their positions and average them out. This is easy enough to visualize on a one dimensional scale – imagine we have two boids, one at position 2 and one at position -2.

Their average position is $\frac{2 + (-2)}{2} = 0$ which is indeed half way in-between the two positions.

This is the only other factor we need to calculate, and the complete code for calculations is as follows.

FlockingVectors GetFlockingVectors (List<PersonWalkScript> people, float alignmentWeight, float cohesionWeight, float separationWeight)
    {
        Vector3 centerMass = new Vector3 ();
        Vector3 alignment = new Vector3 ();

        foreach (PersonWalkScript person in people) {
            centerMass += person.transform.position;

            alignment += person.GetVelocity();
        }

        int count = people.Count;
        centerMass /= count;
        alignment /= count;

        return new FlockingVectors(alignment, centerMass, alignmentWeight, cohesionWeight, separationWeight);
    }

FlockingVectors GetFlockingVectors (List<PersonWalkScript> people, float alignmentWeight, float cohesionWeight, float separationWeight)

{

Vector3 centerMass = new Vector3 ();

Vector3 alignment = new Vector3 ();

foreach (PersonWalkScript person in people) {

centerMass += person.transform.position;

alignment += person.GetVelocity();

}

int count = people.Count;

centerMass /= count;

alignment /= count;

return new FlockingVectors(alignment, centerMass, alignmentWeight, cohesionWeight, separationWeight);

}

Here, FlockingVectors is a new class I’ve defined to help us keep our logic separated. It would be most useful where groups have split out neatly and every neighbour is a neighbour of every other neighbour, but for now it helps to just keep things simple. The complete code for FlockingVectors is:

using System;
using UnityEngine;

public class FlockingVectors
{
    Vector3 alignment;
    Vector3 centerMass;
    float alignmentWeight;
    float cohesionWeight;
    float separationWeight;

    public FlockingVectors(Vector3 alignment, Vector3 centerMass, float alignmentWeight, float cohesionWeight, float separationWeight) {
        this.alignment = alignment.normalized;
        this.centerMass = centerMass;
        this.alignmentWeight = alignmentWeight;
        this.cohesionWeight = cohesionWeight;
        this.separationWeight = separationWeight;
    }

    public Vector3 GetDirection(Vector3 position) {
        Vector3 cohesion = (centerMass - position).normalized;
        Vector3 separation = (position - centerMass).normalized;

        Vector3 result = alignmentWeight * alignment + cohesionWeight * cohesion + separationWeight * separation;

        return new Vector3 (result.x, 0, result.z).normalized;
    }
}

using System;

using UnityEngine;

public class FlockingVectors

{

Vector3 alignment;

Vector3 centerMass;

float alignmentWeight;

float cohesionWeight;

float separationWeight;

public FlockingVectors(Vector3 alignment, Vector3 centerMass, float alignmentWeight, float cohesionWeight, float separationWeight) {

this.alignment = alignment.normalized;

this.centerMass = centerMass;

this.alignmentWeight = alignmentWeight;

this.cohesionWeight = cohesionWeight;

this.separationWeight = separationWeight;

}

public Vector3 GetDirection(Vector3 position) {

Vector3 cohesion = (centerMass - position).normalized;

Vector3 separation = (position - centerMass).normalized;

Vector3 result = alignmentWeight * alignment + cohesionWeight * cohesion + separationWeight * separation;

return new Vector3 (result.x, 0, result.z).normalized;

}

In the GetDirection method, you can see how the factors are combined. Cohesion and separation are actually just negations of one another.

All three vectors are then combined, with a weighting on each one depending on how we want them to behave, and the result is normalized and returned. We’re going for two dimensions in this case, so we zero out the y-component, but you could include this for the more standard three dimensional boid flocking appearance.

And… it is done.

To string all the pieces together, here’s the complete FlockingScript. Let me know if you have any questions or if I’ve left anything out.

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

public class FlockingScript : MonoBehaviour {
    List<PersonWalkScript> walkScripts;

    void Start() {
        PersonWalkScript[] walkScriptsArray = FindObjectsOfType (typeof(PersonWalkScript)) as PersonWalkScript[];
        walkScripts = new List<PersonWalkScript> ();
        walkScripts.AddRange (walkScriptsArray);
    }

	void Update () {
        foreach (PersonWalkScript person in walkScripts) {
            if (person.transform == null) {
                continue;
            }
            List<PersonWalkScript> neighbours = GetNeighbours(walkScripts, person);

            FlockingVectors vectors = GetFlockingVectors (neighbours, 5.0f, 1.5f, 1.1f);
            Vector3 force = vectors.GetDirection(person.transform.position);

            person.AddVelocity(force);
        }
	}

    List<PersonWalkScript> GetNeighbours(List<PersonWalkScript> people, PersonWalkScript person) {
        List<PersonWalkScript> result = new List<PersonWalkScript> ();

        foreach (PersonWalkScript other in people) {
            if ((other.transform.position - person.transform.position).sqrMagnitude < person.GetNeighbourRadius()) {
                result.Add(other);
            }
        }

        return result;
    }

    FlockingVectors GetFlockingVectors (List<PersonWalkScript> people, float alignmentWeight, float cohesionWeight, float separationWeight)
    {
        Vector3 centerMass = new Vector3 ();
        Vector3 alignment = new Vector3 ();

        foreach (PersonWalkScript person in people) {
            centerMass += person.transform.position;

            alignment += person.GetVelocity();
        }

        int count = people.Count;
        centerMass /= count;
        alignment /= count;

        return new FlockingVectors(alignment, centerMass, alignmentWeight, cohesionWeight, separationWeight);
    }
}

using UnityEngine;

using System.Collections;

using System.Collections.Generic;

public class FlockingScript : MonoBehaviour {

List<PersonWalkScript> walkScripts;

void Start() {

PersonWalkScript[] walkScriptsArray = FindObjectsOfType (typeof(PersonWalkScript)) as PersonWalkScript[];

walkScripts = new List<PersonWalkScript> ();

walkScripts.AddRange (walkScriptsArray);

}

void Update () {

foreach (PersonWalkScript person in walkScripts) {

if (person.transform == null) {

continue;

}

List<PersonWalkScript> neighbours = GetNeighbours(walkScripts, person);

FlockingVectors vectors = GetFlockingVectors (neighbours, 5.0f, 1.5f, 1.1f);

Vector3 force = vectors.GetDirection(person.transform.position);

person.AddVelocity(force);

}

List<PersonWalkScript> GetNeighbours(List<PersonWalkScript> people, PersonWalkScript person) {

List<PersonWalkScript> result = new List<PersonWalkScript> ();

foreach (PersonWalkScript other in people) {

if ((other.transform.position - person.transform.position).sqrMagnitude < person.GetNeighbourRadius()) {

result.Add(other);

}

return result;

}

FlockingVectors GetFlockingVectors (List<PersonWalkScript> people, float alignmentWeight, float cohesionWeight, float separationWeight)

{

Vector3 centerMass = new Vector3 ();

Vector3 alignment = new Vector3 ();

foreach (PersonWalkScript person in people) {

centerMass += person.transform.position;

alignment += person.GetVelocity();

}

int count = people.Count;

centerMass /= count;

alignment /= count;

return new FlockingVectors(alignment, centerMass, alignmentWeight, cohesionWeight, separationWeight);

}

Tagged with: C#, flocking, unity
Posted in Unity

Flocking Vectors in Unity

Introduction (aka, those flocking Vectors)

The Flying V: Structures We’ll Need

Who are we?

Alignment – where are we all going?

Cohesion and separation – can’t we all just get along?

And… it is done.

Leave a Reply Cancel reply