p5.js Web Editor | Quadtree Terrain

xxxxxxxxxx
let q;
​
let bombs = [];
const numBombs = 1;
​
const EMPTY = 0;
const SOLID = 1;
const MIXED = -1;
const MIN_QUAD_SIZE = 1;
​
let r = 100;
let shape = null;
let sub = false;
​
let debug = false;
​
function setup() {
  createCanvas(600, 600);
  q = new Quad(0, 0, width, height, EMPTY, 1);
  changeBrush();
  
  while(bombs.length < numBombs) {
    bombs.push(new Bomb(random(width), 0));
  }
}
​
function draw() {
  background(220);
  
  q.show();
  
  bombs = bombs.map(b => {
    b.update();
    b.show();
    let hit = q.hits(b);
    if(hit) {
      const blast = b.blast()
      fill(255, 128, 0);
      blast.show();
      q.subtract(blast);
    }
    
    return hit || b.y > height ? new Bomb(random(width), 0) : b;
  });
  
  noFill();
  if(sub) {
    stroke(255, 0, 0);  
  } else {
    stroke(0, 255, 0);
  }
  updateMouse();
}
​
function updateMouse() {
  shape.x = mouseX;
  shape.y = mouseY;
  
  if(shape instanceof Rect) {
    shape.x -= r/2;
    shape.y -= r/2;
  }
    
  shape.show();
}
​
function mouseReleased() {
  if(sub) {
    q.subtract(shape);
  } else {
    q.add(shape); 
  }
  q.reconsile();
}
​
function keyReleased() {
  if(key === ' ') {
    changeBrush();
  }
  if(key === 'a') {
    sub = false;
  }
  if(key === 's') {
    sub = true;
  }
  if(key === '`') {
    debug = !debug;
  }
}
​
function changeBrush() {
  if(shape instanceof Rect) {
    shape = new Circle(mouseX, mouseY, r/2);
  } else if(shape === null || shape instanceof Circle) {
    shape = new Rect(mouseX, mouseY, r, r);
  }
}
​
class Quad {
  constructor(x, y, w, h, solid, data) {
    this.rect = new Rect(x, y, w, h);
    this.solid = solid;
    this.data = data;
    this.children = [];
  }
  
  atomic() {
    return this.rect.w <= MIN_QUAD_SIZE || this.rect.h <= MIN_QUAD_SIZE;
  }
  
  split() {
    if(this.atomic()) {
      return;
    }
    
    let nw = this.rect.w/2;
    let nh = this.rect.h/2;
    
    let x = this.rect.x;
    let y = this.rect.y;
    this.children.push(new Quad(x, y, nw, nh, this.solid, this.data));
    this.children.push(new Quad(x + nw, y, nw, nh, this.solid, this.data));
    this.children.push(new Quad(x, y + nh, nw, nh, this.solid, this.data));
    this.children.push(new Quad(x + nw, y + nh, nw, nh, this.solid, this.data));
  }
  
  show() {
    if(this.children.length) {
      for(let c of this.children) {
        c.show();
      }
    } else {
      
      noStroke();
      
      if(this.solid === SOLID) {
        fill(0);
        if(debug) {
          stroke(0, 0, 255, alpha);
        }
        
        this.rect.show();
      }
      
    }
  }
  
  hits(shape) {
    if(this.solid === EMPTY || !this.intersects(shape)) {
      return false;
    }
    if(this.solid === SOLID) {
      return true;
    }
    
    for(let c of this.children) {
      if(c.hits(shape)) {
        return true;
      }
    }
    return false;
  }
  
  intersects(shape) {
    if(this.children.length) {
      for(let c of this.children) {
        let q = c.intersects(shape);
        if(q) {
          return q;
        }
      }
    } else {
      if(this.rect.intersects(shape)) {
        return this;
      }
    }
  }
  
  inside(shape) {
    return this.rect.inside(shape);
  }
  
  reconsile() {
    if(!this.children.length) {
      return;
    }
    let add = 0;
    let mul = 1;
    let hasMixedChild = false;
    for(let c of this.children) {
      c.reconsile()
      if(c.solid === MIXED) {
        this.solid = MIXED;
        hasMixedChild = true;
      } else {
        add += c.solid;
        mul *= c.solid;
      }      
    }
    
    if(!hasMixedChild && add === 0 && mul === 0) {
      this.solid = EMPTY; 
      this.children = [];
    } else if (!hasMixedChild && add !== 0 && mul !== 0) {
      this.solid = SOLID
      this.children = [];
    } else {
      this.solid = MIXED
    }
  }
  
  fill(shape, type) {
    if(this.intersects(shape)) {
      if(this.solid === type || this.atomic() || this.inside(shape)) {
        this.children = [];
        this.solid = type;
        return;
      }
      if(!this.children.length) {
        this.split();
      }
      this.solid = MIXED;
      for(let c of this.children) {
        c.fill(shape, type);
      }
    }
  }
  
  subtract(shape) {
    // remove shape from solid
    this.fill(shape, EMPTY);
  }
  
  add(shape) {
    // add shape to solid
    this.fill(shape, SOLID);
  }
}
​
class Rect {
  constructor(x, y, w, h) {
    this.x = x;
    this.y = y;
    this.w = w;
    this.h = h;
  }
  
  show() {
    rect(this.x, this.y, this.w, this.h);
  }
  
  // check if this rect overlaps the shape
  intersects(shape) {
    if(shape instanceof p5.Vector) {
      return shape.x >= this.x &&
        shape.x < this.x + this.w &&
        shape.y >= this.y &&
        shape.y < this.y + this.h; 
    } else if(shape instanceof Rect) {
      return this.x + this.w >= shape.x &&
        this.x < shape.x + shape.w &&
        this.y + this.h >= shape.y &&
        this.y < shape.y + shape.h;
    } else if(shape instanceof Circle) {
      let x = shape.x;
      let y = shape.y;
​
      if(shape.x < this.x) {
        x = this.x;
      } else if(shape.x > this.x + this.w) {
        x = this.x + this.w;
      } 
      if(shape.y < this.y) {
        y = this.y;
      } else if(shape.y > this.y + this.h) {
        y = this.y + this.h;
      } 
​
      let dx = shape.x - x;
      let dy = shape.y - y;
      let d = sqrt((dx * dx) + (dy * dy));
​
      return d <= shape.r;
    }
    return false;
  }
​
  // check if this rectangle is completely inside shape
  inside(shape) {
    if(shape instanceof p5.Vector) {
      return this.w <= 1 && this.h <= 1 && this.intersects(shape);
    } else if(shape instanceof Rect) {
      let c1 = shape.intersects(createVector(this.x, this.y));
      let c2 = shape.intersects(createVector(this.x + this.w, this.y));
      let c3 = shape.intersects(createVector(this.x, this.y + this.h));
      let c4 = shape.intersects(createVector(this.x + this.w, this.y + this.h));
      return c1 && c2 && c3 && c4;
    } else if(shape instanceof Circle) {
      let c = createVector(shape.x, shape.y);
      let r = shape.r;
      
      let d1 = createVector(this.x, this.y).dist(c);
      let d2 = createVector(this.x + this.w, this.y).dist(c);
      let d3 = createVector(this.x, this.y + this.h).dist(c);
      let d4 = createVector(this.x + this.w, this.y + this.h).dist(c);
      
      return d1 <= r && d2 <= r && d3 <= r && d4 <= r;
    }
    return false;
  }
}
​
class Circle {
  constructor(x, y, r) {
    this.x = x;
    this.y = y;
    this.r = r;
  }
  
  show() {
    ellipse(this.x, this.y, this.r * 2, this.r * 2);
  }
}
​
class Bomb extends Circle {
  constructor(x, y) {
    super(x, y, 5);
    this.vx = random(-1, 1);
    this.vy = 0;
  }
  
  blast() {
    return new Circle(this.x, this.y, this.r * 5);
  }
  
  update() {
    this.vy += 0.05;
    
    this.x += this.vx;
    this.y += this.vy;
  }
  
  show() {
    fill(255, 0, 0);
    stroke(0);
    circle(this.x, this.y, this.r * 2);
  }
}
Cookies

Sketch Files

Console

Preview
