Skip to content

Instantly share code, notes, and snippets.

@starcalibre

starcalibre/.gitignore

Last active May 4, 2017 01:38
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save starcalibre/8484a5acaca23f39304780831e79cfa8 to your computer and use it in GitHub Desktop.
Save starcalibre/8484a5acaca23f39304780831e79cfa8 to your computer and use it in GitHub Desktop.
Download ZIP
Boids Simulation
Raw
README.md

Boids is a type of n-body simulation that simulates the flocking behaviour of animals such as birds of fish. A boids simulation applies a few different "rules" to achieve this behaviour, these are:

  • Cohesion - Boids fly towards the center of the group of boids around them.
  • Alignment - Boids attempt to line-up their velocities with boids that are in the vicinity.
  • Separation - Boids attempt to keep some distance from their immediate neighbours.

In addition to these basic rules, this simulation applies a couple of extra rules:

  • Wind Direction - The boids tend to move in a particular direction (up, down, left, right or none at all!) and this will randomly change every so often.
  • Repulsion - Holding down the mouse button over the canvas will cause the boids to avoid the mouse cursor.

Being an n-body simulation, a naive implementation will run in O(n**2) time, as each boid needs to check the position of every other boid in the simulation. We can be a little more smart about the simulation by dividing the boids into a 2D grid. That way, we can search for collisions and near-by boids by only looking at boids belonging to the same, and adjacent grid cells. This demo uses my spatial-partition library, available here.

Raw
Boid.js
'use strict';
function Boid(base, height, position) {
// size, height, other positioning variables
this.base = base;
this.height = height;
this.position = position || new Vector2(0, 0);
this.velocity = new Vector2(0, 0);
this.velocityChange = new Vector2(0, 0);
this.speedLimit = 3;
}
Boid.prototype.draw = function(canvas, ctx) {
var bottomLeftX = -this.base / 2;
var bottomLeftY = this.height / 2;
var bottomRightX = this.base / 2;
var bottomRightY = bottomLeftY;
var topX = 0;
var topY = -this.height / 2;
var angle = this.velocity.getAngle();
ctx.save();
ctx.translate(this.position.x, this.position.y);
ctx.rotate(angle + Math.PI / 2);
ctx.beginPath();
ctx.moveTo(bottomLeftX, bottomLeftY);
ctx.lineTo(bottomRightX, bottomRightY);
ctx.lineTo(topX, topY);
ctx.fill();
ctx.closePath();
ctx.translate(-this.position.x, -this.position.y);
ctx.restore();
};
Boid.prototype.update = function(width, height) {
this.velocity.x += this.velocityChange.x;
this.velocity.y += this.velocityChange.y;
var speed = Math.min(this.speedLimit, this.velocity.magnitude());
var velNorm = this.velocity.normalize();
this.velocity.x = velNorm.x * speed;
this.velocity.y = velNorm.y * speed;
this.position.x += this.velocity.x;
this.position.y += this.velocity.y;
this.position.x = mod(this.position.x, width);
this.position.y = mod(this.position.y, height);
this.velocityChange.x = 0;
this.velocityChange.y = 0;
};
Raw
Common.js
'use strict';
function degToRad(deg) {
return deg * (Math.PI / 180);
}
function clamp(n, min, max) {
return Math.min(Math.max(n, min), max);
}
function mod(n, m) {
return ((n % m) + m) % m;
}
function getMousePos(canvas, evt) {
var rect = canvas.getBoundingClientRect();
return {
x: evt.clientX - rect.left,
y: evt.clientY - rect.top
};
}
function randFloat(min, max) {
return min + (max - min) * Math.random();
}
function randInsideUnitCircle() {
var r = randFloat(2, 5);
var angle = randFloat(0, 2 * Math.PI);
return polarToCartesian(r, angle);
}
function polarToCartesian(r, theta) {
return [
r * Math.cos(theta),
r * Math.sin(theta)
]
}
Raw
gridPartition.min.js
(function(e){if(typeof exports==="object"&&typeof module!=="undefined"){module.exports=e()}else if(typeof define==="function"&&define.amd){define([],e)}else{var t;if(typeof window!=="undefined"){t=window}else if(typeof global!=="undefined"){t=global}else if(typeof self!=="undefined"){t=self}else{t=this}t.GridPartition=e()}})(function(){var e,t,r;return function e(t,r,n){function i(u,a){if(!r[u]){if(!t[u]){var l=typeof require=="function"&&require;if(!a&&l)return l(u,!0);if(o)return o(u,!0);var f=new Error("Cannot find module '"+u+"'");throw f.code="MODULE_NOT_FOUND",f}var s=r[u]={exports:{}};t[u][0].call(s.exports,function(e){var r=t[u][1][e];return i(r?r:e)},s,s.exports,e,t,r,n)}return r[u].exports}var o=typeof require=="function"&&require;for(var u=0;u<n.length;u++)i(n[u]);return i}({1:[function(e,t,r){(function e(){"use strict";if(typeof ses!=="undefined"&&ses.ok&&!ses.ok()){return}function r(e){if(e.permitHostObjects___){e.permitHostObjects___(r)}}if(typeof ses!=="undefined"){ses.weakMapPermitHostObjects=r}var n=false;if(typeof WeakMap==="function"){var i=WeakMap;if(typeof navigator!=="undefined"&&/Firefox/.test(navigator.userAgent)){}else{var o=new i;var u=Object.freeze({});o.set(u,1);if(o.get(u)!==1){n=true}else{t.exports=WeakMap;return}}}var a=Object.prototype.hasOwnProperty;var l=Object.getOwnPropertyNames;var f=Object.defineProperty;var s=Object.isExtensible;var c="weakmap:";var p=c+"ident:"+Math.random()+"___";if(typeof crypto!=="undefined"&&typeof crypto.getRandomValues==="function"&&typeof ArrayBuffer==="function"&&typeof Uint8Array==="function"){var h=new ArrayBuffer(25);var d=new Uint8Array(h);crypto.getRandomValues(d);p=c+"rand:"+Array.prototype.map.call(d,function(e){return(e%36).toString(36)}).join("")+"___"}function v(e){return!(e.substr(0,c.length)==c&&e.substr(e.length-3)==="___")}f(Object,"getOwnPropertyNames",{value:function e(t){return l(t).filter(v)}});if("getPropertyNames"in Object){var _=Object.getPropertyNames;f(Object,"getPropertyNames",{value:function e(t){return _(t).filter(v)}})}function y(e){if(e!==Object(e)){throw new TypeError("Not an object: "+e)}var t=e[p];if(t&&t.key===e){return t}if(!s(e)){return void 0}t={key:e};try{f(e,p,{value:t,writable:false,enumerable:false,configurable:false});return t}catch(e){return void 0}}(function(){var e=Object.freeze;f(Object,"freeze",{value:function t(r){y(r);return e(r)}});var t=Object.seal;f(Object,"seal",{value:function e(r){y(r);return t(r)}});var r=Object.preventExtensions;f(Object,"preventExtensions",{value:function e(t){y(t);return r(t)}})})();function b(e){e.prototype=null;return Object.freeze(e)}var g=false;function w(){if(!g&&typeof console!=="undefined"){g=true;console.warn("WeakMap should be invoked as new WeakMap(), not "+"WeakMap(). This will be an error in the future.")}}var m=0;var O=function(){if(!(this instanceof O)){w()}var e=[];var t=[];var r=m++;function n(n,i){var o;var u=y(n);if(u){return r in u?u[r]:i}else{o=e.indexOf(n);return o>=0?t[o]:i}}function i(t){var n=y(t);if(n){return r in n}else{return e.indexOf(t)>=0}}function o(n,i){var o;var u=y(n);if(u){u[r]=i}else{o=e.indexOf(n);if(o>=0){t[o]=i}else{o=e.length;t[o]=i;e[o]=n}}return this}function u(n){var i=y(n);var o,u;if(i){return r in i&&delete i[r]}else{o=e.indexOf(n);if(o<0){return false}u=e.length-1;e[o]=void 0;t[o]=t[u];e[o]=e[u];e.length=u;t.length=u;return true}}return Object.create(O.prototype,{get___:{value:b(n)},has___:{value:b(i)},set___:{value:b(o)},delete___:{value:b(u)}})};O.prototype=Object.create(Object.prototype,{get:{value:function e(t,r){return this.get___(t,r)},writable:true,configurable:true},has:{value:function e(t){return this.has___(t)},writable:true,configurable:true},set:{value:function e(t,r){return this.set___(t,r)},writable:true,configurable:true},delete:{value:function e(t){return this.delete___(t)},writable:true,configurable:true}});if(typeof i==="function"){(function(){if(n&&typeof Proxy!=="undefined"){Proxy=undefined}function e(){if(!(this instanceof O)){w()}var e=new i;var t=undefined;var o=false;function u(r,n){if(t){return e.has(r)?e.get(r):t.get___(r,n)}else{return e.get(r,n)}}function a(r){return e.has(r)||(t?t.has___(r):false)}var l;if(n){l=function(r,n){e.set(r,n);if(!e.has(r)){if(!t){t=new O}t.set(r,n)}return this}}else{l=function(r,n){if(o){try{e.set(r,n)}catch(e){if(!t){t=new O}t.set___(r,n)}}else{e.set(r,n)}return this}}function f(r){var n=!!e["delete"](r);if(t){return t.delete___(r)||n}return n}return Object.create(O.prototype,{get___:{value:b(u)},has___:{value:b(a)},set___:{value:b(l)},delete___:{value:b(f)},permitHostObjects___:{value:b(function(e){if(e===r){o=true}else{throw new Error("bogus call to permitHostObjects___")}})}})}e.prototype=O.prototype;t.exports=e;Object.defineProperty(WeakMap.prototype,"constructor",{value:WeakMap,enumerable:false,configurable:true,writable:true})})()}else{if(typeof Proxy!=="undefined"){Proxy=undefined}t.exports=O}})()},{}],2:[function(e,t,r){(function(r){t.exports=r.WeakMap!==void 0?r.WeakMap:e("weak-map")}).call(this,typeof global!=="undefined"?global:typeof self!=="undefined"?self:typeof window!=="undefined"?window:{})},{"weak-map":1}],3:[function(e,t,r){"use strict";var n=e("collections/weak-map");var i=e("./util").isNullOrUndefined;var o=e("./util").mod;function u(e,t,r,n){this.width=i(e)?100:e;this.height=i(t)?100:t;this.numberCellsX=i(r)?10:r;this.numberCellsY=i(n)?10:n;this.cellWidth=this.width/this.numberCellsX;this.cellHeight=this.height/this.numberCellsY;this._x=function(e){return e.x};this._y=function(e){return e.y};this.clear()}u.prototype.add=function(e){var t=Math.floor(this._x.call(null,e));var r=Math.floor(this._y.call(null,e));var n=Math.floor(t/this.cellWidth);var i=Math.floor(r/this.cellHeight);this._cells[i][n].push(e);this._entityMap.set(e,[n,i])};u.prototype.addAll=function(e){e.forEach(function(e){this.add(e)}.bind(this))};u.prototype.clear=function(){this._cells=new Array(this.numberCellsX);for(var e=0;e<this.numberCellsY;e++){this._cells[e]=new Array(this.numberCellsX);for(var t=0;t<this.numberCellsX;t++){this._cells[e][t]=[]}}this._entityMap=new n};u.prototype.getCell=function(e,t){if(!this._isCellValid(e,t))return null;return this._cells[t][e]};u.prototype.getCellByWorldCoord=function(e,t){var r=Math.floor(e/this.cellWidth);var n=Math.floor(t/this.cellHeight);return this.getCell(r,n)};u.prototype.getNeighbourhood=function(e,t,r,n){if(i(r)){r=1}if(r<0){r=0}if(i(n)){n=false}var u=[];var a,l,f,s,c;for(a=e-r;a<=e+r;a++){for(l=t-r;l<=t+r;l++){f=o(a,this.numberCellsX);s=o(l,this.numberCellsY);if(!n&&(f!==a||s!==l)){continue}c=this.getCell(f,s);u=u.concat(c)}}return u};u.prototype.getNeighbourhoodByWorldCoord=function(e,t,r,n){var i=Math.floor(Math.floor(e)/this.cellWidth);var o=Math.floor(Math.floor(t)/this.cellHeight);return this.getNeighbourhood(i,o,r,n)};u.prototype.update=function(e){if(!this.remove(e))return false;this.add(e);return true};u.prototype.updateAll=function(e){this.clear();this.addAll(e)};u.prototype.remove=function(e){var t=this._entityMap.get(e);if(i(t))return false;var r=this.getCell(t[0],t[1]);var n=r.indexOf(e);r.splice(n,1);delete this._entityMap[e];return true};u.prototype.x=function(e){if(!i(e)){this._x=e;return this}return this._x};u.prototype.y=function(e){if(!i(e)){this._y=e;return this}return this._y};u.prototype._isCellValid=function(e,t){return e>=0&&t>=0&&e<this.numberCellsX&&t<this.numberCellsY};t.exports=u},{"./util":4,"collections/weak-map":2}],4:[function(e,t,r){"use strict";t.exports={isNullOrUndefined:function(e){return e===null||e===undefined},mod:function(e,t){return(e%t+t)%t}}},{}]},{},[3])(3)});
Raw
index.html
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Boids</title>
</head>
<body>
<canvas id="canvas-main" width="800" height="600"></canvas>
</body>
<script src="Common.js"></script>
<script src="Obstacle.js"></script>
<script src="gridPartition.min.js"></script>
<script src="Vector2.js"></script>
<script src="Boid.js"></script>
<script>
var canvas = document.getElementById('canvas-main');
var ctx = canvas.getContext('2d');
var width = +canvas.width;
var height = +canvas.height;
var moveTowardsCenterOfMass = 1 / 100;
var velocityMatch = 1 / 8;
var windForce = 1 / 10;
var numberBoids = 750;
var boids = [];
var boidBase = 5;
var boidHeight = 10;
var collisionDistance = 7.5;
var windDirection = new Vector2(1, 0);
var windChangeChance = 0.001;
// create a grid partitioning of the space to make neighbour
// searches more efficient
var grid = new GridPartition(width, height, width / 10, height / 10)
.x(function(d) {
return d.position.x;
})
.y(function(d) {
return d.position.y;
});
// create the obstacle object that tracks the mouse and causes the boids to flee
var obstacle = new Obstacle();
// create the set of boids that will be used for the flocking simulation
createBoids();
grid.add(obstacle);
grid.addAll(boids);
var mouseDown = false;
// create event listeners to update the obstacle with the mouse
canvas.addEventListener('mousemove', function(e) {
obstacle.position = getMousePos(canvas, e);
grid.update(obstacle);
});
canvas.addEventListener('mousedown', function() {
mouseDown = true;
obstacle.show();
});
canvas.addEventListener('mouseup', function() {
mouseDown = false;
obstacle.hide();
});
canvas.addEventListener('mouseleave', function() {
obstacle.hide();
});
canvas.addEventListener('mouseenter', function() {
if(mouseDown) obstacle.show();
});
// start the show!
animate();
function updateBoids() {
grid.updateAll(boids);
grid.add(obstacle);
boids.forEach(function(boid) {
var neighbours = grid.getNeighbourhoodByWorldCoord(boid.position.x, boid.position.y, 3);
if(neighbours.length == 1) { return; } // no nearby objects
var center = new Vector2(0, 0);
var velocitySum = new Vector2(0, 0);
neighbours.forEach(function(neighbour) {
// calculate local center of mass
if(boid !== neighbour && (neighbour instanceof Boid)) {
center.x += neighbour.position.x;
center.y += neighbour.position.y;
velocitySum.x += neighbour.velocity.x;
velocitySum.y += neighbour.velocity.y;
}
// repulsion - avoid the obstacle
if(neighbour instanceof Obstacle && neighbour.active) {
boid.velocityChange.x -= (neighbour.position.x - boid.position.x) * 2;
boid.velocityChange.y -= (neighbour.position.y - boid.position.y) * 2;
}
});
center.x /= (neighbours.length - 1);
center.y /= (neighbours.length - 1);
velocitySum.x /= (neighbours.length - 1);
velocitySum.y /= (neighbours.length - 1);
// cohesion -- steer towards center of mass of neighbouring boids
boid.velocityChange.x += (center.x - boid.position.x) * moveTowardsCenterOfMass;
boid.velocityChange.y += (center.y - boid.position.y) * moveTowardsCenterOfMass;
// alignment -- boids take same heading as neighbouring boids
boid.velocityChange.x += (velocitySum.x - boid.velocity.x) * velocityMatch;
boid.velocityChange.y += (velocitySum.y - boid.velocity.y) * velocityMatch;
// wind -- apply a force pushing the boids to the right
boid.velocityChange.x += windDirection.x * windForce;
boid.velocityChange.y += windDirection.y * windForce;
});
// separation -- steer to avoid collisions with other boids
boids.forEach(function(boid) {
var colliders = grid.getNeighbourhoodByWorldCoord(boid.position.x, boid.position.y, 1);
if(colliders.length == 1) { return; } // nobody nearby to collide with
var separation = new Vector2(0, 0);
colliders.forEach(function(collider) {
if(boid != collider && boidDistance(boid, collider) < collisionDistance && (collider instanceof Boid)) {
separation.x -= (collider.position.x - boid.position.x);
separation.y -= (collider.position.y - boid.position.y);
}
});
boid.velocityChange.x += separation.x;
boid.velocityChange.y += separation.y;
});
// update all the boids
boids.forEach(function(b) {
b.update(width, height);
});
// update wind direction (maybe!)
if(Math.random() < windChangeChance) {
windDirection.x = Math.random() < 0.5 ? 0 : 1;
windDirection.y = Math.random() < 0.5 ? 0 : 1;
windDirection.x *= Math.random() < 0.5 ? -1 : 1;
windDirection.y *= Math.random() < 0.5 ? -1 : 1;
}
}
function createBoids() {
var i, newBoid, newPos, newVel;
for(i = 0; i < numberBoids; i++) {
newPos = new Vector2(randFloat(0, width), randFloat(0, height));
newBoid = new Boid(boidBase, boidHeight, newPos);
newVel = randInsideUnitCircle();
newBoid.velocity.x = newVel[0];
newBoid.velocity.y = newVel[1];
boids.push(newBoid);
}
}
function boidDistance(a, b) {
var dx = a.position.x - b.position.x;
var dy = a.position.y - b.position.y;
return Math.sqrt(dx * dx + dy * dy);
}
function draw() {
ctx.clearRect(0, 0, width, height);
boids.forEach(function(b) {
b.draw(canvas, ctx);
});
obstacle.render(ctx);
}
function animate() {
requestAnimationFrame(animate);
updateBoids();
draw();
}
</script>
</html>
Raw
Obstacle.js
'use strict';
function Obstacle() {
this.minRadius = 3;
this.maxRadius = 10;
this.minAlpha = 0.1;
this.maxAlpha = 0.8;
this.baseColour = '#FF0000';
this.radiusDelta = 0.1;
this.alphaDelta = (this.maxAlpha - this.minAlpha) / ((this.maxRadius - this.minRadius) / this.radiusDelta);
this.position = { x: 0, y: 0 };
this.active = false;
this.radius = this.minRadius;
this.alpha = this.minAlpha;
}
Obstacle.prototype.show = function() {
this.radius = this.minRadius;
this.alpha = this.minAlpha;
this.active = true;
};
Obstacle.prototype.hide = function() {
this.active = false;
};
Obstacle.prototype.render = function(ctx) {
if(!this.active) return;
this.radius += this.radiusDelta;
this.alpha += this.alphaDelta;
if(this.radius > this.maxRadius) {
this.radius = this.minRadius;
}
if(this.alpha > this.maxAlpha) {
this.alpha = this.minAlpha;
}
ctx.save();
ctx.beginPath();
ctx.arc(this.position.x, this.position.y, this.radius, 0, 2 * Math.PI);
ctx.fillStyle = this.baseColour;
ctx.globalAlpha = this.alpha;
ctx.fill();
ctx.closePath();
ctx.restore();
};
Raw
Vector2.js
'use strict';
// simple 2d vector class with add, subtract, magnitude and normalise methods
function Vector2(x, y) {
this.x = x || 0;
this.y = y || 0;
}
Vector2.prototype.add = function(v) {
return new Vector2(this.x + v.x, this.y + v.y);
};
Vector2.prototype.subtract = function(v) {
return new Vector2(this.x - v.x, this.y - v.y);
};
Vector2.prototype.magnitude = function() {
return Math.sqrt(this.x * this.x + this.y * this.y);
};
Vector2.prototype.magnitudeSq = function() {
return this.x * this.x + this.y * this.y;
};
Vector2.prototype.normalize = function() {
var mag = this.magnitude();
return new Vector2(this.x / mag, this.y / mag);
};
Vector2.prototype.distanceTo = function(v) {
var delta = this.subtract(v);
return delta.magnitude();
};
Vector2.prototype.distanceToSq = function(v) {
var delta = this.subtract(v);
return delta.magnitudeSq();
};
Vector2.prototype.getAngle = function() {
return Math.atan2(this.y, this.x);
};
Vector2.prototype.rotateVector = function(angle) {
var x = this.x * Math.cos(angle) - this.y * Math.sin(angle);
var y = this.x * Math.sin(angle) + this.y * Math.cos(angle);
return new Vector2(x, y);
};
Vector2.prototype.dot = function(v) {
return this.x * v.x + this.y * v.y;
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment