Quadtree Collision Detection

AABB Collision Detection implemented with a recursive quadtree

by Carl Baumann

HTML

<canvas id="myCanvas" width="640" height="640"></canvas>

CSS

canvas { background: #eee; }

JavaScript

// recursive quadtree implementation

let canvas = document.getElementById("myCanvas");
let ctx = canvas.getContext("2d");

let t0 = performance.now();

let config={
	gravity : new Vector2(0,98),
  
  maxBranchLevel : 4,
  maxBallsPer : 4,
  
  ballCount : 100,
  ballMass : 1,
  ballRadius : 10,
  maxBallVelocity : 0.1
};


function Quadrant(x,y,w,h,subDepth = 0) {
	this.x = x;
  this.y = y;
  this.w = w;
  this.h = h;
  this.subDepth = subDepth;
  this.subQuads = [];
  this.isSubdivided = false;
  this.contents = [];
  
  this.subdivide = function() {
  	if (this.isSubdivided || this.subDepth > config.maxBranchLevel) { return; }
    
  	else {
	    let q1 = new Quadrant(this.x+this.w/2,this.y,this.w/2,this.h/2,this.subDepth+1);
  	 	let q2 = new Quadrant(this.x,this.y,this.w/2,this.h/2,this.subDepth+1);
	    let q3 = new Quadrant(this.x,this.y+this.h/2,this.w/2,this.h/2,this.subDepth+1);
	    let q4 = new Quadrant(this.x+this.w/2,this.y+this.h/2,this.w/2,this.h/2,this.subDepth+1);
      
	    this.isSubdivided = true;
  	  this.subQuads.push(q1);
	    this.subQuads.push(q2);
 	    this.subQuads.push(q3);
	    this.subQuads.push(q4);
      
	    return;
    }
  }
  
  this.draw = function(){
  	ctx.beginPath();
		ctx.rect(this.x, this.y, this.w, this.h);
		ctx.fillStyle = "#000000";
		ctx.stroke();
		ctx.closePath();
    
    if (this.isSubdivided) {
    	for(let index = 0; index < 4; index++) {
      	this.subQuads[index].draw();
      }
    }
    else {
/*     	ctx.font = "16px Arial";
    	      ctx.fillStyle = "#9500DD";
    	
    	      ctx.fillText(this.contents.length,this.x+this.w/2, this.y+this.h/2); */
    }
	}
  
  this.clear = function() {
  	this.isSubdivided = false;
    this.subQuads = [];
  }
  
  this.sortContents = function(items) {
  
  	if(!this.isSubdivided && items.length > config.maxBallsPer) {
  		this.subdivide();
  	}
  
  if(this.isSubdivided) {
    	let q1Items = [];
      let q2Items = [];
      let q3Items = [];
      let q4Items =...