Hiii, I’m trying to do a 3D flocking simulation with two types of boids and octree optimization.
I would like to have two octrees one for each flock in order to then insert an interaction between the two flocks as a method of the flock class (reference below).
So I set up a TreeItem, a Cube and an OcTree class:
class TreeItem{
float x;
float y;
float z;
Boid boid;
public TreeItem(Boid boid_){
this.x = boid_.position.x;
this.y = boid_.position.y;
this.z = boid_.position.z;
this.boid = boid_;
}
}
class Cube{
float x, y, z;
float w, h, d;
public Cube(float x_, float y_, float z_, float w_, float h_, float d_){
this.x = x_;
this.y = y_;
this.z = z_;
this.w = w_;
this.h = h_;
this.d = d_;
}
Boolean contains(TreeItem treeItem) {
return ( treeItem.x >= x - w && treeItem.x <= x + w &&
treeItem.y >= y - h && treeItem.y <= y + h &&
treeItem.z >= z - d && treeItem.z <= z + d );
}
Boolean intersects(Cube range) {
return !( range.x - range.w > x + w || range.x + range.w < x - w ||
range.y - range.h > y + h || range.y + range.h < y - h ||
range.z - range.d > z + d || range.z + range.d < z - d );
}
}
class OcTree {
int capacity;
boolean divided ;
ArrayList <TreeItem> treeItems;
Cube boundary;
OcTree NWT, NET, SET, SWT;
OcTree NWB, NEB, SEB, SWB;
OcTree(Cube boundary, int capacity) {
this.boundary = boundary;
this.capacity = capacity;
this.treeItems = new ArrayList <TreeItem>();
this.divided = false;
}
boolean insert(TreeItem treeItem) {
if (!this.boundary.contains(treeItem)) {
return false;
}
if (this.treeItems.size() < this.capacity) {
this.treeItems.add(treeItem);
return true;
} else {
if (!this.divided) {
this.subdivide();
}
// N = North, S = South, E = East, W = West, B = Bottom, T = Top
if (this.NWT.insert(treeItem)) {
return true;
} else if (this.NET.insert(treeItem)) {
return true;
} else if (this.SET.insert(treeItem)) {
return true;
} else if (this.SWT.insert(treeItem)) {
return true;
} else if (this.NWB.insert(treeItem)) {
return true;
} else if (this.NEB.insert(treeItem)) {
return true;
} else if (this.SEB.insert(treeItem)) {
return true;
} else if (this.SWB.insert(treeItem)) {
return true;
}
}
return false;
}
void subdivide() {
float x = this.boundary.x;
float y = this.boundary.y;
float z = this.boundary.z;
float w = this.boundary.w / 2;
float h = this.boundary.h / 2;
float d = this.boundary.d / 2;
Cube NWTBoundary = new Cube(x - w, y - h, z - d, w, h, d);
Cube NETBoundary = new Cube(x + w, y - h, z - d, w, h, d);
Cube SETBoundary = new Cube(x + w, y + h, z - d, w, h, d);
Cube SWTBoundary = new Cube(x - w, y + h, z - d, w, h, d);
Cube NWBBoundary = new Cube(x - w, y - h, z + d, w, h, d);
Cube NEBBoundary = new Cube(x + w, y - h, z + d, w, h, d);
Cube SEBBoundary = new Cube(x + w, y + h, z + d, w, h, d);
Cube SWBBoundary = new Cube(x - w, y + h, z + d, w, h, d);
this.NWT = new OcTree(NWTBoundary, this.capacity);
this.NET = new OcTree(NETBoundary, this.capacity);
this.SET = new OcTree(SETBoundary, this.capacity);
this.SWT = new OcTree(SWTBoundary, this.capacity);
this.NWB = new OcTree(NWBBoundary, this.capacity);
this.NEB = new OcTree(NEBBoundary, this.capacity);
this.SEB = new OcTree(SEBBoundary, this.capacity);
this.SWB = new OcTree(SWBBoundary, this.capacity);
this.divided = true;
}
ArrayList<TreeItem> query(Cube range, ArrayList<TreeItem> found) {
if (found == null) found = new ArrayList<TreeItem>();
if (!this.boundary.intersects(range)) {
return found;
} else {
for (TreeItem treeItem : this.treeItems) {
if (range.contains(treeItem)) {
found.add(treeItem);
}
}
if (this.divided) {
this.NWT.query(range, found);
this.NET.query(range, found);
this.SET.query(range, found);
this.SWT.query(range, found);
this.NWB.query(range, found);
this.NEB.query(range, found);
this.SEB.query(range, found);
this.SWB.query(range, found);
}
}
return found;
}
void show(color col, int strokeW){
pushMatrix();
strokeWeight(strokeW);
stroke(col, 10);
noFill();
translate(this.boundary.x, this.boundary.y, this.boundary.z);
box(this.boundary.w * 2, this.boundary.h * 2, this.boundary.d * 2);
popMatrix();
if (this.divided){
this.NWT.show(col, strokeW);
this.NET.show(col, strokeW);
this.SET.show(col, strokeW);
this.SWT.show(col, strokeW);
this.NWB.show(col, strokeW);
this.NEB.show(col, strokeW);
this.SEB.show(col, strokeW);
this.SWB.show(col, strokeW);
}
}
}
Then the boid class makes use of the octree in the behaviour method:
class Boid{
PVector position;
PVector velocity;
PVector acceleration;
float x, y, z;
float maxForce = 0.5;
float maxSpeed = 4;
float flap = 0;
float sc = 3;
color col;
int perceptionRadius;
Boid(color col_, int perceptionRadius_){
this.position = new PVector(random(width),
random(height), random(z_min, z_max));
this.x = this.position.x;
this.y = this.position.y;
this.z = this.position.z;
this.velocity = PVector.random3D().setMag(random(2, 4));
this.acceleration = new PVector(0, 0, 0);
this.col = col_;
this.perceptionRadius = perceptionRadius_;
}
ArrayList<PVector> behaviour(ArrayList<Boid> boids){
ArrayList<PVector> steering = new ArrayList<PVector>();
float maxAngle = PI ;
int tot = 0;
PVector alignSteering = new PVector();
PVector cohesionSteering = new PVector();
PVector separationSteering = new PVector();
if (useOcTree == true) {
Cube range = new Cube(this.position.x, this.position.y,
this.position.z, perceptionRadius, perceptionRadius, perceptionRadius);
if (showBox){
if (this == boids.get(0)){
pushMatrix();
strokeWeight(1);
stroke(255, 255, 255);
noFill();
translate(range.x, range.y, range.z);
box(range.w * 2, range.h * 2, range.d * 2);
popMatrix();
}
}
ArrayList<TreeItem> maybeNeighbors = octree.query(range, null);
for (TreeItem otherr : maybeNeighbors){
Boid other = otherr.boid;
PVector diff = PVector.sub(this.position, other.position);
float d = diff.mag();
float theta = PVector.angleBetween(position, PVector.sub(this.position, other.position));
if (other != this && d < perceptionRadius && theta < maxAngle){
alignSteering.add(other.velocity);
cohesionSteering.add(other.position);
diff.setMag(1/d); // Magnitude inversely proportional to the distance
separationSteering.add(diff);
tot++;
}
}
}
if (useOcTree == false){
for (Boid other : boids){
PVector diff = PVector.sub(this.position, other.position);
float d = diff.mag();
float theta = PVector.angleBetween(position, PVector.sub(this.position, other.position));
if (other != this && d < perceptionRadius && theta < maxAngle){
alignSteering.add(other.velocity);
cohesionSteering.add(other.position);
diff.setMag(1/d); // Magnitude inversely proportional to the distance
separationSteering.add(diff);
tot++;
}
}
}
if (tot > 0){
alignSteering.div(tot);
alignSteering.setMag(this.maxSpeed);
alignSteering.sub(this.velocity);
alignSteering.limit(this.maxForce);
cohesionSteering.div(tot);
cohesionSteering.sub(this.position);
cohesionSteering.setMag(this.maxSpeed);
cohesionSteering.sub(this.velocity);
cohesionSteering.limit(this.maxForce);
separationSteering.div(tot);
separationSteering.setMag(this.maxSpeed);
separationSteering.sub(this.velocity);
separationSteering.limit(this.maxForce);
}
separationSteering.mult(2);
alignSteering.mult(2);
cohesionSteering.mult(1.5);
steering.add(alignSteering);
steering.add(cohesionSteering);
steering.add(separationSteering);
return steering;
}
void flock(ArrayList<Boid> boids){
ArrayList<PVector> steering = behaviour(boids);
PVector alignment = steering.get(0);
PVector cohesion = steering.get(1);
PVector separation = steering.get(2);
this.acceleration.add(alignment); // steering force !!
this.acceleration.add(cohesion); // steering force !!
this.acceleration.add(separation); // steering force !!
}
void update(){
//this.sc = map(position.z, 0, z_max, 1, 3);
velocity.add(acceleration);
velocity.limit(maxSpeed);
position.add(velocity);
acceleration.mult(0);
}
void edges() {
if (position.x > width) {
position.x = 0;
} else if (position.x < 0) {
position.x = width;
}
if (position.y > height) {
position.y = 0;
} else if (position.y < 0) {
position.y = height;
}
if(position.z > z_max) position.z = z_min;
if(position.z < z_min) position.z = z_max;
}
void show(ArrayList<Boid> boids){
pushMatrix();
translate(position.x, position.y, position.z);
rotateY(atan2(-velocity.z, velocity.x));
rotateZ(asin(velocity.y/velocity.mag()));
noFill();
noStroke();
strokeWeight(1);
if (this == boids.get(0)){
stroke(255);
fill(255);
}
else{
stroke(col);
fill(col);
}
//draw bird
beginShape(TRIANGLES);
vertex(3*sc, 0, 0);
vertex(-3*sc, 2*sc, 0);
vertex(-3*sc, -2*sc,0);
vertex(3*sc,0,0);
vertex(-3*sc,2*sc,0);
vertex(-3*sc,0,2*sc);
vertex(3*sc,0,0);
vertex(-3*sc,0,2*sc);
vertex(-3*sc,-2*sc,0);
vertex(-3*sc,0,2*sc);
vertex(-3*sc,2*sc,0);
vertex(-3*sc,-2*sc,0);
endShape();
popMatrix();
}
PVector avoid(PVector target, boolean weight){
PVector steer = new PVector();
steer.set(PVector.sub(position, target));
if(weight)
steer.mult(1/sq(PVector.dist(position, target)));
steer.limit(maxForce);
return steer;
}
void run(ArrayList<Boid> boids) {
if(avoidWalls)
{
acceleration.add(PVector.mult(avoid(new PVector(position.x, height, position.z), true), 5));
acceleration.add(PVector.mult(avoid(new PVector(position.x, 0, position.z), true), 5));
acceleration.add(PVector.mult(avoid(new PVector(width, position.y, position.z), true), 5));
acceleration.add(PVector.mult(avoid(new PVector(0, position.y, position.z), true), 5));
acceleration.add(PVector.mult(avoid(new PVector(position.x, position.y, z_min), true), 5));
acceleration.add(PVector.mult(avoid(new PVector(position.x, position.y, z_max), true), 5));
}
flock(boids);
update();
edges();
show(boids);
}
}
I think here is the problem, the octree the behaviour method uses is not linked to the boid so it uses always the octree of the first flock even for the boids of the second flock.
The flock class:
class Flock {
ArrayList<Boid> boids; // An ArrayList for all the boids
Flock() {
this.boids = new ArrayList<Boid>(); // Initialize the ArrayList
}
void run() {
octree = new OcTree(bound, 2);
for (Boid b : boids) {
Boid tempBoid = b;
octree.insert(new TreeItem(tempBoid));
tempBoid.run(flock.boids);
}
}
void addBoid(Boid b) {
boids.add(b);
}
}
Various functions:
void keyPressed() {
if (key == 'o' || key == 'O'){
useOcTree = !useOcTree;
if (useOcTree == false) showOctree = false;
}
if (key == 's' || key == 'S'){
showOctree = !showOctree;
}
if (key == 'a' || key == 'A'){
show2 = !show2;
}
}
void get_box(){
noFill();
strokeWeight(1);
stroke(255);
line(0, 0, z_min, 0, height, z_min);
line(0, 0, z_max, 0, height, z_max);
line(0, 0, z_min, width, 0, z_min);
line(0, 0, z_max, width, 0, z_max);
line(width, 0, z_min, width, height, z_min);
line(width, 0, z_max, width, height, z_max);
line(0, height, z_min, width, height, z_min);
line(0, height, z_max, width, height, z_max);
line(0, 0, z_min, 0, 0, z_max);
line(0, height, z_min, 0, height, z_max);
line(width, 0, z_min, width, 0, z_max);
line(width, height, z_min, width, height, z_max);
}
void calculateAxis( float length )
{
// Store the screen positions for the X, Y, Z and origin
axisXHud.set( screenX(length,0,0), screenY(length,0,0), 0 );
axisYHud.set( screenX(0,length,0), screenY(0,length,0), 0 );
axisZHud.set( screenX(0,0,length), screenY(0,0,length), 0 );
axisOrgHud.set( screenX(0,0,0), screenY(0,0,0), 0 );
}
// ------------------------------------------------------------------------ //
void drawAxis( float weight )
{
pushStyle(); // Store the current style information
strokeWeight( weight ); // Line width
stroke( 255, 0, 0 ); // X axis color (Red)
line( axisOrgHud.x, axisOrgHud.y, axisXHud.x, axisXHud.y );
stroke( 0, 255, 0 );
line( axisOrgHud.x, axisOrgHud.y, axisYHud.x, axisYHud.y );
stroke( 0, 0, 255 );
line( axisOrgHud.x, axisOrgHud.y, axisZHud.x, axisZHud.y );
fill(255); // Text color
textFont( axisLabelFont ); // Set the text font
text( "X", axisXHud.x, axisXHud.y );
text( "Y", axisYHud.x, axisYHud.y );
text( "Z", axisZHud.x, axisZHud.y );
popStyle(); // Recall the previously stored style information
}
And here’s the main:
import peasy.*;
import peasy.org.apache.commons.math.geometry.*;
PeasyCam cam;
CameraState state;
PFont axisLabelFont;
PVector axisXHud, axisYHud, axisZHud, axisOrgHud;
import com.hamoid.*;
VideoExport videoExport;
int saveCount = 1;
// various verbs
boolean useOcTree = true, showBox = true, showOctree = true, show2 = true;
boolean avoidWalls = true, smoothEdges = true;
int z_min = 0, z_max = 800;
int perception_radius = 50, perception_radius2 = 50;
int boyz_num = 50;
Flock flock, flock2;
OcTree octree, octree2;
Cube bound;
void setup() {
size(800, 800, P3D);
// camera setup
cam = new PeasyCam(this, 300);
Rotation rot = new Rotation(RotationOrder.XYZ, PI, PI, 0);
Vector3D center = new Vector3D(width/2, height/2, z_min);
CameraState state = new CameraState(rot, center, 1500);
cam.setState(state, 1500);
state = cam.getState();
// axis setup
axisLabelFont = createFont( "Arial", 14 );
axisXHud = new PVector();
axisYHud = new PVector();
axisZHud = new PVector();
axisOrgHud = new PVector();
// bounds of octrees
bound = new Cube(width/2, height/2, z_max/2, width/2, height/2, z_max/2);
// flocks initialization
flock = new Flock();
flock2 = new Flock();
for (int i = 0; i < boyz_num; i++){
flock.addBoid( new Boid(#EA4C4C, perception_radius) );
flock2.addBoid( new Boid(#BEAFD6, perception_radius2) );
}
}
void draw() {
background(27);
directionalLight(150, 150, 150, 0, 1, 0);
ambientLight(150, 150, 150);
// BOX
get_box();
flock.run();
flock2.run();
if (showOctree){
octree.show(#EA4C4C, 1);
if (show2){
// uncomment this to get the error that brokes the code, this is actually the problem,
// i would like flock2 to run on octree2 but it runs on octree and thus the octree2
// object never gets filled with the second kind (color) of boids
// octree2.show(#BEAFD6, 1);
}
}
// display axis
calculateAxis(500);
cam.beginHUD();
drawAxis(3);
cam.endHUD();
}
I tried inserting the octree object both in the flock and boid classes but I get a null pointer exception error since evidently the octree object results empty, here’s one of the trial:
new boid class with octree as input
class Boid{
PVector position;
PVector velocity;
PVector acceleration;
float x, y, z;
float maxForce = 0.5;
float maxSpeed = 4;
float flap = 0;
float sc = 3;
color col;
int perceptionRadius;
OcTree octree;
Boid(color col_, int perceptionRadius_, OcTree octree_){
this.position = new PVector(random(width),
random(height), random(z_min, z_max));
this.x = this.position.x;
this.y = this.position.y;
this.z = this.position.z;
this.velocity = PVector.random3D().setMag(random(2, 4));
this.acceleration = new PVector(0, 0, 0);
this.col = col_;
this.perceptionRadius = perceptionRadius_;
this.octree = octree_;
}
ArrayList<PVector> behaviour(ArrayList<Boid> boids){
ArrayList<PVector> steering = new ArrayList<PVector>();
float maxAngle = PI ;
int tot = 0;
PVector alignSteering = new PVector();
PVector cohesionSteering = new PVector();
PVector separationSteering = new PVector();
if (useOcTree == true) {
Cube range = new Cube(this.position.x, this.position.y,
this.position.z, perceptionRadius, perceptionRadius, perceptionRadius);
if (showBox){
if (this == boids.get(0)){
pushMatrix();
strokeWeight(1);
stroke(255, 255, 255);
noFill();
translate(range.x, range.y, range.z);
box(range.w * 2, range.h * 2, range.d * 2);
popMatrix();
}
}
ArrayList<TreeItem> maybeNeighbors = octree.query(range, null);
for (TreeItem otherr : maybeNeighbors){
Boid other = otherr.boid;
PVector diff = PVector.sub(this.position, other.position);
float d = diff.mag();
float theta = PVector.angleBetween(position, PVector.sub(this.position, other.position));
if (other != this && d < perceptionRadius && theta < maxAngle){
alignSteering.add(other.velocity);
cohesionSteering.add(other.position);
diff.setMag(1/d); // Magnitude inversely proportional to the distance
separationSteering.add(diff);
tot++;
}
}
}
if (useOcTree == false){
for (Boid other : boids){
PVector diff = PVector.sub(this.position, other.position);
float d = diff.mag();
float theta = PVector.angleBetween(position, PVector.sub(this.position, other.position));
if (other != this && d < perceptionRadius && theta < maxAngle){
alignSteering.add(other.velocity);
cohesionSteering.add(other.position);
diff.setMag(1/d); // Magnitude inversely proportional to the distance
separationSteering.add(diff);
tot++;
}
}
}
if (tot > 0){
alignSteering.div(tot);
alignSteering.setMag(this.maxSpeed);
alignSteering.sub(this.velocity);
alignSteering.limit(this.maxForce);
cohesionSteering.div(tot);
cohesionSteering.sub(this.position);
cohesionSteering.setMag(this.maxSpeed);
cohesionSteering.sub(this.velocity);
cohesionSteering.limit(this.maxForce);
separationSteering.div(tot);
separationSteering.setMag(this.maxSpeed);
separationSteering.sub(this.velocity);
separationSteering.limit(this.maxForce);
}
separationSteering.mult(2);
alignSteering.mult(2);
cohesionSteering.mult(1.5);
steering.add(alignSteering);
steering.add(cohesionSteering);
steering.add(separationSteering);
return steering;
}
void flock(ArrayList<Boid> boids){
ArrayList<PVector> steering = behaviour(boids);
PVector alignment = steering.get(0);
PVector cohesion = steering.get(1);
PVector separation = steering.get(2);
this.acceleration.add(alignment); // steering force !!
this.acceleration.add(cohesion); // steering force !!
this.acceleration.add(separation); // steering force !!
}
void update(){
//this.sc = map(position.z, 0, z_max, 1, 3);
velocity.add(acceleration);
velocity.limit(maxSpeed);
position.add(velocity);
acceleration.mult(0);
}
void edges() {
if (position.x > width) {
position.x = 0;
} else if (position.x < 0) {
position.x = width;
}
if (position.y > height) {
position.y = 0;
} else if (position.y < 0) {
position.y = height;
}
if(position.z > z_max) position.z = z_min;
if(position.z < z_min) position.z = z_max;
}
void show(ArrayList<Boid> boids){
pushMatrix();
translate(position.x, position.y, position.z);
rotateY(atan2(-velocity.z, velocity.x));
rotateZ(asin(velocity.y/velocity.mag()));
noFill();
noStroke();
strokeWeight(1);
if (this == boids.get(0)){
stroke(255);
fill(255);
}
else{
stroke(col);
fill(col);
}
//draw bird
beginShape(TRIANGLES);
vertex(3*sc, 0, 0);
vertex(-3*sc, 2*sc, 0);
vertex(-3*sc, -2*sc,0);
vertex(3*sc,0,0);
vertex(-3*sc,2*sc,0);
vertex(-3*sc,0,2*sc);
vertex(3*sc,0,0);
vertex(-3*sc,0,2*sc);
vertex(-3*sc,-2*sc,0);
vertex(-3*sc,0,2*sc);
vertex(-3*sc,2*sc,0);
vertex(-3*sc,-2*sc,0);
endShape();
popMatrix();
}
PVector avoid(PVector target, boolean weight){
PVector steer = new PVector();
steer.set(PVector.sub(position, target));
if(weight)
steer.mult(1/sq(PVector.dist(position, target)));
steer.limit(maxForce);
return steer;
}
void run(ArrayList<Boid> boids) {
if(avoidWalls)
{
acceleration.add(PVector.mult(avoid(new PVector(position.x, height, position.z), true), 5));
acceleration.add(PVector.mult(avoid(new PVector(position.x, 0, position.z), true), 5));
acceleration.add(PVector.mult(avoid(new PVector(width, position.y, position.z), true), 5));
acceleration.add(PVector.mult(avoid(new PVector(0, position.y, position.z), true), 5));
acceleration.add(PVector.mult(avoid(new PVector(position.x, position.y, z_min), true), 5));
acceleration.add(PVector.mult(avoid(new PVector(position.x, position.y, z_max), true), 5));
}
flock(boids);
update();
edges();
show(boids);
}
}
and new main:
import peasy.*;
import peasy.org.apache.commons.math.geometry.*;
PeasyCam cam;
CameraState state;
PFont axisLabelFont;
PVector axisXHud, axisYHud, axisZHud, axisOrgHud;
import com.hamoid.*;
VideoExport videoExport;
int saveCount = 1;
// various verbs
boolean useOcTree = true, showBox = true, showOctree = true, show2 = true;
boolean avoidWalls = true, smoothEdges = true;
int z_min = 0, z_max = 800;
int perception_radius = 50, perception_radius2 = 50;
int boyz_num = 50;
Flock flock, flock2;
OcTree octree, octree2;
Cube bound;
void setup() {
size(800, 800, P3D);
// camera setup
cam = new PeasyCam(this, 300);
Rotation rot = new Rotation(RotationOrder.XYZ, PI, PI, 0);
Vector3D center = new Vector3D(width/2, height/2, z_min);
CameraState state = new CameraState(rot, center, 1500);
cam.setState(state, 1500);
state = cam.getState();
// axis setup
axisLabelFont = createFont( "Arial", 14 );
axisXHud = new PVector();
axisYHud = new PVector();
axisZHud = new PVector();
axisOrgHud = new PVector();
// bounds of octrees
bound = new Cube(width/2, height/2, z_max/2, width/2, height/2, z_max/2);
// flocks initialization
flock = new Flock();
flock2 = new Flock();
for (int i = 0; i < boyz_num; i++){
flock.addBoid( new Boid(#EA4C4C, perception_radius, octree) );
flock2.addBoid( new Boid(#BEAFD6, perception_radius2, octree2) );
}
}
void draw() {
background(27);
directionalLight(150, 150, 150, 0, 1, 0);
ambientLight(150, 150, 150);
// BOX
get_box();
flock.run();
flock2.run();
if (showOctree){
octree.show(#EA4C4C, 1);
if (show2){
// uncomment this to get the error that brokes the code, this is actually the problem,
// i would like flock2 to run on octree2 but it runs on octree and thus the octree2
// object never gets filled with the second kind (color) of boids
// octree2.show(#BEAFD6, 1);
}
}
// display axis
calculateAxis(500);
cam.beginHUD();
drawAxis(3);
cam.endHUD();
}
the null pointer exception pops out at: “ArrayList maybeNeighbors = octree.query(range, null);”
I’m pretty new to java/javascript so any help is appreciated!