Boids

One of the things I love about natural systems is how complex behavior can arise from sets of simple rules. In biology you see this fairly often, for example Lotka-Volterra equations predict predator-prey interactions and can lead to very complex outcomes despite being incredibly simple. A famous example from the history of computer science is John Conway’s Game of Life which produces incredibly complex (and sometimes unpredictable) interactions between cellular automata from only four rules. A lesser known example are Boids, or bird-oid objects, which demonstrate how three principles, separation, alignment, and cohesion can explain how flocking behavior can arise despite decentralized control. I implemented my own version of the Boids algorithm in Typescript using the HTML5 Canvas element. The complete code can be found in the Github repo.

You can play with the demo before jumping into the code:

Number

Size

Avoid Factor

Cohere Factor

Align Factor

Min Speed

Max Speed

Understanding Boids

The flocking behavior in boids is an emergent property of three different rules:

1. Try to stay near the central position of your neighbors (cohere)
2. Try to get away from very close neighbors (avoid)
3. Try to move in the same direction as you neighbors (align)

While each of these rules is applied independently of one another, they lead to complex flocking behavior when taken together.

Implementation

To implement boids, I created two classes:

• A Boid class which has fields for its current x, y position on the canvas as well as its horizontal velocity, vx, and its vertical velocity vy.
• A BoidContainer which has fields for a list of boids, references to the canvas element and rendering context, and a list of values for the neighbor distance, avoid factor, align factor, etc. which are shared by all the boids.

I also added methods to have the boids avoid the walls of the container, collision detection, clamp boid speed to between a minimum and maximum, and some convenience methods to modify parameters while the simulation is running.

One thing I did not do is have boids detect collisions with each other, or optimize how the BoidContainer detects neighbors. In theory, something like an AABB tree (Axis Aligned Bounding Box) would make finding neighbors more efficient (currently, it checks the distance of each boid against every other boid). That being said, despite the O(n²) complexity, it seems to run fine. I might attempt another version with collision detection and a real data structure to detect distance to other boids so that I can push the number of boids to something obscene. I also might see if I can change the color of the boids based on the average distance to neighbors.

type DefaultCanvasOpts = {
	avoidFactor: number
	alignFactor: number
	cohereFactor: number
	neighborDist: number
	closeDist: number
	buffer: number
	minSpeed: number
	maxSpeed: number
}

type CanvasOpts = DefaultCanvasOpts & {
	width: number
	height: number
}

type OptionalCanvasOpts = Partial<CanvasOpts>;

type CanvasOptKey = keyof DefaultCanvasOpts;

type BoidOpts = {
	vx?: number
	vy?: number
	size?: number
	color?: string
}

const defaultCanvasOpts: DefaultCanvasOpts = {
	avoidFactor: 0.05,
	cohereFactor: 0.03,
	alignFactor: 0.02,
	neighborDist: 100,
	closeDist: 33,
	minSpeed: 20,
	maxSpeed: 100, 
	buffer: 100
};

class Boid {
	x: number
	y: number
	vx: number
	vy: number
	private size: number
	private color: string
	private canvasOpts: CanvasOpts

	/**
	 * Boid represents a "bird like object" that engages in flocking behavior with other boids.
	 * 
	 * @param x The x position on the canvas
	 * @param y The y position on the canvas
	 * @param canvasOpts Values shared by all boids on the canvas, such as alignFactor, cohereFactor, maxSpeed, etc.
	 * @param opts Options for an individual boid, such as size, color, vx, vy, etc.
	 */
	constructor(x: number, y: number, canvasOpts: CanvasOpts, opts?: BoidOpts) {
		const {vx, vy, size, color} = opts || {};
		this.x = x;
		this.y = y;
		this.canvasOpts = canvasOpts;
		this.vx = vx || 0;
		this.vy = vy || 0;
		this.size = size || 5;
		this.color = color || "#000000";
	}


	/**
	 * Set options for this boid
	 */
	setOpts(opts: BoidOpts) {
		this.vx = opts.vx || this.vx;
		this.vy = opts.vy || this.vy;
		this.size = opts.size || this.size;
		this.color = opts.color || this.color; 
	}

	/**
	 * Draws the current point
	 * @param ctx The canvas rendering context.
	 */
	draw(ctx: CanvasRenderingContext2D): void {
		// Creates a circle
		ctx.arc(this.x, this.y, this.size, 0, 2*Math.PI);
		ctx.fillStyle = this.color;
		ctx.closePath();
		ctx.fill();
	}

	/** Updates poistion of current boid
	 * @param dt The difference, in milliseconds, since last update
	 * @param neighbors An array of neighbor boids
	 * 
	 */
	update(dt: number, neighbors: Boid[]): void {
		const {closeDist} = this.canvasOpts;
		// Separate from close neighbors
		this.separate(neighbors.filter(boid => dist(this, boid) < closeDist));
		// Align with neighbors
		this.align(neighbors);
		// Cohere with neighbors
		this.cohere(neighbors);
		// Avoid walls
		this.avoidWalls();
		// Clamp between min and max speed
		this.clampSpeed();
	
		const timeFactor = dt/1000;
		const [dx, dy] = [this.vx*timeFactor, this.vy*timeFactor];
		if (!this.isCollided(dx, dy)) {
			this.x += dx; 
			this.y += dy;
		}
	}

	// Returns true if boid has collided with canvas walls
	// will also set position to just have bounced off of wall if 
	// collided
	// NOTE: Probably should set value to where it would be if it 
	// had collided
	private isCollided(dx: number, dy: number): boolean {
		const {width, height} = this.canvasOpts;
		let collided = false;
		// Collided with left side
		if (this.x + dx - this.size < 0) {
			this.x = 0 + this.size;
			this.vx = Math.abs(this.vx);
			collided = true;
		}
		// Collided with right side
		if (this.x + dx + this.size > width) {
			this.x = width - this.size;
			this.vx = -1 * Math.abs(this.vx);
			collided = true
		}
		// Collided with top
		if (this.y + dy - this.size < 0) {
			this.y = 0 + this.size;
			this.vy = Math.abs(this.vy);
			collided = true;
		}
		// Collided with bottom
		if (this.y + dy + this.size > height) {
			this.y = height - this.size;
			this.vy = -1 * Math.abs(this.vy);
			collided = true;
		}

		return collided;
	}

	// Pushes boid away from walls 
	private avoidWalls() {
		const {width, height, buffer, avoidFactor} = this.canvasOpts;
		let [dx, dy] = [0, 0];
		if (this.x - 0 < buffer) {
			dx = this.x - 0;
		}	
		if (width - this.x < buffer) {
			dx = this.x - width;
		}
		if (this.y - 0 < buffer) {
			dy = this.y - 0;
		}
		if (height - this.y < buffer) {
			dy = this.y - height;
		}

		this.vx += dx*avoidFactor;
		this.vy += dy*avoidFactor;
	}

	// Pushes boid away from close neighbors
	private separate(closeNeighbors: Boid[]):void {
		// Initialize the sum of the x, y distance to neighbors to zero
		let [dx, dy] = [0, 0];
		const {avoidFactor} = this.canvasOpts;

		// Sum up the x and y distance for all close neighbors
		for (let i = 0; i < closeNeighbors.length; i++) {
			dx += this.x - closeNeighbors[i].x;
			dy += this.y - closeNeighbors[i].y;
		} 

		// Update current boid's x, y velocity component so that
		// it moves away from close boids
		this.vx += dx*avoidFactor;
		this.vy += dy*avoidFactor;
	}

	// Aligns boid's velocity vector with neighbors
	private align(neighbors: Boid[]):void {
		// Initialize the average x and y velocities and number of neighbors to 0
		let [vx_avg, vy_avg, n] = [0, 0, 0];

		const {alignFactor} = this.canvasOpts;

		// Calculate sum of velocities and number of neighbors
		for (let i = 0; i < neighbors.length; i++) {
			vx_avg += neighbors[i].vx;
			vy_avg += neighbors[i].vy;
			n++;
		}

		// Get the average x, y component of neighbor velocity 
		if (n > 0) {
			vx_avg = vx_avg/n;
			vy_avg = vy_avg/n;
		}

		// Set current boid's velocity so that the closer it is to the average
		// the less it changes
		this.vx += (vx_avg - this.vx)*alignFactor;
		this.vy += (vy_avg - this.vy)*alignFactor;
	}

	// Pushes boid towards center of neighbors
	private cohere(neighbors: Boid[]): void {
		// Initialize the average x,y position and number of neighbors to zero
		let [px_avg, py_avg, n] = [0, 0, 0];
	
		const {cohereFactor} = this.canvasOpts;

		// Sum up the x, y and number of neighbors
		for (let i = 0; i < neighbors.length; i++) {
			px_avg += neighbors[i].x;
			py_avg += neighbors[i].y;
			n++;
		}
		if (n > 0) {
			// Get the average x, y position
			px_avg = px_avg/n;
			py_avg = py_avg/n;
		}

		// Set the x, y components of the velocity so that 
		// the closer to the center of neighbors, the less it changes
		this.vx += (px_avg - this.x)*cohereFactor;
		this.vy += (py_avg - this.y)*cohereFactor;
	}

	// Clamps speed to limits
	private clampSpeed(): void {
		const {maxSpeed, minSpeed} = this.canvasOpts;
		const speed = Math.sqrt(Math.pow(this.vx, 2) + Math.pow(this.vy, 2));
		if (speed > maxSpeed) {
			this.vx = (this.vx/speed)*maxSpeed;
			this.vy = (this.vy/speed)*maxSpeed;
		}
		if (speed < minSpeed) {
			this.vx = (this.vx/speed)*minSpeed;
			this.vy = (this.vy/speed)*minSpeed;
		}
	}
}  

/** Returns the Euclidean distance between two points in 2D space
 * @param p1 A 2D Cartesian point {x, y} 
 * @param p2 A 2D Cartesian point {x, y}
 * @return The distance (in same units as input) between p1 and p2
 */
function dist(p1: {x: number, y: number}, p2: {x: number, y: number}): number {
	return Math.sqrt(Math.pow(p1.x - p2.x, 2) + Math.pow(p1.y - p2.y, 2));
}

class BoidContainer {
	boids: Boid[];
	n: number;
	canvasOpts: CanvasOpts;
	defaultBoidOpts: BoidOpts;
	canvas: HTMLCanvasElement;
	ctx: CanvasRenderingContext2D;
	running: boolean;

	private previousTimestamp: number | undefined | null;

	/**
	 * BoidContainer  
	 * @param canvas 
	 * @param n 
	 * @param defaultBoidOpts 
	 */
	constructor(canvas: HTMLCanvasElement, n: number = 30, defaultBoidOpts: BoidOpts = {size: 5}) {
		const { avoidFactor, alignFactor, cohereFactor, neighborDist, closeDist, minSpeed, maxSpeed, buffer } = defaultCanvasOpts;
		if (canvas === null) {
			throw 'Canvas element is null';
		}
		const ctx = canvas.getContext('2d');
		if (!ctx) {
			throw 'Browser does not support 2D canvas context'
		}
		this.canvas = canvas;
		this.ctx = ctx;
		this.boids = [];
		this.n = n;
		this.canvasOpts = {
			width: canvas.width,
			height: canvas.height,
			avoidFactor: avoidFactor,
			alignFactor: alignFactor,
			cohereFactor: cohereFactor,
			neighborDist: neighborDist,
			closeDist: closeDist,
			buffer: buffer,
			minSpeed: minSpeed,
			maxSpeed: maxSpeed 
		};
		this.defaultBoidOpts = defaultBoidOpts;
		this.running = false;
	}
	
	/**
	 * Initialize the boids on the canvas
	 */
	init() : void {
		// Reset canvas, if anything is currently there
		//
		this.ctx.beginPath();
		this.ctx.clearRect(0, 0, this.canvas.width, this.canvas.height);
		this.ctx.stroke();

		// Clear boids, if they are there
		this.boids = [];
		// Create n boids
		for (let i = 0; i < this.n; i++) {
			const boid = new Boid(Math.random()*(this.canvasOpts.width - 20) + 10, Math.random()*(this.canvasOpts.height - 20) + 10, this.canvasOpts, {...this.defaultBoidOpts, vx: Math.random()*2*this.canvasOpts.maxSpeed - this.canvasOpts.maxSpeed, vy: Math.random()*2*this.canvasOpts.maxSpeed - this.canvasOpts.maxSpeed}); 
			this.boids.push(boid);
			boid.draw(this.ctx);
		}
	}

	private step(timestamp: number) {
		if (!this.previousTimestamp) {
			this.previousTimestamp = timestamp;
		}

		const dt = timestamp - this.previousTimestamp // dt in milliseconds


		this.ctx.beginPath();
		this.ctx.clearRect(0, 0, this.canvas.width, this.canvas.height);
		this.ctx.stroke();

		this.boids.forEach(boid => {
			const neighbors = this.boids.filter(neighbor => neighbor !== boid && (dist(boid, neighbor) < this.canvasOpts.neighborDist));
			boid.update(dt, neighbors);
			boid.draw(this.ctx);
		});

		this.previousTimestamp = timestamp;
		
		if (this.running) {
			window.requestAnimationFrame(this.step.bind(this));		
		}
	}

	/**
	 * Sets the number of boids
	 * 
	 * @param n The number of boids to be drawn on the canvas
	 */
	setNumber(n: number): void {
		const d = n - this.n;
		if (d > 0) {
			for (let i = 0; i < d; i++) {
				const boid = new Boid(Math.random()*(this.canvasOpts.width - 20) + 10, Math.random()*(this.canvasOpts.height - 20) + 10, this.canvasOpts, {...this.defaultBoidOpts, vx: Math.random()*2*this.canvasOpts.maxSpeed - this.canvasOpts.maxSpeed, vy: Math.random()*2*this.canvasOpts.maxSpeed - this.canvasOpts.maxSpeed}); 
				this.boids.push(boid);
			}
		} else {
			this.boids.splice(0, Math.abs(d));
		}
		this.n = n;
	}

	/**
	 * Start the animation
	 */
	start() {
		this.running = true;
		window.requestAnimationFrame(this.step.bind(this));
	}

	/**
	 * Stop the animation
	 */
	stop() {
		this.running = false;
		this.previousTimestamp = null;
	}

	/**
	 * Sets one or more canvas options to be shared by all boids currently being drawn
	 * 
	 * @param opts One of more canvas options to set for all boids, e.g. avoidFactor, cohereFactor, maxSpeed
	 */
	setCanvasOpts(opts: OptionalCanvasOpts) {
		this.canvasOpts = Object.assign(this.canvasOpts, opts);
	}

	/**
	 *  Sets one ore more boid options to be shared by all boids currently being drawn
	 * 
	 * @param opts One or more boid options to set for all boids, e.g. size, color
	 */
	setBoidOpts(opts: BoidOpts) {
		this.defaultBoidOpts = Object.assign(this.defaultBoidOpts, opts);
		this.boids.forEach(boid => boid.setOpts(opts));
	}
}