In 1986, Craig Reynolds created a model to describe the motion of flocks. These flocks recreated the motion of animals that move in groups, such as fish or birds, and he called these simulated animals boids. With three simple rules, this model creates very naturalistic motion. What follows is a summary of my implementation of this model, using C# and Unity.
Three Simple Rules
Our base representation of our boids without any behavior will be them just moving in some initial direction with some initial speed. The boid would move along this velocity vector infinitely, never changing direction. With Reynolds’ three simple rules, we can add behavior to this motion, and life to the boids. The three rules are as follows
-
Separation
Steering away from neighboring boids that are too close.
-
Alignment
Steering towards the average of the velocities of all neighboring boids.
-
Cohesion
Steering towards the center of mass of all neighboring boids.
With these rules, we can start with the implementation.
Unity Setup and the First Problem to Solve
I started by jumping in Unity, getting my scene setup, and creating a BoidController class that sets its initial velocity to some random unit vector. I’m going to assume this is a baseline thing for anyone reading this, if you need help getting this far, there are plenty of Unity tutorials on YouTube. Otherwise, if you’ve set up a character controller before, this will follow in the same vein.
Also created a FlockController class, which is responsible for creating the boids when you hit play. I used a List of GameObjects to store references to these boids, which we’ll need so we can find a list of our neighbors.
1
2
3
4
5
6
7
void Start() {
for (int i = 0; i < settings.numBoids; i++) {
BoidController boid = Instantiate(settings.boidPrefab).GetComponent<BoidController>();
boid.Initialize(settings);
boids.Add(boid);
}
}
You’ll note I’m using some settings objects to get all of these parameters. This is a ScriptableObject I created called BoidsSettings, which is designed to represent all of our parameters for the boids and flock.
Our first problem here is that the boids just move along their initial velocity vector, so the first problem was to contain the boids in some volume, or create some bounds for our simulation. For this, we need a minimum range for the boids, which will let us know how close the boids are allowed to get to the edge, and a max range, which will create a sphere centered on the origin, which represents our bounds for the simulation. Here’s my commented code for this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Vector3 EdgeAvoidance() {
//if the boid is inside the spawn radius, but within it's avoidance distance
if (transform.position.magnitude > settings.maxRadius - settings.avoidanceRadius) {
//get the distance from the boid to the edge of the spawn radius
float distance = settings.maxRadius - transform.position.magnitude;
//set the strength to the inverse square of the distance
float strength = 1 / (distance * distance);
//invert the direction
Vector3 avoidanceDir = -transform.position.normalized;
//return multiplied with our strength
return avoidanceDir * settings.avoidanceWeight * strength;
}
return Vector3.zero;
}
How do boids “see” their neighbors?
This is our first truly complex problem to solve, but it’s also probably the toughest step in this implementation. Don’t worry, it only gets easier afterward! The first thing to set up here is a new setting for the sight radius of our boids, I called it perceptionRadius . Each boid should be aware of all the other boids within this radius, these are their neighbors.
Brute Force
1200 boids, each checking every other boid
We need to find every boid within that perception radius, and the brute force method would be to loop through all the boids, checking each distance and storing the boids with a distance less than perceptionRadius. The problem with this is every boid is checking every other boid on every frame. This is a computing nightmare, so we must find a better solution. There are better options than what I did, such as using an octree or spatial hash. With the implementations, the boids don’t have to search the entire simulation, as they generally map locations to groups, which is far more efficient
If I had known that Unity’s Physics library makes use of these methods under the hood, then I would have used them instead. I mistakenly assumed that it would require a RigidBody on each boid, which would not scale well. If I continue to work on this project, I would go back and use those instead. The implementation would change, but the efficiency boost would be notable, allowing for 5000+ boids, instead of my solution, which starts to chug at around 2500 boids.
Brute Force Light
Because I was over-assuming the inefficiencies of the built-in physics library, I tried to find some middle ground. The first thing I did was limit how many neighbors each boid could have with a parameter, maxNeighbors. Instead of trying to find every boid within the perception radius, we only try to find boids until we hit that max, and then stop looking.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public BoidController[] BruteForceLight(BoidController boid) {
//create a new array of neighbors
BoidController[] nearbyBoids = new BoidController[settings.maxNeighbors];
int count = 0;
//get a random int between 0 and the number of boids as our offset
int offset = Random.Range(0, boids.Count);
//loop through all the boids
for (int i = 0; i < boids.Count; i++) {
//if inside the radius, add to the list and increment count
if (Vector3.Distance(boid.transform.position, other.transform.position) < settings.maxRadius) {
nearbyBoids[count] = other;
count++;
}
//if num neightbors == maxNieghbors, stop searching
if (count >= settings.maxNeighbors) break;
}
//return list of boids
return nearbyBoids;
}
Now that we can find our neighbors, we have everything we need to start on the three rules, I started with Separation.
Separation
All we need to do here is loop through our neighbors, check if the distance to that neighbor is less than our avoidanceRadius (the same value we used for EdgeAvoidance). If the neighbor is inside that radius, we use the inverse square law to determine our strength and move in the opposite direction of that neighbor. This result is added up and averaged for all our neighbors.
All we need to do here is loop through our neighbors, check if the distance to that neighbor is less than our avoidanceRadius (the same value we used for EdgeAvoidance). If the neighbor is inside that radius, we use the inverse square law to determine our strength and move in the opposite direction of that neighbor. This result is added up and averaged for all our neighbors.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Vector3 Separation() {
//our result vector, initialized to 0,0,0
Vector3 separationDir = Vector3.zero;
//for each neighbor
foreach (BoidController neighbor in neighbors) {
if (neighbor != null) {
//vector between the neighbor and this boid
Vector3 toNeighbor = transform.position - neighbor.transform.position;
//magnitude is the distance between the two
float distance = toNeighbor.magnitude;
if (distance < settings.avoidanceRadius) {
//use inverse square law to determine strength
separationDir += toNeighbor.normalized * 1 / distance * distance;
}
}
}
//still gets scaled linearally by the weight
return separationDir.normalized * settings.separationWeight;
}
This looks quite similar to our EdgeAvoidance function, and that’s because it is! The only difference is we’re checking against our distance to boids, instead of the distance to our bounds.
An Issue Crops Up
After implementing this, I noticed this was creating some clumping among the boids. The boids weren’t really separating. I realized this was an issue with how we find neighbors. Since the list of all boids is static, each boid is finding the same neighbors over and over. To solve this, I added a (controllable) random offset to our BruteForceLight function.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public BoidController[] BruteForceLight(BoidController boid) {
...
int offset = Random.Range(0, boids.Count);
//loop through all the boids
for (int i = 0; i < boids.Count; i++) {
//randomly offset search based on randomNeighbor setting
int index = settings.randomNeighbors ? (i + offset) % boids.Count : i;
if (settings.randomNeighbors) {
index = (i + offset) % boids.Count;
}
//get the boid out of the list
BoidController other = boids[index];
...
As you can see in this video, this resolves the clumping issue.
Alignment + Cohesion
Similar to cohesion, we have to start by looping through the list of neighbors. We add up all of the neighbor’s velocity vectors and then take the average. This average is our Alignment vector.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Vector3 Alignment() {
Vector3 alignmentDir = Vector3.zero;
//keeping track of how many neighbors regardless of max neighbors
int neighborCount = 0;
// add all velocties of valid neighbors
foreach (BoidController neighbor in neighbors) {
if (neighbor != null) {
alignmentDir += neighbor.velocity;
neighborCount++;
}
}
//take average of all neighbors velocity
alignmentDir /= neighborCount;
//scale by weight
return alignmentDir.normalized * settings.alignmentWeight;
}
As we can see, we have all the parameters set up from Separation. I added in alignmentWeight so we can tweak the strength of this force in the editor.
Cohesion followed right after. This time we get the center of mass of our neighbors by adding all of their positions (not velocity) and averaging the result.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Vector3 Cohesion() {
Vector3 centerOfMass = Vector3.zero;
int neighborCount = 0;
foreach (BoidController neighbor in neighbors) {
if (neighbor != null) {
centerOfMass += neighbor.transform.position;
neighborCount++;
}
}
if (neighborCount > 0) {
centerOfMass /= neighborCount;
return (centerOfMass - transform.position).normalized * settings.cohesionWeight;
}
return Vector3.zero;
}
This also gets a cohesionWeight , controllable from the editor. After playing with each of the parameters, I was able to dial in this simulation of 2000 boids:
Conclusion
For the future I’d love to make this something that is easily sharable, so anyone can go in and experience what control over a flock feels like. As I mentioned, I would also go back to improve the efficiency of finding neighbors. If given enough time, I would change over to using a Compute Shader wherever possible. Running this on the GPU would allow this simulation to reach a massive scale, with hundreds of thousands of boids flocking in real time.
There are also additional rules we can add to extend the Flocks behavior, including Predators, Leaders, and smaller flocks within the whole. You can learn more about them in the later sources below.
It’s really interesting to think about how such simple rules create an organic motion. I’m really happy with how this came out. I like to think of it as a parameter driven toy. I created all these parameters that I can change during runtime and watch as they take effect in the simulation. It’s really fun to see how each parameter affects the simulation, turning some off to see what happens. The nice thing about this is that it’s art directable, a school of fish would behave quite differently than a flock of birds, but we have the ability to tweak everything to match that expected behavior.
Sources
Reynolds’ Website on Boids
https://www.red3d.com/cwr/boids/
The Coding Train - Coding Challenge #124: Flocking Simulation
https://www.youtube.com/watch?v=mhjuuHl6qHM
Sebastian Lague - Coding Adventure: Boids
https://www.youtube.com/watch?v=bqtqltqcQhw
Neat AI - Neat AI Does Predator Boids
https://www.youtube.com/watch?v=rkQB4zEJggE
Harmen de Weerd- Boids: Flocking made simple