let boids = [];

const BOID_COUNT = 1000;

const VIEW_RADIUS = 20;

const QUAD_CAPACITY = 2;

​

function setup() {

  createCanvas(405, 720);

  strokeWeight(5);

  for (let i = 0; i < BOID_COUNT; i++) {

    boids.push(new Boid(random(width), random(height)));

  }

}

​

function draw() {

  background(0,10);

  // Create quadtree

  let boundary = new Rectangle(width/2, height/2, width/2, height/2);

  qtree = new QuadTree(boundary, QUAD_CAPACITY);

  strokeWeight(1)

  // Update and show boids

  for (let boid of boids) {

    let p = new Point(boid.pos.x, boid.pos.y, boid);

    qtree.insert(p);

  }

  qtree.show();

  strokeWeight(3);

  for (let boid of boids) {

    let range = new Rectangle(boid.pos.x, boid.pos.y, VIEW_RADIUS, VIEW_RADIUS);

    let neighbors = qtree.query(range);

    boid.update(neighbors);

    stroke(255);

    point(boid.pos.x, boid.pos.y);

  }

}

​

class Boid {

  constructor(x, y) {

    this.pos = createVector(x, y);

    this.vel = p5.Vector.random2D();

    this.vel.setMag(random(2, 4));

    this.acc = createVector();

  }

​

  update(neighbors) {

    let align = createVector();

    let cohesion = createVector();

    let separation = createVector();

    let total = 0;

​

    let alignStrength = map(mouseY, 0, height, 2, 10);

    let separationStrength = map(mouseX, 0, width, 1.2, 3);

​

    for (let point of neighbors) {

      let other = point.userData;

      if (other !== this) {

        let d = dist(this.pos.x, this.pos.y, other.pos.x, other.pos.y);

        if (d < VIEW_RADIUS) {

          align.add(other.vel);

          cohesion.add(other.pos);

          let diff = p5.Vector.sub(this.pos, other.pos);

          diff.div(d);

          separation.add(diff);

          total++;

        }

      }

    }

​

    if (total > 0) {

      align.div(total).setMag(alignStrength);

      cohesion.div(total).sub(this.pos).setMag(2);

      separation.div(total).setMag(separationStrength);

      this.acc.add(align);

      this.acc.add(cohesion);

      this.acc.add(separation);

    }

​

    this.vel.add(this.acc).limit(4);

    this.pos.add(this.vel);

    this.acc.set(0, 0);

    this.edges();

  }

  edges() {

    if (this.pos.x > width) this.pos.x = 0;

    if (this.pos.x < 0) this.pos.x = width;

    if (this.pos.y > height) this.pos.y = 0;

    if (this.pos.y < 0) this.pos.y = height;

  }

}

​

class Point {

  constructor(x, y, userData) {

    this.x = x;

    this.y = y;

    this.userData = userData;

  }

}

​

class Rectangle {

  constructor(x, y, w, h) {

    this.x = x;

    this.y = y;

    this.w = w;

    this.h = h;

  }

  contains(point) {

    return (point.x >= this.x - this.w &&

            point.x < this.x + this.w &&

            point.y >= this.y - this.h &&

            point.y < this.y + this.h);

  }

  intersects(range) {

    return !(range.x - range.w > this.x + this.w ||

             range.x + range.w < this.x - this.w ||

             range.y - range.h > this.y + this.h ||

             range.y + range.h < this.y - this.h);

  }

}

​

class QuadTree {

  constructor(boundary, n) {

    this.boundary = boundary;

    this.capacity = n;

    this.points = [];

    this.divided = false;

  }

​

  subdivide() {

    let x = this.boundary.x;

    let y = this.boundary.y;

    let w = this.boundary.w / 2;

    let h = this.boundary.h / 2;

    let nw = new Rectangle(x - w, y - h, w, h);

    let ne = new Rectangle(x + w, y - h, w, h);

    let sw = new Rectangle(x - w, y + h, w, h);

    let se = new Rectangle(x + w, y + h, w, h);

    this.northwest = new QuadTree(nw, this.capacity);

    this.northeast = new QuadTree(ne, this.capacity);

    this.southwest = new QuadTree(sw, this.capacity);

    this.southeast = new QuadTree(se, this.capacity);

    this.divided = true;

  }

​

  insert(point) {

    if (!this.boundary.contains(point)) return false;

    if (this.points.length < this.capacity) {

      this.points.push(point);

      return true;

    }

    if (!this.divided) this.subdivide();

    return (this.northwest.insert(point) ||

            this.northeast.insert(point) ||

            this.southwest.insert(point) ||

            this.southeast.insert(point));

  }

​

  query(range, found = []) {

    if (!this.boundary.intersects(range)) return found;

    for (let p of this.points) {

      if (range.contains(p)) found.push(p);

    }

    if (this.divided) {

      this.northwest.query(range, found);

      this.northeast.query(range, found);

      this.southwest.query(range, found);

      this.southeast.query(range, found);

    }

    return found;

  }

​

  show() {

    stroke(255, 50);

    noFill();

    rectMode(CENTER);

    rect(this.boundary.x, this.boundary.y, this.boundary.w * 2, this.boundary.h * 2);

    if (this.divided) {

      this.northwest.show();

      this.northeast.show();

      this.southwest.show();

      this.southeast.show();

    }

  }

}