By Drew Cutchins - 16 August 2018
Have you ever watched a school of fish, a flock of birds, or even a crowd of people and watched how they move?
Moving together, yet without a leader, they are exhibiting a behavior known as flocking.
Programmer Craig Reynolds defined this behavior according to three rules:
We can create flocking behavior in code by using these same rules.
First we need a way to represent a single member of the flock. These are called boids. Boids will have a position, velocity and acceleration. During every frame of the simulation, they will use their acceleration and velocity values to update their position.
// Defining the model for a boid
class Boid{
// They will be initialized with a starting x and y position
constructor(xPos, yPos){
// The mass of the boid will dictate how responsive it is to flocking forces
this.mass = 1;
this.position = {x: xPos, y: yPos};
this.velocity = {x: 0, y: 0};
this.acceleration = {x: 0, y: 0};
}
// Heading is represented by a decimal value indicating the radians
get heading{
return Math.atan2(this.velocity.x, this.velocity.y);
}
// This function will be called to guide the boid while flocking
applyForce(force){
// Acceleration is force devided by mass
this.acceleration.x += force.x / this.mass;
this.acceleration.y += force.y / this.mass;
}
update(){
// We will later add code to change the velocity of the boid given its suroundings
updatePosition();
}
updatePosition(){
// Acceleration is change in velocity
this.velocity.x += this.acceleration.x;
this.velocity.y += this.acceleration.y;
// Veloity is change in position
this.position.x += this.velocity.x;
this.position.y += this.velocity.y;
// Acceleration is reset each frame
this.acceleration = {x: 0, y: 0};
}
}
Next, lets create a model for an entire flock.
// Defining the model for a flock
class Flock{
constructor(flockSize){
this.boids = [];
this.size = flockSize;
this.populateFlock();
}
populateFlock(){
for(var n = 0; n < this.size; n++){
// The boids will be created at the center of the graph.
this.boids.push(new Boid(0,0));
// The angle of the boids are evenly distributed in a circle
var angle = (n / this.size) * 2 * Math.PI;
// The velocity is set based on the calculated angle
this.boids[n].velocity = {x: Math.cos(angle), y: Math.sin(angle)};
}
}
updateFlock(){
for(var i = 0; i < this.size; i++){
this.boids[i].update();
}
}
}
And finally, we can create a function to render our flock. I have created a few functions such as “drawTriangle” that are irrelevent to the flocking algorithm and therefore not included in this article.
function renderFlock(flock){
for(var i = 0; i < flock.size; i++){
renderBoid(flock.boids[i]);
}
}
function renderBoid(boid){
// The drawTriangle function takes a position and a rotation as parameters
drawTriangle(boid.position.x, boid.position.y, boid.heading);
}
Alright, now lets test our flock update
var flock = new Flock(10);
function loop(){
// The loop will run every 10 milliseconds
setTimeout(loop, 10);
flock.update();
renderFlock(flock);
}
Wait! All of the boids are gone as soon as they leave the canvas, I’ll add a bit of code to make the sides of the screen wrap to one another. If a boid leaves on the left side of the canvas it will reappear on the right side.
Now that we have our flock management and rendering code set up, we can start applying our three rules of flocking.
However, in order to do this, our boids need to have information of other boids nearby. We need to change the boid update function to take an array of neighboring boids as a parameter. We also need to allow our updateFlock function to provide each boid update with its neighbors.
class Flock{
constructor(flockSize){
// ...
// The proximity boids have to be, to be considered neighbors.
this.neighborDistance = 10;
// The neighborDistanceSquared is compared to the square distance between neighbors.
// This avoids the performance costly square root operation.
this.neighborDistanceSquared = Math.pow(this.neighborDistance, 2);
}
// ...
updateFlock(){
for(var i = 0; i < this.size; i++){
var neighbors = [];
// Iterates through all other boids to find neighbors.
for(var j = 0; j < this.size; j++){
if(j != i){
var squareDistance = Math.pow(this.boids[j].position.x - this.boids[i].position.x, 2)
+ Math.pow(this.boids[j].position.y - this.boids[i].position.y, 2);
if(squareDistance < this.neighborDistanceSquared){
neighbors.push(this.boids[j]);
}
}
}
this.boids[i].update(neighbors);
}
}
}
Finally we can begin with applying separation to our boids. This force is calculated as a sum of vectors pointing away from nearby boids.
class Boid{
constructor(xPos, yPos){
// ...
// We define an ideal distance for our boids to keep from one another
this.separationDistance = 5;
// The strength with which the boid will avoid others
this.separationStrength = 1;
}
// ...
update(neighbors){
var separationForce = calculateSeparation(neighbors);
this.applyForce(separationForce);
updatePosition()
}
calculateSeparation(neighbors){
// This vector is the force we want to apply to our boid to keep it away from neighbors
var separationForce = {x: 0, y: 0}
for(var i = 0; i < neighbors.length; i++){
// Distance = sqrt((x1 - x2)^2 + (y1 - y2)^2)
var distance = distance(this.position.x - neighbors[i].position.x,
this.position.y - neighbors[i].position.y);
if(distance < this.separationDistance){
// The offset between the two boids
var offset = {
x: this.position.x - neighbors[i].position.x,
y: this.position.y - neighbors[i].position.y,
}
// Note the use of a normalize function,
// It scales the vector so that its magnitude is 1.
// This value is used to indicate direction rather than distance.
// This function is not included in javascript so I had to implement it myself.
var normalizedOffset = normalize(offset)
// The normalized offset is divided by the distance between the boids.
// A further boid requires less force to avoid
var force = {x:normalizedOffset.x /= distance, y:normalizedOffset.y /= distance};
// The calculated force is added to the total separation force
separationForce.x += force.x;
separationForce.y += force.y
}
}
return separationForce;
}
// ...
}
Separation Strength
Separation Distance
As you watch how the boids avoid one another, try playing with the avoidance strength and seperation distance values. Note that the seperation distance cannot be greater than the neighbor distance value.
Next, we will implement cohesion, forcing boids toward the average position of all of its neighbors. Cohesion is essentially the opposite of separation. If boids are too close they will repel one another, if they are too far, they will atract one another. These two forces will work together to maintain a specified distance between boids.
class Boid{
// ...
calculateCohesion(neighbors){
// This is the average position of all neighbors
var averagePosition = {x: 0, y: 0};
// Tracks the number of boids within the cohesion distance
var count = 0;
for(var i = 0; i < neighbors.length; i++){
var distance = distance(this.position.x - neighbors[i].position.x,
this.position.y - neighbors[i].position.y);
if(distance < this.cohesionDistance){
averagePosition.x += neighbors[i].position.x;
averagePosition.y += neighbors[i].position.y;
count++;
}
}
averagePosition /= count;
var displacement = {x: averagePosition.x - this.position.x,
y: averagePosition.y - this.position.y};
// This vector is the force we want to apply to our boid to keep it away from neighbors
var cohesionForce = {x: displacement.x * this.cohesionStrength,
y: displacement.y * this.cohesionStrength};
return cohesionForce
}
}
Cohesion Strength
Cohesion Distance
Note how the boids stick near one another. However these boids now resemble clumps rather than a flock. By combining separation and cohesion, we can create much more realistic behavior.
Separation Strength
Separation Distance
Cohesion Strength
Cohesion Distance
Last but not least, we need to implement “heading”. This final rule forces boids in a similar direction that their neighbors are travelling.
class Boid{
// ...
calculateAlignment(neighbors){
// This is the average velocity of all neighbors
var averageVelocity = {x: 0, y: 0};
// Tracks the number of boids within the cohesion distance
var count = 0;
for(var i = 0; i < neighbors.length; i++){
var distance = distance(this.position.x - neighbors[i].position.x,
this.position.y - neighbors[i].position.y);
if(distance < this.alignmentDistance){
averageVelocity.x += neighbors[i].velocity.x;
averageVelocity.y += neighbors[i].velocity.y;
count++;
}
}
// Average = sum/count
averageVelocity /= count;
var alignmentForce = {x: averageVelocity.x * this.alignmentStrength,
y: averageVelocity.y * this.alignmentStrength};
return alignmentForce
}
}
Separation Strength
Separation Distance
Cohesion Strength
Cohesion Distance
Alignment Strength
Alignment Distance
When combined, these three simple rules have created complex emergent behavior. I hope you’ve enjoyed reading about flocking and that you’ve learned something new! Please provide any feedback or suggestions in the comments.