Artificial Life: Colonies in Motion
In this Post ...
I'll revisit Craig Reynolds' famous algorithm for simulating flocking behavior.
Introduction
Recently I was reminded of an algorithm created to simulate the movement of large groups of organisms -- think; schools of fish, flocks of birds, cauldrons of bats -- that sort of thing. Craig Reynolds created the algorithm way back in 1986. Soon thereafter, it was applied to create special effects in movies and video games as-well-as as a tool for scientific inquiry into complex systems. What I found most compelling about it back then -- and still do today -- is how the algorithm provides a very simple explanation for emergent behavior in terms of three simple rules: alignment, separation and cohesion.
Since Reynolds' boids have proved so profoundly useful in so many domains I've incorporated it as a part of my SVG Creators framework and wanted to devote some time to examining it here. So in this post I'll briefly describe the algorithm, provide a javascript implementation using SVGCC framework components, and present a demo of how at can be applied to create artworks with hundreds and even potentially thousands of SVG elements.
Boids Rules
The boids algorithm is eloquent in its simplicity. Named for its sprite-like elements -- "bird-oids" -- it revolves around three elemental forces that drive "steering behavior": alignment, separation and cohesion as illustrated below.
Alignment basically compels boids to seek to align and move in the same general direction. The Separation force drives boids apart and keeps them from colliding. Coherence (cohesion) keeps boids together by driving them toward a "center of mass".
Artificial Life: Colonies in Motion
The Boid Sprite
Boids is such a classic building block for games and simulations that I'd be remiss if I didn't fold it into the Scalable Vector Graphics Creators Framework™. To make things easy for creative coders, I've included the full source below so you can drop it straight into your own projects and start experimenting right away.
import {
Vector2D
} from "./vector.js";
import {
Movable
} from "./movable.js";
export class BoidSprite extends Movable {
/**
* Boid constructor ...
* @param {*} id
* @param {*} svg
* @param {*} p
* @param {*} v
* @param {*} a
* @param {*} r
* @param {*} s
* @param {GameController} gc reference to the GameController
* (injected by the factory)
*/
constructor (id, svg, p, v, a, r, s, gc ) {
super( p, v, a );
this.rotation = r;
this.scale = s;
this.id = id;
this.svg = svg;
this.gc = gc;
}
updateTransform ( ) {
const { x, y } = this.pos;
const rotation = this.rotation;
const scale = this.scale;
this.svg.setAttribute(
'transform',
`translate( ${x} ${y} ) rotate( ${rotation} ) scale( ${scale.xAxis} ${scale.yAxis} )`
);
}
update ( deltaTime ) {
// apply boid rules which all update your velocity ...
this.applyBoidRules();
super.move( deltaTime );
this.turnabout();
this.limitSpeed();
this.rotation = Math.atan2(this.vel.y, this.vel.x) * 180 / Math.PI;
this.updateTransform();
}
limitSpeed() {
const limits = this.params.speedLimits;
const mySpeed = this.vel.length();
if( mySpeed > limits.MAX ) {
this.vel.x = this.vel.x / mySpeed * limits.MAX;
this.vel.y = this.vel.y / mySpeed * limits.MAX;
} else if ( mySpeed < limits.MIN ) {
if (mySpeed > 0) {
this.vel.x = (this.vel.x / mySpeed) * limits.MIN;
this.vel.y = (this.vel.y / mySpeed) * limits.MIN;
} else {
// kick it off in a small random direction if speed == 0
this.vel.x = limits.MIN * (Math.random() * 2 - 1);
this.vel.y = limits.MIN * (Math.random() * 2 - 1);
}
}
}
turnabout() {
if( ! this.worldModel ) {
return;
}
const x = this.worldModel.bounds.x + 50;
const y = this.worldModel.bounds.y + 50;
const width = this.worldModel.bounds.width -50;
const height = this.worldModel.bounds.height -50;
const turnfactor = this.params.TURNING_FACTOR;
// horizontal turns
if( this.pos.x > width ) {
this.vel.x -= turnfactor;
} else if ( this.pos.x < x ) {
this.vel.x += turnfactor;
}
// vertical turns
if( this.pos.y > height ) {
this.vel.y -= turnfactor;
} else if ( this.pos.y < y ) {
this.vel.y += turnfactor;
}
}
setCollection( group ) {
this.group = group;
}
setWorldModel( wm ) {
this.worldModel = wm;
}
setTunableParameters ( params ) {
this.params = params;
}
setLeader( bool ) {
this.leader = bool;
}
isLeader() {
return this.leader;
}
/**
* This is the heart of the boid. Da rools is as follows:
*
* 1. separate: get away from me! protected range
* 2. align: steer in the same direction as others in "visible range"
* 3. cohere: steer toward the CENTER of boids in range
* (i.e., in your sphere of influence...)
*/
applyBoidRules() {
const params = this.params;
const grp = this.group;
const myPosition = this.pos;
// Accumulators for all three rules
let sepX = 0, sepY = 0;
let vXsum = 0, vYsum = 0, alignCount = 0;
let pXsum = 0, pYsum = 0, cohereCount = 0;
// Leader bias accumulators
let leaderVelX = 0, leaderVelY = 0, leaderCount = 0;
for (let i = 0; i < grp.length; i++) {
const other = grp[i];
if (other === this) continue;
const d = myPosition.getDistance(other.pos);
// Separation
if (d < params.SEPARATION_RADIUS) {
sepX += myPosition.x - other.pos.x;
sepY += myPosition.y - other.pos.y;
}
// Alignment
if (d < params.ALIGNMENT_RADIUS) {
vXsum += other.vel.x;
vYsum += other.vel.y;
alignCount++;
}
// Cohesion
if (d < params.COHERENCE_RADIUS) {
pXsum += other.pos.x;
pYsum += other.pos.y;
cohereCount++;
}
// Leader bias
if (other.isLeader) {
leaderVelX += other.vel.x;
leaderVelY += other.vel.y;
leaderCount++;
}
}
// Apply separation
this.vel.x += sepX * params.AVOIDANCE;
this.vel.y += sepY * params.AVOIDANCE;
// Apply alignment
if (alignCount > 0) {
const vXavg = vXsum / alignCount;
const vYavg = vYsum / alignCount;
this.vel.x += (vXavg - this.vel.x) * params.ALIGNMENT;
this.vel.y += (vYavg - this.vel.y) * params.ALIGNMENT;
}
// Apply cohesion
if (cohereCount > 0) {
const cx = pXsum / cohereCount;
const cy = pYsum / cohereCount;
this.vel.x += (cx - this.pos.x) * params.COHESION;
this.vel.y += (cy - this.pos.y) * params.COHESION;
}
// Apply leader bias at the end
if (leaderCount > 0) {
const lXavg = leaderVelX / leaderCount;
const lYavg = leaderVelY / leaderCount;
this.vel.x += (lXavg - this.vel.x) * params.LEADER_BIAS;
this.vel.y += (lYavg - this.vel.y) * params.LEADER_BIAS;
}
}
export const tunableParamDefaults = {
AVOIDANCE: 0.05,
ALIGNMENT: 0.05,
COHESION: 0.0005,
SEPARATION_RADIUS: 8,
ALIGNMENT_RADIUS: 40,
COHERENCE_RADIUS: 40,
TURNING_FACTOR: 0.2,
LEADER_BIAS : 0.01,
speedLimits : {
MAX: 40,
MIN: 0,
}
};
Walk-through and Analysis
Key Dependencies
The boid rules are built entirely around vectors. I've already covered the Vector2D implementation in another post so if you'd like a refresher on how vectors work in the framework you can check that out here. You'll find the full Vector2D implementation in an appendix.
I've also provided a base-class for defining sprites in the framework, Movable, which I've also discussed elsewhere. Movable is designed around vector composition and can be readily extended to create new sprite types. For convenience, I've in-lined the Movable implementation below.
/**
* Base class for 'movable' entities like sprites and
* particles...
*/
export class Movable {
constructor( initPosition, initVelocity, acceleration ) {
this.pos = initPosition;
this.vel = initVelocity;
this.acceleration = acceleration;
// ---- bind methods ------------------------
this.move = this.move.bind( this );
this.isInBounds = this.isInBounds.bind(this);
}
/**
* Every Moveable needs to be able to move.
* expect deltaTime in seconds (i.e. msec / 1000)
*
* Update velocity by adding accelaration. To make it
* time-based you need to factor in the interval between
* current and last frame (i.e., multiply acceleration by
* deltaTime). Expect delta Time in seconds...
*
* Update position by adding velocity. You also need to
* account for delta time...
*
* See: https://dr-nick-nagel.github.io/blog/kinematics.html
*/
move ( deltaTime ) {
this.vel.x += this.acceleration.x * deltaTime;
this.vel.y += this.acceleration.y * deltaTime;
this.pos.x += this.vel.x * deltaTime;
this.pos.y += this.vel.y * deltaTime;
}
...
}
Boid Rules
With the vector and movable foundations in place, the heart of the BoidSprite lies in the encapsulation of the boid rules. In the SvgCC framework movables tie into an animation loop by implementing an update method. update performs operations to update the sprite's internal state and then calls move with the time delta parameter (in seconds) to handle kinematics. Finally, updateTransform syncs the visual state by updating the sprite's SVG on the DOM. This architecture fits the boid model perfectly; in SvgCC sprites are expected to "know how to move themselves".
The rules for boid movement are encapsulated in applyBoidRules. Boids have to have awareness of other members of their group. The framework achieves this by injecting the collection of boids comprising the group through the setter method setCollection. This enables each boid to iterate over members within specified radii that affect its movements and apply the rules.
Separation: Update your velocity by accumulating the difference vectors between yours and the others' positions and applying an avoidance factor.
Here, $\alpha$ is the avoidance factor -- one of a set of tunable parameter described below. $p_i$ is the boid's current position relative to its neighbors' $p_j$ falling within its "circle of influence" defined by radius $r_i$.
Alignment: keep yourself aligned by updating your velocity with the average velocity of the others in your circle of influence.
Here, $\Beta$ is the alignment factor (a parameterized weight applied to vary the aligment force).
Coherence: Update your velocity to gravitate toward the average position of neighbors in your circle of influence (which essentially defines a center of mass for the group).
And that's largely it! I've added in a few more details to allow boid "leaders" to exert an influence and constrain group movement to remain withing an SVG viewport "world area", but the three rules as formulated above pretty much provide a complete implementation for organic collective movement behavior.
As a final note, for ease of definition and maintenance I've abstracted a set of tunable parameters into a javascript object literal and provided a set of defaults as an exportable in the BoidSprite module.
Discussion
Since its introduction, Reynolds' boids algorithm has had a huge impact on science, art, and industry. I'm especially intrigued by its implications for the study of artificial life. And while its applications to games and entertainment may seem obvious, boids have proven far more influential across many fields. With its profoundly simple explanation of how local rules give rise to emergent collective motion, the algorithm has been used to study:
-
Phase transitions in complex systems,
-
Formation control in robotics and engineering,
-
Information visualization and optimization
... and much, much more.
With such wide and profound influence, the boids algorithm is, in my view, a “must-study” for anyone interested in the arts, sciences, or entertainment industry.
Working boids into the SVG Creators Collective framework has been more than just a technical exercise. It's solid proof that even simple, browser-native tools can bring the beauty of emergent systems to life. Reynolds' original idea still feels fresh today. And seeing it run in real time with nothing to power it but javascript and SVG shows just how far the web has come as a playground for both science and art. Finally -- the best part is, the sprites that I created along the way to this post are now re-usable building blocks you can use to bring your own amazing SVG creations to life!
