Diffusion Limited Aggregation

click on sketch to restart the simulation
Quad Tree Optimisation

// ##### Main Sketch

let moving = []; 
let diameter = 8; // diameter of all particles
let iterations = 100;
let col = 0;
let done = false;
let c1, c2, c3, c4, c5;
let maxWalkers;


// quadtree
let qtree;



function setup() {
  createCanvas(500, 500);
  frameRate(60);
  noStroke();
  
  // # Sketch settings
  maxWalkers = width *1.5;
  
  // # Color Palette
  c1 = color(255, 205, 178);
  c2 = color(255, 180, 162);
  c3 = color(229, 152, 155);
  c4 = color(181, 131, 141);
  c5 = color(109, 104, 117);
  
  init();
}

function init(){
  
    // # create quadtree
  let boundary = new Rectangle(width/2, height/2, width, height);
  qtree = new QuadTree(boundary, 4);

  // # create first fixed particle in the center of the sketch
  let first = new Particle(width/2,height/2)
  first.col = (-cos(col) + 1)/2;
  qtree.insert(first);

  for (var i = 0; i < maxWalkers; i++) {
    moving[i] = new Particle();
  }
}

function mouseClicked() { 
  init();
} 

function draw() {
  background(c5); // Draw Background

  // # Display all moving particles
  fill(200,10);
  for (let i = 0; i < moving.length; i++) {
    moving[i].render();
  }

  for (let j = 0; j < iterations; j++) {
    for (let i = 0; i < moving.length; i++) {
      moving[i].update(); // Update position
      
      // quadtree search
      //let range = new Circle(moving[i].pos.x, moving[i].pos.y, diameter); // DO I NEED 2 PUT DIAMETER OR HIGHR
      let fixed = qtree.query(new Circle(moving[i].pos.x, moving[i].pos.y, diameter));
      
      // collision check
      if (moving[i].collision(fixed)) {
        col += 1/maxWalkers ;
        moving[i].col = col;
        qtree.insert(moving[i]);
        moving.splice(i, 1);
      }
    }
  }
  
  qtree.renderPoints();

}

// Custom Functions

function distSq(a, b) {
  return (b.x - a.x) ** 2 + (b.y - a.y) ** 2;
}

function lerpColorThree(c1, c2, c3, i)
{
  return ((i <= 0.5) ? lerpColor(c1,c2, i*2) : lerpColor(c2,c3, (i-0.5)*2));
}

function lerpColorFive(c1, c2, c3, c4, c5, i)
{
  if(i <= 0.25)       {return lerpColor(c1,c2, map(i,0,0.25,0,1));}
  else if(i <= 0.5)   {return lerpColor(c2,c3, map(i,0.25,0.5,0,1));}
  else if(i <= 0.75)  {return lerpColor(c3,c4, map(i,0.5,0.75,0,1));}
  else                {return lerpColor(c4,c5, map(i,0.75,1,0,1));}
}

// ##### Particle Prototype

class Particle {
  constructor(x,y) {
    if (arguments.length == 2) {
      this.pos = createVector(x,y);

    } else {
      let r = int(random(0,4));
      if( r == 0 ) {this.pos = createVector(random(0,width),0)} // north
      if( r == 1 ) {this.pos = createVector(random(0,width),height)} // south
      if( r == 2 ) {this.pos = createVector(0,random(0,height))} // west
      if( r == 3 ) {this.pos = createVector(width,random(0,height))} // east

    }
  }

  update() {
    var vel = p5.Vector.random2D();
    var tow = createVector(width/2 - this.pos.x, height/2 - this.pos.y); // towards aggregation 
    vel.add(tow.setMag(0.01));
    this.pos.add(vel);

    // # constrain
    //this.pos.x = constrain(this.pos.x, 0, width); 
    //this.pos.y = constrain(this.pos.y, 0, height);
  }

  collision(others) { 
    for (var i = 0; i < others.length; i++) { 
      // # calculate distance between [this] particle and every fixed particle
      let d = (this.pos.x - others[i].pos.x) ** 2 + (this.pos.y - others[i].pos.y) ** 2;
      //let d = distSq(this.pos, others[i].pos);
      if (d < diameter ** 2) { // if collision
        return true;
      }
    }
  }

  render() {
    circle(this.pos.x, this.pos.y, diameter);
  }
}

// ##### Quadtree Helper Classes

class Rectangle {
  constructor(x, y, w, h) {
    this.x = x;
    this.y = y;
    this.w = w;
    this.h = h;
  }

  contains(point) {
    return (point.pos.x >= this.x - this.w &&
      point.pos.x <= this.x + this.w &&
      point.pos.y >= this.y - this.h &&
      point.pos.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 Circle {
  constructor(x, y, r) {
    this.x = x;
    this.y = y;
    this.r = r;
  }

  contains(point) {
    //let d = distSq(point.pos, createVector(this.x,this.y));
    let d = (point.pos.x - this.x) ** 2 + (point.pos.y - this.y) ** 2;
    return d <= this.r ** 2;
  }

  intersects(range) {

    var xDist = Math.abs(range.x - this.x);
    var yDist = Math.abs(range.y - this.y);

    // radius of the circle
    var r = this.r;

    var w = range.w;
    var h = range.h;

    var edges = (xDist - w) ** 2 + (yDist - h) ** 2;

    // no intersection
    if (xDist > (r + w) || yDist > (r + h))
      return false;

    // intersection within the circle
    if (xDist <= w || yDist <= h)
      return true;

    // intersection on the edge of the circle
    return edges <= this.r ** 2;
  }
}

// ##### Quadtree Class

class QuadTree {
  constructor(boundary, capacity) {
    if (!boundary) {
      throw TypeError('boundary is null or undefined');
    }
    if (!(boundary instanceof Rectangle)) {
      throw TypeError('boundary should be a Rectangle');
    }
    if (typeof capacity !== 'number') {
      throw TypeError(`capacity should be a number but is a ${typeof capacity}`);
    }
    if (capacity < 1) {
      throw RangeError('capacity must be greater than 0');
    }
    this.boundary = boundary;
    this.capacity = capacity;
    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 ne = new Rectangle(x + w, y - h, w, h);
    this.northeast = new QuadTree(ne, this.capacity);
    let nw = new Rectangle(x - w, y - h, w, h);
    this.northwest = new QuadTree(nw, this.capacity);
    let se = new Rectangle(x + w, y + h, w, h);
    this.southeast = new QuadTree(se, this.capacity);
    let sw = new Rectangle(x - w, y + h, w, h);
    this.southwest = new QuadTree(sw, 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();
    }

    if (this.northeast.insert(point) || this.northwest.insert(point) ||
      this.southeast.insert(point) || this.southwest.insert(point)) {
      return true;
    }
  }

  query(range, found) {
    if (!found) {
      found = [];
    }

    if (!range.intersects(this.boundary)) {
      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;
  }

  renderPoints(){
    
    for(let p of this.points){
      let l = lerpColorFive(c1,c2,c3,c4,c5, p.col);
      fill(l);
      circle(p.pos.x,p.pos.y,diameter);
    }

    if (this.divided) {
      this.northwest.renderPoints();
      this.northeast.renderPoints();
      this.southwest.renderPoints();
      this.southeast.renderPoints();
    }
  }
  
  renderQuads(){
    if (this.divided) {
      this.northwest.renderQuads();
      this.northeast.renderQuads();
      this.southwest.renderQuads();
      this.southeast.renderQuads();
    }
    else{        
      rect(this.boundary.x, this.boundary.y, this.boundary.w*2-3, this.boundary.h*2-3); 
    }
  }
}