# 3D Flocking simulation with two species and octree optimisation

Hi, I’m trying to set up a flocking simulation with two species of boids and octree optimization.
My problem here is that I want the two species to run on different octrees, and I don’t really understand how to do that starting from my code:

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
}
``````

TreeItem, Cube and Octree classes

``````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) {
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)) {
}
}

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);
}

}
}
``````

Boid class

``````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;

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_;
}

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,
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){

diff.setMag(1/d); // Magnitude inversely proportional to the distance

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){

diff.setMag(1/d); // Magnitude inversely proportional to the distance

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);

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);

}

void update(){
//this.sc = map(position.z, 0, z_max, 1, 3);
velocity.limit(maxSpeed);
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);
}

}
``````

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);
}
}

}
}
``````

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 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++){
}
}

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();
}
``````

So, what I understand is that I should give octree as a “parameter” to the flock or (boid) class, so I could reference octree or octree2 respectively if I’m using the first flock or the second flock.

The problem here is that I’m not able to do it lol, I tried but if I add it in the flock class, also the boid class needs it, so I tried adding it to boid and I get a null pointer exception error…
I’m new to java/javascript so all this classes inheritance thing is something I still need to master.
Really don’t know, haaaaaalp me plz <3.

NB it’s the first time a write in a blog so if formatting is off let me know and I’ll fix it.
NB2 I’m Italian, so I’m sorry for the bad English.