quadTree

// a quadtree tracking a Shiffman mover object.

// the white ellipse is part of the vehicle

// the red ellipse is part of the quadtree and indicates the

// location of  a quadrant size of less than 2 by 2

// vector, Reynolds' seeking/arriving behaviour, particle system, quadtree

​

Vehicle v;

QuadTree QT;

​

void setup() {

  size(700, 700);

  v = new Vehicle();

  QT = new QuadTree();

}

​

void draw() {

  background(#320D8B);

  v.seek();

  QT.insert(0, 0, width, v.pos.x, v.pos.y);

}

class Trail {

  ArrayList<Particle> particles;

  PVector pos;

  Trail(PVector location) {

    pos = location.get();

    particles = new ArrayList<Particle>();

  }

​

    void run() {

      particles.add(new Particle(pos));

      for (int i = particles.size()-1; i >= 0; i--) {

      Particle p = particles.get(i);

      p.run();

      if (p.isDead()) {

        particles.remove(i);

      }

    }  

    }

  }

​

class Particle {

  PVector pos;

  PVector vel;

  float lifespan, diam;

​

  Particle(PVector location) {

    vel = new PVector(random(-0.03, 0.03), random(-0.03, 0.03));

    pos = location.get();

    lifespan = 255.0;

    diam = 2;

  }

​

  void run() {

    move();

    display();

  }

​

  void move() {

    pos.add(vel);

    lifespan -= .5;

    diam += 0.05;

  }

​

  void display() {

    //noStroke();

    stroke(#320D8B, lifespan);

    strokeWeight(.5);

    fill(255,lifespan);

    ellipse(pos.x,pos.y,diam,diam);

  }

  boolean isDead() {

    if (lifespan < 0.0) {

      return true;

    } else {

      return false;

    }

  }

}

​

​

class QuadTree {

  int which;

​

  // quadrant top left xy, quadrant width/height,  xy of vehicle being tracked

  void insert(float x, float y, float sze, float vX, float vY) {

    if (sze > 1) {

​

      which = whichQuad(vX, vY, x, y, sze);

      noFill();

      stroke(255, 0, 0);

      strokeWeight(1);

​

      if (sze > 20) {

        line(x + sze/2, y, x+sze/2, y + sze);  // vertical

        line(x, y + sze/2, x + sze, y +sze/2); // horizontal

      }

​

      if (sze < 2) {

        fill(255, 0, 0);

        stroke(255, 0, 0);

        strokeWeight(1);

        ellipseMode(CENTER);

        ellipse(x, y, 2, 2);

​

        //line(x, y-15, x, y +15); // vertical

        //line(x-15, y, x+15, y ); // horizontal

      }

​

      // could use switch here

      if (which == 1)insert(x, y, sze/2, vX, vY);                       // tl

      else if (which == 2)insert(x + sze/2, y, sze/2, vX, vY);          // tr

      else if (which == 3) insert(x, y + sze/2, sze/2, vX, vY);         // bl

      else if (which == 4)insert(x + sze/2, y  + sze/2, sze/2, vX, vY); // br

      else println("ERROR");

    }

  }

​

​

  // vehicle xy, current quadrant top left xy, current quadrant width/height

  int whichQuad(float vx, float vy, float tlx, float tly, float  s) {

    if ( vx <= tlx + s/2 && vy <= tly + s/2) return 1;      // tl

    else if ( vx >= tlx + s/2 && vy <= tly + s/2)return 2;  // tr

    else if ( vx <= tlx + s/2 && vy >= tly + s/2)return 3 ; // bl

    else if ( vx >= tlx + s/2 && vy >= tly + s/2)return 4;  // br

    return 5;

  }

}

​

class Vehicle {

  Trail trail;

  PVector pos, accel, vel, follow;

  float maxSpeed, maxForce, angle, dist, m;

  int s ; 

​

​

  Vehicle() {

    pos = new PVector(width/2, height/2);

    vel = new PVector(0, 0);

    accel = new PVector(0, 0);

    follow = new PVector(0, 0);

    trail = new Trail(pos);

    maxSpeed = 3;

    maxForce = 0.05;

    s = 10;

  } 

​

  void applyForce(PVector f) {

    accel.add(f);

  }

​

  //   dxdy   =  mouse position -  current position

  void seek() {

    follow.set(mouseX, mouseY);

    PVector desired = PVector.sub(follow, pos);  

    dist = desired.mag(); //measure how far away we are

    desired.normalize();  

​

    if (dist < 100) {

      m = map(dist, 0, 100, 0, maxSpeed);

      desired.mult(m);

    } else {

      desired.mult(maxSpeed);

    }

​

    // steer = desired velocity  - current velocity  

    PVector steer = PVector.sub(desired, vel);

    steer.limit(maxForce);  // limit to only a  gradual change in heading

​

    applyForce(steer);

    update(); 

    trail.run();

    display();

  }

​

  void update() {

    vel.add(accel);

    pos.add(vel);

    trail.pos.set(pos);

    accel.mult(0);

  }

​

  void display() {

    angle = vel.heading2D();

    stroke(255);

    fill(#320D8B);

    strokeWeight(2);

    pushMatrix();

    translate(pos.x, pos.y);

    rotate(angle);

    beginShape();

    vertex(-s, -s);

    vertex(-s, s);

    vertex(s*3, 0);

    endShape(CLOSE);

    ellipseMode(CENTER);

    noFill();

    ellipse(0,0,20,20);

    popMatrix();

  }

}

​

​

​