Table of Contents
Reference Resources:
Algorithm Overview
In 1987, computer scientist Craig Reynolds published a paper on simulating flocking behavior in birds. In it, he introduced an algorithm called Boids, which quickly found applications in movies and games. For example, it was used to animate bat and penguin swarms in Batman Returns (1992), and bird-like creatures in Half-Life (1998).
The Boids algorithm is based on a decentralized idea: it defines the behavior of each individual, without directly modeling the group. The “flock” is simply the visual result of many individuals following simple rules. Each Boid follows three basic principles:
- Separation: Move away from nearby Boids to avoid crowding.
- Alignment: Steer toward the average heading of nearby Boids.
- Cohesion: Move toward the average position of nearby Boids.
Detailed Explanation of the Rules
Separation Rule
One key behavior in a flock is that each individual tends to move away from nearby neighbors—similar to how like poles of magnets repel each other. The closer they are, the stronger this repelling force becomes. This rule helps prevent collisions and overlapping between Boids.
Here’s how the separation rule can be implemented in code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
// Separation Rule
Vector2D separation(const std::vector<Boid>& boids)
{
Vector2D separation(0, 0);
for (const Boid& b : boids)
{
float distance = (b.position - position).length();
if (distance > 0 && distance < separation_distance)
{
Vector2D diff = position - b.position;
separation = separation + diff * (1.0f / distance);
}
}
return separation;
}
|
Alignment Rule
In flocking simulations, alignment helps control how each individual adjusts its direction of movement. Intuitively, we often judge whether a group is truly a “flock” or just a random crowd based on whether its members are moving in a similar direction.
Alignment rule can be implemented like this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
// Alignment Rule
Vector2D alignment(const std::vector<Boid>& boids)
{
Vector2D avg_velocity(0, 0);
int total_neighbors = 0;
for (const Boid& b : boids)
{
float distance = (b.position - position).length();
if (distance > 0 && distance < neighbor_distance)
{
avg_velocity = avg_velocity + b.velocity;
total_neighbors++;
}
}
if (total_neighbors > 0)
{
avg_velocity = avg_velocity * (1.0f / total_neighbors);
return avg_velocity - velocity;
}
return Vector2D(0, 0);
}
|
Cohesion Rule
与分离规则相反，聚集规则是一种凝聚力，像磁铁的异性相吸。它保证了集群中的个体不会因为分离规则而过度分散，导致无法产生“邻居个体”。
The cohesion rule works in the opposite way to separation—it acts like an attractive force, similar to how opposite poles of magnets pull toward each other. It helps prevent individuals from spreading out too far due to separation, ensuring that each Boid still has nearby neighbors to interact with.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
// Cohesion Rule
Vector2D cohesion(const std::vector<Boid>& boids)
{
Vector2D center_of_mass(0, 0);
int total_neighbors = 0;
for (const Boid& b : boids)
{
float distance = (b.position - position).length();
if (distance > 0 && distance < neighbor_distance)
{
center_of_mass = center_of_mass + b.position;
total_neighbors++;
}
}
if (total_neighbors > 0)
{
center_of_mass = center_of_mass * (1.0f / total_neighbors);
return (center_of_mass - position);
}
return Vector2D(0, 0);
}
|
- These three rules constantly interact and balance each other. With just basic math and vector operations, simple individuals can exhibit surprisingly complex collective intelligence.
- In different scenarios, flocking behavior is essentially shaped by fine-tuning the parameters of these rules. For example, in fish schools, we often simulate uneven spacing caused by water resistance by reducing the strength of the alignment rule—this creates a realistic “tail lag” effect when turning. In mouse swarms or zombie hordes, increasing the weight of the cohesion rule helps the group flow smoothly around obstacles like a stream of liquid. In sci-fi-style scenes, we might want the flock to maintain a sharp, triangular formation—this can be achieved by adding shape constraints on top of the cohesion rule.
Full Implementation
Implementation Approach and Workflow
Creating the Boid Class
Each individual in the flock needs three key properties: position, velocity, and acceleration. All three are represented as 2D vectors, since this project implements the Boids algorithm in a 2D visual space.
Here’s how the Boid class can be defined:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
// boid.js
class Boid
{
constructor()
{
this.position = createVector(width / 2, height / 2); // Position of the boid
this.velocity = p5.Vector.random2D(); // Initial velocity of the boid
this.velocity.setMag(random(0.5, 1.5 )) // Assign each boid a slightly different speed
this.acceleration = createVector(); // Acceleration of the boid
}
update(){
this.position.add(this.velocity);
this.velocity.add(this.acceleration);
}
show(){
strokeWeight(16);
stroke(255);
point(this.position.x, this.position.y);
}
}
|
Suppose we have 100 boids in total. In sketch.js, we can use an array to store them like this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
// sketch.js
const flock = [];
function setup() {
createCanvas(640, 360);
for (let i = 0; i < 100; i++){
flock.push(new Boid());
}
}
function draw() {
background(51);
for (let boid of flock){
boid.show();
boid.update();
}
}
|
Now you can see the result looks like this:
Implementing the Alignment Rule
“Alignment is the simplest of the three rules, so we’ll start with it.
How it works: For each Boid, we check a circular area around it—using the Boid’s position as the center and a fixed radius. We then calculate the average velocity of all other Boids within that circle (its neighbors). This average velocity becomes the target direction the Boid should steer toward. By comparing its current velocity with the target, we can compute the steering force needed to adjust its movement.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
// boid.js
align(boids){
let perceptionRadius = 50; // A circular detection range with a radius of 50 pixels
let steering = createVector(); // The desired steering velocity for this boid
let total = 0; // Number of neighboring boids
for (let other of boids){
let d = dist(this.position.x, this.position.y, other.position.x, other.position.y);
if (other != this && d < perceptionRadius) {
steering.add(other.velocity); // Add the velocity of each neighbor
total++;
}
}
if (total > 0){
steering.div(total); // Calculate the average velocity of nearby boids
steering.setMag(this.maxSpeed); // Set the magnitude to the boid’s max speed
steering.sub(this.velocity); // Target velocity minus current velocity = steering force
steering.limit(this.maxForce); // Limit the steering force to avoid sharp turns
}
return steering;
}
flock(boids){
let alignment = this.align(boids);
this.acceleration = alignment; // Apply the alignment steering force as acceleration
// Force = mass × acceleration; assuming mass = 1, force equals acceleration
}
|
Now let’s add an effect where boids can “fly in and out” of the screen:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
// boid.js
edges(){
if (this.position.x > width){
this.position.x = 0;
} else if (this.position.x < 0){
this.position.x = width;
}
if (this.position.y > height){
this.position.y = 0;
} else if (this.position.y < 0){
this.position.y = height;
}
}
|
This gives us the following alignment effect:
Implementing the Cohesion Rule
This rule is similar to the alignment rule, but instead of calculating the average velocity of nearby Boids, we calculate their average position. This “target position” becomes the point the Boid should move toward to stay close to the group.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
cohesion(boids){
let perceptionRadius = 50;
let steering = createVector();
let total = 0;
for (let other of boids){
let d = dist(this.position.x, this.position.y, other.position.x, other.position.y);
if (other != this && d < perceptionRadius) {
steering.add(other.position); // Add the positions of nearby boids
total++;
}
}
if (total > 0){
steering.div(total); // Calculate the average position (target position)
steering.sub(this.position); // Target position - current position = desired movement direction
steering.setMag(this.maxSpeed); // Set the desired speed
steering.sub(this.velocity); // Desired velocity - current velocity = steering force
steering.limit(this.maxForce); // Limit the steering force to avoid sharp turns
}
return steering;
}
|
In the cohesion rule, maxForce isn’t the most critical factor. What really matters is the value of perceptionRadius, which determines how far a Boid can “see” its surroundings—and that directly affects its tendency to flock together.
Combining the two rules is quite straightforward. Just like in basic physics, the total force acting on an object is the sum of all individual forces.
1
2
3
4
5
6
7
8
9
10
|
// boid.js
flock(boids){
let alignment = this.align(boids);
let cohesion = this.cohesion(boids);
// Add the two forces together to get the combined steering force
this.acceleration.add(alignment);
this.acceleration.add(cohesion);
}
|
With both rules in effect, the flock now moves along trajectories like this:
Implementing the Separation Rule
Under the separation rule, we calculate the desired velocity of a Boid like this:
In essence, separation is the opposite of cohesion. So we can implement separation using a similar approach to cohesion, but instead of steering toward the average position of neighbors, we steer away from them.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
// boid.js
separation(boids){
let perceptionRadius = 50;
let steering = createVector();
let total = 0;
for (let other of boids){
let d = dist(this.position.x, this.position.y, other.position.x, other.position.y);
if (other != this && d < perceptionRadius) {
let diff = p5.Vector.sub(this.position, other.position); // Boid position minus neighbor position gives the desired velocity (steering away from the neighbor)
diff.div(d); // The farther a neighbor is, the less influence it has; the closer it is, the stronger the effect
steering.add(diff);
total++;
}
}
if (total > 0){
steering.div(total);
steering.setMag(this.maxSpeed);
steering.sub(this.velocity);
steering.limit(this.maxForce);
}
return steering;
}
|
This is the resulting effect of the separation rule:
With that, the basic version of the Boids algorithm is complete. By adjusting the weights of the three rules—alignment, cohesion, and separation—we can fine-tune the flocking behavior to suit different scenarios.
Full Source Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
// boid.js
class Boid
{
constructor()
{
this.position = createVector(random(width), random(height)); // Initial position of the boid
this.velocity = p5.Vector.random2D(); // Initial velocity
this.velocity.setMag(random(0.5, 2)) // Assign each boid a different speed
this.acceleration = createVector(); // Initial acceleration
this.maxForce = 0.2; // Maximum steering force
this.maxSpeed = 2; // Maximum speed
}
// Create a wrap-around effect when boids fly off the screen
edges(){
if (this.position.x > width){
this.position.x = 0;
} else if (this.position.x < 0){
this.position.x = width;
}
if (this.position.y > height){
this.position.y = 0;
} else if (this.position.y < 0){
this.position.y = height;
}
}
align(boids){
let perceptionRadius = 50; // Radius of the detection circle
let steering = createVector(); // Desired steering velocity
let total = 0; // Number of neighbors
for (let other of boids){
let d = dist(this.position.x, this.position.y, other.position.x, other.position.y);
if (other != this && d < perceptionRadius) {
steering.add(other.velocity); // Sum up neighbors' velocities
total++;
}
}
if (total > 0){
steering.div(total); // Average velocity of nearby boids
steering.setMag(this.maxSpeed); // Normalize to max speed
steering.sub(this.velocity); // Desired velocity - current velocity = steering force
steering.limit(this.maxForce); // Limit the steering force
}
return steering;
}
cohesion(boids){
let perceptionRadius = 100;
let steering = createVector();
let total = 0;
for (let other of boids){
let d = dist(this.position.x, this.position.y, other.position.x, other.position.y);
if (other != this && d < perceptionRadius) {
steering.add(other.position); // Sum up neighbors' positions
total++;
}
}
if (total > 0){
steering.div(total); // Average position (center of mass)
steering.sub(this.position); // Target position - current position = desired movement
steering.setMag(this.maxSpeed); // Normalize to max speed
steering.sub(this.velocity); // Desired velocity - current velocity = steering force
steering.limit(this.maxForce); // Limit the cohesion force
}
return steering;
}
separation(boids){
let perceptionRadius = 50;
let steering = createVector();
let total = 0;
for (let other of boids){
let d = dist(this.position.x, this.position.y, other.position.x, other.position.y);
if (other != this && d < perceptionRadius) {
let diff = p5.Vector.sub(this.position, other.position); // Vector pointing away from neighbor
diff.div(d); // Weight by inverse distance
steering.add(diff);
total++;
}
}
if (total > 0){
steering.div(total);
steering.setMag(this.maxSpeed);
steering.sub(this.velocity);
steering.limit(this.maxForce);
}
return steering;
}
flock(boids){
let alignment = this.align(boids);
let cohesion = this.cohesion(boids);
let separation = this.separation(boids);
// Apply rule weights
alignment.mult(alignSlider.value());
cohesion.mult(cohesionSlider.value());
separation.mult(separationSlider.value());
// Combine all steering forces
this.acceleration.add(alignment);
this.acceleration.add(cohesion);
this.acceleration.add(separation);
}
update(){
this.position.add(this.velocity);
this.velocity.add(this.acceleration);
this.velocity.limit(this.maxSpeed);
this.acceleration.set(0, 0); // Reset acceleration to avoid compounding force
}
show()
{
strokeWeight(8);
stroke(255);
point(this.position.x, this.position.y);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
// sketch.js
const flock = [];
let alignSlider, cohesionSlider, separationSlider
function setup() {
createCanvas(640, 360);
alignSlider = createSlider(0, 5, 1, 0.1);
cohesionSlider = createSlider(0, 5, 1, 0.1);
separationSlider = createSlider(0, 5, 1, 0.1);
for (let i = 0; i < 100; i++){
flock.push(new Boid());
}
}
function draw() {
background(51);
for (let boid of flock){
boid.edges();
boid.flock(flock);
boid.show();
boid.update();
}
}
|
