Skip to content

Instantly share code, notes, and snippets.

@HarryStevens
Last active Jul 27, 2020
Embed
What would you like to do?
Good Boids
license: gpl-3.0

This is my version of Craig Reynolds’s boids, using Vladimir Agafonkin’s RBush as a spatial index to improve efficiency. Compare to Bad Boids.

Click and drag to add boids.

<!DOCTYPE html>
<html>
<head>
<style>
body {
font-family: sans-serif;
margin: 0;
}
#controls {
padding: 5px;
position: absolute;
text-align: center;
width: 100%;
bottom: 0px;
}
#controls .control {
background: rgba(255, 255, 255, .8);
display: inline-block;
padding: 10px;
text-align: left;
width: 200px;
}
#controls .control .range input, #controls .control .range .value {
display: inline-block;
}
#controls .control .range .value {
font-size: 12px;
margin-top: -5px;
vertical-align: middle;
}
#controls .control .description {
font-size: 12px;
}
#stats {
font-size: 14px;
padding: 5px;
position: absolute;
right: 0px;
}
</style>
</head>
<div id="controls">
<div class="control">
<div class="title">Alignment</div>
<div class="range">
<input data-parameter="alignment" type="range" min="0" max="1" value="1" step=".1" />
<div class="value">1.0</div>
</div>
<div class="description">Steer towards the average heading of local flockmates</div>
</div>
<div class="control">
<div class="title">Cohesion</div>
<div class="range">
<input data-parameter="cohesion" type="range" min="0" max="1" value="1" step=".1" />
<div class="value">1.0</div>
</div>
<div class="description">Steer towards the average position of local flockmates</div>
</div>
<div class="control">
<div class="title">Separation</div>
<div class="range">
<input data-parameter="separation" type="range" min="0" max="1" value="1" step=".1" />
<div class="value">1.0</div>
</div>
<div class="description">Steer to avoid crowding local flockmates</div>
</div>
<div class="control">
<div class="title">Perception</div>
<div class="range">
<input data-parameter="perception" type="range" min="1" max="100" value="20" step="1" />
<div class="value">20</div>
</div>
<div class="description">Maximum distance of other boids to consider</div>
</div>
</div>
<div id="stats"></div>
<div id="simulation"></div>
<body>
<script src="https://unpkg.com/rbush@2.0.1/rbush.min.js"></script>
<script src="vecmath.js"></script>
<script src="https://d3js.org/d3-color.v1.min.js"></script>
<script src="https://d3js.org/d3-interpolate.v1.min.js"></script>
<script src="https://d3js.org/d3-scale-chromatic.v1.min.js"></script>
<script src="https://d3js.org/d3-array.v2.min.js"></script>
<script>
class BoidBush extends rbush {
toBBox(boid) { return {minX: boid.pos[0], minY: boid.pos[1], maxX: boid.pos[0], maxY: boid.pos[1]}; }
compareMinX(a, b) { return a.pos[0] - b.pos[0]; }
compareMinY(a, b) { return a.pos[1] - b.pos[1]; }
}
class Boids {
constructor(){
this._width = innerWidth;
this._height = innerHeight;
this._perception = 20;
this._alignment = 1;
this._cohesion = 1;
this._separation = 1;
this._maxSpeed = 4;
this.maxForce = 0.2;
this.flock = [];
this.tree = new BoidBush();
}
alignment(n){
if (isFinite(n)){
this._alignment = n;
for (let i = 0, l = this.flock.length; i < l; i++){
this.flock[i]._alignment = n;
}
return this;
}
else {
return this._alignment;
}
}
cohesion(n){
if (isFinite(n)){
this._cohesion = n;
for (let i = 0, l = this.flock.length; i < l; i++){
this.flock[i]._cohesion = n;
}
return this;
}
else {
return this._cohesion;
}
}
perception(n){
if (isFinite(n)){
this._perception = n;
for (let i = 0, l = this.flock.length; i < l; i++){
this.flock[i]._perception = n;
}
return this;
}
else {
return this._perception;
}
}
separation(n){
if (isFinite(n)){
this._separation = n;
for (let i = 0, l = this.flock.length; i < l; i++){
this.flock[i]._separation = n;
}
return this;
}
else {
return this._separation;
}
}
width(n){
if (isFinite(n)){
this._width = n;
for (let i = 0, l = this.flock.length; i < l; i++){
this.flock[i]._width = n;
}
return this;
}
else {
return this._width;
}
}
height(n){
if (isFinite(n)){
this._height = n;
for (let i = 0, l = this.flock.length; i < l; i++){
this.flock[i]._height = n;
}
return this;
}
else {
return this._height;
}
}
maxSpeed(n){
if (isFinite(n)){
this._maxSpeed = n;
for (let i = 0, l = this.flock.length; i < l; i++){
this.flock[i]._maxSpeed = n;
}
return this;
}
else {
return this._maxSpeed;
}
}
add(opts){
this.flock.push(new Boid(this, opts));
return this;
}
each(fn){
for (let i = 0, l = this.flock.length; i < l; i++){
fn(this.flock[i], i, this.flock);
}
return this;
}
tick(){
this.tree.clear();
this.tree.load(this.flock);
this.each(boid => boid.update());
return this;
}
}
class Boid {
constructor(Boids, opts){
Object.assign(this, Boids);
Object.assign(this, opts);
// Angle, position, and speed can be assigned by the user.
this.ang = this.ang || 2 * Math.random() * Math.PI;
this.pos = this.pos || [
Math.random() * this._width,
Math.random() * this._height
];
this.speed = this.speed || 1;
const obj = {
pos: this.pos,
ang: this.ang,
speed: this.speed,
vel: vecmath.sub(
vecmath.trans(this.pos, this.ang, this.speed),
this.pos
),
acc: [0, 0],
id: this.flock.length
};
Object.assign(this, obj);
}
update(){
// To learn more about this math, see https://www.youtube.com/watch?v=mhjuuHl6qHM
const prev = { ...this };
let alignment = [0, 0],
cohesion = [0, 0],
separation = [0, 0],
n = 0,
candidates = this.tree.search({
minX: this.pos[0] - this._perception,
minY: this.pos[1] - this._perception,
maxX: this.pos[0] + this._perception,
maxY: this.pos[1] + this._perception,
});
for (let i = 0, l = candidates.length; i < l; i ++){
const that = candidates[i],
dist = vecmath.dist(this.pos, that.pos);
if (this.id !== that.id && dist < this._perception){
alignment = vecmath.add(alignment, that.vel);
cohesion = vecmath.add(cohesion, that.pos);
const diff = vecmath.div(
vecmath.sub(this.pos, that.pos),
Math.max(dist, 1e-6)
);
separation = vecmath.add(separation, diff);
n++;
}
}
if (n > 0){
alignment = vecmath.div(alignment, n);
alignment = vecmath.setMag(alignment, this._maxSpeed);
alignment = vecmath.sub(alignment, this.vel);
alignment = vecmath.limit(alignment, this.maxForce);
cohesion = vecmath.div(cohesion, n);
cohesion = vecmath.sub(cohesion, this.pos);
cohesion = vecmath.setMag(cohesion, this._maxSpeed);
cohesion = vecmath.sub(cohesion, this.vel);
cohesion = vecmath.limit(cohesion, this.maxForce);
separation = vecmath.div(separation, n);
separation = vecmath.setMag(separation, this._maxSpeed);
separation = vecmath.sub(separation, this.vel);
separation = vecmath.limit(separation, this.maxForce);
}
alignment = vecmath.mult(alignment, this._alignment);
cohesion = vecmath.mult(cohesion, this._cohesion);
separation = vecmath.mult(separation, this._separation);
this.acc = vecmath.add(this.acc, alignment);
this.acc = vecmath.add(this.acc, cohesion);
this.acc = vecmath.add(this.acc, separation);
this.pos = vecmath.add(this.pos, this.vel);
this.vel = vecmath.add(this.vel, this.acc);
this.vel = vecmath.limit(this.vel, this._maxSpeed);
if (this.pos[0] > this._width) this.pos[0] = 0;
if (this.pos[0] < 0) this.pos[0] = this._width;
if (this.pos[1] > this._height) this.pos[1] = 0;
if (this.pos[1] < 0) this.pos[1] = this._height;
this.ang = vecmath.ang(prev.pos, this.pos);
this.speed = vecmath.dist(prev.pos, this.pos);
this.acc = vecmath.mult(this.acc, 0);
}
}
// Initiate some boids
const myBoids = (_ => {
const sim = new Boids;
// Add 500 boids
for (let i = 0; i < 500; i++) {
sim.add();
}
return sim;
})();
// Draw the simulation
const wrapper = document.getElementById("simulation"),
canvas = document.createElement("canvas"),
context = canvas.getContext("2d");
canvas.width = myBoids.width();
canvas.height = myBoids.height();
wrapper.appendChild(canvas);
// Some variables for stats
let stats = document.querySelector("#stats"),
startTime = (new Date()).getTime(),
seconds = 0,
secondsRounded = 0,
ticks = 0,
speeds = [0];
function tick(){
requestAnimationFrame(tick);
context.clearRect(0, 0, myBoids.width(), myBoids.height());
// The simulation.tick method advances the simulation one tick
myBoids.tick();
myBoids.each(boid => {
const a = vecmath.trans(boid.pos, boid.ang - Math.PI * .5, 3),
b = vecmath.trans(boid.pos, boid.ang, 9),
c = vecmath.trans(boid.pos, boid.ang + Math.PI * .5, 3);
context.beginPath();
context.moveTo(...a);
context.lineTo(...b);
context.lineTo(...c);
context.lineTo(...a);
const color = d3.interpolateRdPu(.6 * myBoids.maxSpeed() / boid.speed);
context.strokeStyle = color;
context.fillStyle = d3.color(color).brighter(2);
context.fill();
context.stroke();
});
seconds = ((new Date()).getTime() - startTime) / 1e3;
ticks++;
stats.innerHTML = `${myBoids.flock.length} boids at ${d3.mean(speeds)} frames/sec.`;
if (Math.round(seconds) !== secondsRounded){
speeds.push(ticks);
if (speeds.length > 2) speeds.shift();
secondsRounded = Math.round(seconds);
ticks = 0;
}
}
tick();
// Logic for adding boids
let holding = false;
canvas.addEventListener("mousedown", e => { holding = true; addBoidOnEvent(e); });
canvas.addEventListener("mouseup", e => { holding = false });
canvas.addEventListener("mousemove", e => { if (holding) addBoidOnEvent(e); });
function addBoidOnEvent(e){
myBoids.add({
pos: [e.pageX, e.pageY]
});
}
// Logic for resizing
addEventListener("resize", _ => {
myBoids.width(innerWidth);
myBoids.height(innerHeight);
canvas.width = myBoids.width();
canvas.height = myBoids.height();
});
// Logic for using the sliders
const controls = document.querySelectorAll(".control");
controls.forEach(control => {
control.addEventListener("input", _ => {
const t = _.target,
v = +t.value;
t.nextElementSibling.innerHTML = v;
myBoids[t.dataset.parameter](v);
});
});
</script>
</body>
</html>
// Add vector w to vector v
function add(v, w) {
let out = [];
for (let i = 0; i < v.length; i++){
out[i] = v[i] + w[i];
}
return out;
}
// Subtract vector w from vector v
function sub(v, w) {
let out = [];
for (let i = 0; i < v.length; i++){
out[i] = v[i] - w[i];
}
return out;
}
// Multiply vector v by w, either a vector of equal length or a number
function mult(v, w) {
let that = [];
if (typeof w === "number"){
for (let i = 0; i < v.length; i++){
that[i] = w;
}
}
else {
that = w;
}
let out = [];
for (let i = 0; i < v.length; i++){
out[i] = v[i] * that[i];
}
return out;
}
// Divide vector v by w, either a vector of equal length or a number
function div(v, w) {
let that = [];
if (typeof w === "number"){
for (let i = 0; i < v.length; i++){
that[i] = w;
}
}
else {
that = w;
}
let out = [];
for (let i = 0; i < v.length; i++){
out[i] = v[i] / that[i];
}
return out;
}
// Limit the magnitude of this vector to the value used for the n parameter.
function limit(v, n) {
let out = v;
const sq = Math.pow(getMag(v), 2);
if (sq > n * n){
out = div(out, Math.sqrt(sq));
out = mult(out, n);
}
return out;
}
// Normalize the vector to length 1 (make it a unit vector).
function normalize(v) {
const m = getMag(v), l = v.length;
return m ? mult(v, 1 / m) : v.map(d => 1 / l);
}
// Get the magnitude of a vector
function getMag(v) {
let l = v.length, sums = 0;
for (let i = 0; i < l; i++){
sums += v[i] * v[i];
}
return Math.sqrt(sums);
}
// Set the magnitude of this vector to the value used for the n parameter.
function setMag(v, n) {
return mult(normalize(v), n);
}
// Angle from vector v to vector w in radians
function ang(v, w) {
return Math.atan2(w[1] - v[1], w[0] - v[0]);
}
// Distance from position of vector v to position of vector w in pixels
function dist(v, w) {
return Math.sqrt(Math.pow(w[0] - v[0], 2) + Math.pow(w[1] - v[1], 2));
}
// Translate position of vector v by an angle in radians and a distance in pixels
function trans(v, ang, dist) {
return [v[0] + dist * Math.cos(ang), v[1] + dist * Math.sin(ang)];
}
const vecmath = {
add, sub, mult, div, limit, normalize, getMag, setMag, ang, dist, trans
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment