# 3D flocking simulation with two types of boids and octree optimization

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

}
}
``````

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;

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

}
``````

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

}
}
``````

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

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

}
``````

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

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!

Hi @m.codeeee , Fascinating stuff, I think I’ve assembled the 4 pieces of your sketch, but it wants peasy and install library is failing for me (Could not find a library in the downloaded file). Does it run correctly with just one flock? Looking at your comment, do you just need a var each boid to say which octree it lives in? (do boids live in octrees - haha).

Hiii @RichardDL, peasycam can be installed directly in Processing going to add mode and then clicking on the libraries a searching for it. I think you can also download it here peasycam and insert it in the processing folder.

Anyway, yeah boids need to live in octrees.
I think I solved the problem, let me update my situation:

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;
float xMin, xMax, yMin, yMax, zMin, zMax;

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_;
this.xMin = x - w;
this.xMax = x + w;
this.yMin = y - h;
this.yMax = y + h;
this.zMin = z - d;
this.zMax = z + 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);
}
/*
for (TreeItem p : treeItems){
stroke(255);
strokeWeight(10);
point(p.x,p.y, p.z );
}*/
}

}
``````

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;
OcTree octree;

Boid(color col_, int perceptionRadius_, OcTree octree_){
this.octree = octree_;
this.position = new PVector(random(octree.boundary.xMin, octree.boundary.xMax),
random(octree.boundary.yMin, octree.boundary.yMax),
random(octree.boundary.zMin, octree.boundary.zMax) );
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();
//PVector interSeparationSteering = 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 > octree.boundary.xMax) {
position.x = octree.boundary.xMin;
} else if (position.x < octree.boundary.xMin) {
position.x = octree.boundary.xMax;
}
if (position.y > octree.boundary.yMax) {
position.y = octree.boundary.yMin;
} else if (position.y < octree.boundary.yMin) {
position.y = octree.boundary.yMax;
}
if (position.z > octree.boundary.zMax) {
position.z = octree.boundary.zMin;
} else if (position.z < octree.boundary.zMin) {
position.z = octree.boundary.zMax;
}
}

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); //, map(position.z, z_min, z_max, 0, 255));

fill(col); //, map(position.z, z_min, z_max, 0, 255));
}
//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(2*sc,0,0);
vertex(-1*sc,0,0);
vertex(-1*sc,-8*sc, flap);

vertex(2*sc,0,0);
vertex(-1*sc,0,0);
vertex(-1*sc,8*sc, flap);
*/

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(); //creates vector for steering
steer.set(PVector.sub(position, target)); //steering vector points away from target
if(weight)
steer.mult(1/sq(PVector.dist(position, target)));
steer.limit(maxForce); //limits the steering force to maxSteerForce
return steer;
}

void run(ArrayList<Boid> boids, OcTree octree_, boolean choicee) {
if (choicee)  {
octree = octree_;
}

if(avoidWalls)
{
acceleration.add(PVector.mult(avoid(new PVector(position.x, octree.boundary.yMax, position.z), true), 5));
acceleration.add(PVector.mult(avoid(new PVector(position.x, octree.boundary.yMin, position.z), true), 5));
acceleration.add(PVector.mult(avoid(new PVector(octree.boundary.xMax, position.y, position.z), true), 5));
acceleration.add(PVector.mult(avoid(new PVector(octree.boundary.xMin, position.y, position.z), true), 5));
acceleration.add(PVector.mult(avoid(new PVector(position.x, position.y, octree.boundary.zMin), true), 5));
acceleration.add(PVector.mult(avoid(new PVector(position.x, position.y, octree.boundary.zMax), true), 5));
}

flock(boids);
update();
edges();
show(boids);
}

}
``````

flock class:

``````class Flock {
ArrayList<Boid> boids; // An ArrayList for all the boids
OcTree octree;
color col;
boolean choicee;

Flock(color col_, int perceptionRadius_, OcTree octree_, boolean choice_) {
this.boids = new ArrayList<Boid>(); // Initialize the ArrayList
this.octree = octree_;
this.col = col_;
this.choicee = choice_;

for (int i = 0; i < boyz_num; i++){
}
}

void run() {
this.octree = new OcTree(this.octree.boundary, capacity);
for (Boid b : boids) {
octree.insert(new TreeItem(b));
}
if (octreeShow)  octree.show(boids.get(0).col, 1);

for (Boid b : boids) {
b.run(this.boids, octree, choicee);

}

}

}
``````

various functions:

``````// verb controls
void keyPressed() {

if (key == 'o' || key == 'O'){
useOcTree = !useOcTree;
if (octreeShow == false) octreeShow = false;
}

if (key == 's' || key == 'S'){
octreeShow = !octreeShow;
}

if (key == 'a' || key == 'A'){
show2 = !show2;
}
}

// dispaly bounds of the system
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);
}

// Axis code
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 finally 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;

// verbs
boolean useOcTree = true, showBox = true, octreeShow = true, show2 = true;
boolean avoidWalls = false;
boolean choice = true;
// parameters
int z_min = 0, z_max = 800;
int boyz_num = 1000;

// inizialization
Flock flock1, flock2;
OcTree octree1, octree2;
Cube bound1, bound2;

int capacity = 2;

void setup() {
size(800, 800, P3D);
background(27);

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

// bound of the octrees
bound1 = new Cube(width/2, height/2, z_max/2, width/2, height/2, z_max/2);
bound2 = new Cube(width/2, height/2, z_max/2, width/2, height/2, z_max/2);
//bound2 = new Cube(2*width, height/2, z_max/2, width/2, height/2, z_max/2);

// flock initialization
octree1 = new OcTree(bound1, capacity);
octree2 = new OcTree(bound2, capacity);

flock1 = new Flock(#EA4C4C, perceptionRadius, octree1, choice);
flock2 = new Flock(#BEAFD6, perceptionRadius2, octree2, choice);
}

void draw() {

background(27);
directionalLight(150, 150, 150, 0, 1, 0);
ambientLight(150, 150, 150);

// dispaly bounds of the system
get_box();

useOcTree = true;
flock1.run();
//if (showOctree) octree1.show(#EA4C4C, 1);

//useOcTree = false;
flock2.run();

// show axes
calculateAxis(500);
cam.beginHUD();
drawAxis(3);
cam.endHUD();
}
``````

With this code I think everything I now working, but it could be much cleaner in the octree dependencies of the boid, in fact the reaaaally relevant part in the octree dependence is the

``````if (choicee)  {
octree = octree_;
}
``````

in the run method in the Boid class, without that (set choice=false in main) I think everything stops working correctly.

My problem now is how to let these flocks interact with each other, I thought I could give to the boid object also the “other octree” , that is the octree of the other flock and setup an interSeparationSteering which is computed taking othermaybeNeighbors = otherOctree(range, null).
In that way with maybeNeighbors one computes all the intra-octree interactions and with othermaybeNeighbors one computes all the inter-octree interactions.

I hope this is clear, it’s pretty contorted I know lol.

PS.
If you want to run this I advice setting octreeShow to false (you can toggle it with the “s” key) in order to get a higher frame rate.

PPS.
I nice effect is obtained by fixing avoidWalls = true

I tried it on another PC, Peasy installed there (whatever). (needs Video Export library as well.) Now it runs it’s fascinating. Much more interesting than the 2D one in the examples. As I watch it I can see a few small groups of a few birds, that seem to be following each other, not big flocks. Is that what you expect? I wondered if you draw the far-away (smaller) birds first, so the bigger ones always fly between them and the observer. Tried to see that but couldn’t be sure either way.

can somebody post the entire version in one go

Hiii, yeah it’s much more fascinating than the 2D case, I think big flocks can be obtained by playing with the multipliers of the various steering forces or with the perception radius!
I could modulate the size of the boids by a mapping of their z- position if that is what you mean.

The entire version now contains obstacle avoidance in a dumb way I think lol but here it is:

``````
// Flocking simulation
// v 0.3
// mcodeeee 2022-05-26
// flocking simulation with octree optimization and object avoidance

class Flock {
ArrayList<Boid> boids;
color col;

this.col = col_;
this.boids = new ArrayList<Boid>();
// BOIDS INITIALIZATION
for (int i = 0; i < boyz_num; i++){
}
}

void run(OcTree octree_, OcTree otherOctree_) {
// UPDATE OCTREE
OcTree octree = octree_;
OcTree otherOctree = otherOctree_;

if (octreeShow) octree.show(col, 1);

// UPDATE BOIDS
for (Boid b : boids) {
b.run(octree, otherOctree);
}
}
}

class ObstacleTreeItem{
float x;
float y;
float z;
public ObstacleTreeItem(float x0, float y0, float z0, float r, float r1 , float theta, float phi){
// sphere obstacle
this.x = x0 + r*sin(theta)*cos(phi);
this.y = y0 + r*sin(theta)*sin(phi);
this.z = z0 + r*cos(theta);

// torus obstacle
/*
this.x = x0 + (r1 + r * cos(theta)) * cos(phi) ;
this.y = y0 + (r1 + r * cos(theta)) * sin(phi) ;
this.z = z0 + r * sin(theta);
*/
}
}

class ObstacleCube{
float x, y, z;
float w, h, d;
float xMin, xMax, yMin, yMax, zMin, zMax;

public ObstacleCube(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_;
this.xMin = x - w;
this.xMax = x + w;
this.yMin = y - h;
this.yMax = y + h;
this.zMin = z - d;
this.zMax = z + d;
}

Boolean obstacleContains(ObstacleTreeItem obstacleTreeItem) {
return ( obstacleTreeItem.x >= x - w && obstacleTreeItem.x <= x + w &&
obstacleTreeItem.y >= y - h && obstacleTreeItem.y <= y + h &&
obstacleTreeItem.z >= z - d && obstacleTreeItem.z <= z + d   );
}

Boolean obstacleIntersects(ObstacleCube 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 ObstacleOcTree{
int octreeCapacity;
boolean divided ;
ArrayList <ObstacleTreeItem> obstacleTreeItems;

ObstacleCube boundary;
ObstacleOcTree NWT, NET, SET, SWT;
ObstacleOcTree NWB, NEB, SEB, SWB;

ObstacleOcTree(ObstacleCube boundary, int octreeCapacity) {
this.boundary = boundary;
this.octreeCapacity = octreeCapacity;
this.obstacleTreeItems = new ArrayList <ObstacleTreeItem>();
this.divided = false;
}

boolean insert(ObstacleTreeItem obstacleTreeItem) {
if (!this.boundary.obstacleContains(obstacleTreeItem)) {
return false;
}

if (this.obstacleTreeItems.size() < this.octreeCapacity) {
return true;
} else {
if (!this.divided) {
this.subdivide();
}

// N = North, S = South, E = East, W = West, B = Bottom, T = Top
if (this.NWT.insert(obstacleTreeItem)) {
return true;
} else if (this.NET.insert(obstacleTreeItem)) {
return true;
} else if (this.SET.insert(obstacleTreeItem)) {
return true;
} else if (this.SWT.insert(obstacleTreeItem)) {
return true;
} else if (this.NWB.insert(obstacleTreeItem)) {
return true;
} else if (this.NEB.insert(obstacleTreeItem)) {
return true;
} else if (this.SEB.insert(obstacleTreeItem)) {
return true;
} else if (this.SWB.insert(obstacleTreeItem)) {
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;

ObstacleCube NWTBoundary = new ObstacleCube(x - w, y - h, z - d, w, h, d);
ObstacleCube NETBoundary = new ObstacleCube(x + w, y - h, z - d, w, h, d);
ObstacleCube SETBoundary = new ObstacleCube(x + w, y + h, z - d, w, h, d);
ObstacleCube SWTBoundary = new ObstacleCube(x - w, y + h, z - d, w, h, d);
ObstacleCube NWBBoundary = new ObstacleCube(x - w, y - h, z + d, w, h, d);
ObstacleCube NEBBoundary = new ObstacleCube(x + w, y - h, z + d, w, h, d);
ObstacleCube SEBBoundary = new ObstacleCube(x + w, y + h, z + d, w, h, d);
ObstacleCube SWBBoundary = new ObstacleCube(x - w, y + h, z + d, w, h, d);

this.NWT = new ObstacleOcTree(NWTBoundary, this.octreeCapacity);
this.NET = new ObstacleOcTree(NETBoundary, this.octreeCapacity);
this.SET = new ObstacleOcTree(SETBoundary, this.octreeCapacity);
this.SWT = new ObstacleOcTree(SWTBoundary, this.octreeCapacity);
this.NWB = new ObstacleOcTree(NWBBoundary, this.octreeCapacity);
this.NEB = new ObstacleOcTree(NEBBoundary, this.octreeCapacity);
this.SEB = new ObstacleOcTree(SEBBoundary, this.octreeCapacity);
this.SWB = new ObstacleOcTree(SWBBoundary, this.octreeCapacity);
this.divided = true;
}

ArrayList<ObstacleTreeItem> query(ObstacleCube range, ArrayList<ObstacleTreeItem> found) {
if (found == null) found = new ArrayList<ObstacleTreeItem>();

if (!this.boundary.obstacleIntersects(range)) {
return found;
} else {

for (ObstacleTreeItem obstacleTreeItem : this.obstacleTreeItems) {
if (range.obstacleContains(obstacleTreeItem)) {
}
}

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

for (ObstacleTreeItem p : obstacleTreeItems){
stroke(255);
strokeWeight(1);
point(p.x, p.y, p.z);
}
}
}

class Boid{
PVector position;
PVector velocity;
PVector acceleration;
float x, y, z;
float maxForce = 0.1;
float maxSpeed = 2;
float flap = 0;
float sc = 2;
color col;
OcTree octree, otherOctree;
Cube wall;

Boid(color col_, int perceptionRadius_, Cube wall_){
this.wall = wall_;
this.position = new PVector(random(wall.xMin, wall.xMax),
random(wall.yMin, wall.yMax),
random(wall.zMin, wall.zMax) );
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(OcTree octree_, OcTree otherOctree_){
float maxAngle = PI ;
int tot = 0;
int interTot = 0;
int avoidTot = 0;

ArrayList<PVector> steering = new ArrayList<PVector>();
PVector alignSteering = new PVector();
PVector cohesionSteering = new PVector();
PVector separationSteering = new PVector();
PVector interSeparationSteering = new PVector();
PVector avoidSteering = new PVector();

OcTree octree = octree_;
OcTree otherOctree = otherOctree_;

ArrayList<TreeItem> maybeNeighbors = octree.query(range, null);
for (TreeItem other : maybeNeighbors){
PVector diff = PVector.sub(this.position, other.boid.position);
float d = diff.mag();
float theta = PVector.angleBetween(position, PVector.sub(this.position, other.boid.position));

if (other.boid != this && d < perceptionRadius && theta < maxAngle){

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

tot++;
}
}

ArrayList<TreeItem> interMaybeNeighbors = otherOctree.query(range, null);
for (TreeItem other : interMaybeNeighbors){
PVector diff = PVector.sub(this.position, other.boid.position);
float d = diff.mag();
float theta = PVector.angleBetween(position, PVector.sub(this.position, other.boid.position));

if (other.boid != this && d < interPerceptionRadius && theta < maxAngle){

diff.setMag(1/sq(d)); // Magnitude inversely proportional to the squared distance
interTot++;
}
}

if (avoidObstacle){
ArrayList<ObstacleTreeItem> obstacles = obstacleOcTree.query(obstacleRange, null);
for (ObstacleTreeItem p : obstacles){
PVector point = new PVector(p.x, p.y, p.z);
PVector diff = PVector.sub(this.position, point);
float d = diff.mag();
float theta = PVector.angleBetween(position, PVector.sub(this.position, point));

if (d < interPerceptionRadius && theta < maxAngle){
diff.setMag(1/sq(d)); // Magnitude inversely proportional to the squared distance

avoidTot++;
}
}
}

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

if (interFlockInteraction && interTot > 0){
interSeparationSteering.div(interTot);
interSeparationSteering.setMag(this.maxSpeed);
interSeparationSteering.sub(this.velocity);
interSeparationSteering.limit(this.maxForce);
}

if (avoidObstacle && avoidTot > 0){
avoidSteering.div(avoidTot);
avoidSteering.setMag(this.maxSpeed);
avoidSteering.sub(this.velocity);
avoidSteering.limit(this.maxForce);
}

alignSteering.mult(1.8);
cohesionSteering.mult(1.5);
separationSteering.mult(2.2);

return steering;
}

void flock(OcTree octree_, OcTree otherOctree_){
ArrayList<PVector> steering = behaviour(octree_, otherOctree_);
if (interFlockInteraction) this.acceleration.add(steering.get(3)); // inter separation steering force
if (avoidObstacle) this.acceleration.add(steering.get(4)); // inter separation steering force

if(avoidWalls)
{
this.acceleration.add(PVector.mult(avoid(new PVector(position.x, wall.yMax, position.z), true), 10));
this.acceleration.add(PVector.mult(avoid(new PVector(position.x, wall.yMin, position.z), true), 10));
this.acceleration.add(PVector.mult(avoid(new PVector(wall.xMax, position.y, position.z), true), 10));
this.acceleration.add(PVector.mult(avoid(new PVector(wall.xMin, position.y, position.z), true), 10));
this.acceleration.add(PVector.mult(avoid(new PVector(position.x, position.y, wall.zMax), true), 10));
this.acceleration.add(PVector.mult(avoid(new PVector(position.x, position.y, wall.zMin), true), 10));
}
}

void update(){
velocity.limit(maxSpeed);
// RESET FORCES
acceleration.mult(0);
}

void edges() {
if (position.x > wall.xMax) {
position.x = wall.xMin;
} else if (position.x < wall.xMin) {
position.x = wall.xMax;
}
if (position.y > wall.yMax) {
position.y = wall.yMin;
} else if (position.y < wall.yMin) {
position.y = wall.yMax;
}
if (position.z > wall.zMax) {
position.z = wall.zMin;
} else if (position.z < wall.zMin) {
position.z = wall.zMax;
}
}

void show(){
pushMatrix();
translate(position.x, position.y, position.z);
rotateY(atan2(-velocity.z, velocity.x));
rotateZ(asin(velocity.y/velocity.mag()));

strokeWeight(1);
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);

if (showFlap){
vertex(2*sc,0,0);
vertex(-1*sc,0,0);
vertex(-1*sc,-8*sc, flap);

vertex(2*sc,0,0);
vertex(-1*sc,0,0);
vertex(-1*sc,8*sc, flap);
}

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(); //creates vector for steering
steer.set(PVector.sub(position, target)); //steering vector points away from target
if(weight)
steer.mult(1/sq(PVector.dist(position, target)));
steer.limit(maxForce); //limits the steering force to maxSteerForce
return steer;
}

void run(OcTree octree_, OcTree otherOctree_) {
flock(octree_, otherOctree_);
update();
edges();
show();
}
}

// verb controls
void keyPressed() {

if (key == 'o' || key == 'O'){
useOcTree = !useOcTree;
if (octreeShow == false) octreeShow = false;
}

if (key == 's' || key == 'S'){
octreeShow = !octreeShow;
}

if (key == 'a' || key == 'A'){
show2 = !show2;
}
}

// dispaly walls of the system
void get_box(){
noFill();
strokeWeight(1);
stroke(255);

line(0, 0, wall.zMin, 0, wall.yMax, wall.zMin);
line(0, 0, wall.zMax, 0, wall.yMax, wall.zMax);
line(0, 0, wall.zMin, wall.xMax, 0, wall.zMin);
line(0, 0, wall.zMax, wall.xMax, 0, wall.zMax);

line(wall.xMax, 0, wall.zMin, wall.xMax, wall.yMax, wall.zMin);
line(wall.xMax, 0, wall.zMax, wall.xMax, wall.yMax, wall.zMax);
line(0, wall.yMax, wall.zMin, wall.xMax, wall.yMax, wall.zMin);
line(0, wall.yMax, wall.zMax, wall.xMax, wall.yMax, wall.zMax);

line(0, 0, wall.zMin,  0, 0, wall.zMax);
line(0, wall.yMax, wall.zMin, 0, wall.yMax, wall.zMax);
line(wall.xMax, 0, wall.zMin, wall.xMax, 0, wall.zMax);
line(wall.xMax, wall.yMax, wall.zMin,  wall.xMax, wall.yMax, wall.zMax);
}

// Axis code
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
}

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;
float xMin, xMax, yMin, yMax, zMin, zMax;

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_;
this.xMin = x - w;
this.xMax = x + w;
this.yMin = y - h;
this.yMax = y + h;
this.zMin = z - d;
this.zMax = z + 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   );
}

Boolean obstacleContains(ObstacleTreeItem obstacleTreeItem) {
return ( obstacleTreeItem.x >= x - w && obstacleTreeItem.x <= x + w &&
obstacleTreeItem.y >= y - h && obstacleTreeItem.y <= y + h &&
obstacleTreeItem.z >= z - d && obstacleTreeItem.z <= z + d   );
}
}

class OcTree {
int octreeCapacity;
boolean divided ;
ArrayList <TreeItem> treeItems;

Cube boundary;
OcTree NWT, NET, SET, SWT;
OcTree NWB, NEB, SEB, SWB;

OcTree(Cube boundary, int octreeCapacity) {
this.boundary = boundary;
this.octreeCapacity = octreeCapacity;
this.treeItems = new ArrayList <TreeItem>();
this.divided = false;
}

boolean insert(TreeItem treeItem) {
if (!this.boundary.contains(treeItem)) {
return false;
}

if (this.treeItems.size() < this.octreeCapacity) {
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.octreeCapacity);
this.NET = new OcTree(NETBoundary, this.octreeCapacity);
this.SET = new OcTree(SETBoundary, this.octreeCapacity);
this.SWT = new OcTree(SWTBoundary, this.octreeCapacity);
this.NWB = new OcTree(NWBBoundary, this.octreeCapacity);
this.NEB = new OcTree(NEBBoundary, this.octreeCapacity);
this.SEB = new OcTree(SEBBoundary, this.octreeCapacity);
this.SWB = new OcTree(SWBBoundary, this.octreeCapacity);
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);
}
}
}
/*
TODO

- pov camera of a boid
- avoid objects  octree --> single octree class ???
- take out boids from the avoid object
- clean octree dependence
*/

// CAMERA
import peasy.*;
import peasy.org.apache.commons.math.geometry.*;
PeasyCam cam;
CameraState state;

// AXIS
PFont axisLabelFont;
PVector axisXHud, axisYHud, axisZHud, axisOrgHud;

// RECORDING
boolean recordVideo = false;
int SECONDS_TO_CAPTURE = 10;
int VIDEO_FRAME_RATE = 60;
int videoFramesCaptured = 0;

// VERBS
boolean useOcTree = true, showBox = true, octreeShow = false, show2 = true;
boolean avoidWalls = true;
boolean showFlap = false;
boolean interFlockInteraction = true;
boolean avoidObstacle = true;

// PARAMETERS
int z_min = 0;
int z_max;
int boyz_num = 1000;
int octreeCapacity = 10;

// FLOCK INITIALIZATION
Cube wall;

OcTree octree1, octree2;
Flock flock1, flock2;

// OBSTACLE INITIALIZATION
// x0, y0, z0 is the centre of the sphere/torus
// r is the radius of the sphere and r1 is the section radius of the torus
float x0, y0, z0, r, r1;
ObstacleOcTree obstacleOcTree;
ObstacleCube obstacleWall;

void setup() {
size(800, 800, P3D);
z_max = height;

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

// DIFFERENT CAMERA FOR FURTHER DEVELOPMENT
/*camera(width, height, z_max, // eyeX, eyeY, eyeZ
width/2, height/2, z_max/2, // centerX, centerY, centerZ
1, 1.0, 0.0); // upX, upY, upZ
*/

// AXIS SETUP
axisLabelFont = createFont( "Arial", 14 );
axisXHud      = new PVector();
axisYHud      = new PVector();
axisZHud      = new PVector();
axisOrgHud    = new PVector();

// BOUND OF THE OCTREES
wall = new Cube(width/2, height/2, z_max/2, width/2, height/2, z_max/2);

// FLOCK INITIALIZATION

// OBSTACLE INITIALIZATION
ArrayList<Float> thetaList = new ArrayList<Float>();
ArrayList<Float> phiList = new ArrayList<Float>();
int num = 50;
x0 = width/2;
y0 = height/2;
z0 = z_max/2;
r = 100;
r1 = 300;
// get arraylist of angles
for (int i = 0; i < num; i++){
// for a sphere obstacle
thetaList.add( 0 + i * (PI - 0) / (num - 1)) ;
// for a torus obstacle
// thetaList.add( 0 + i * (2*PI - 0) / (num - 1)) ;
phiList.add( 0 + i * (2*PI - 0) / (num - 1)) ;
}

obstacleWall = new ObstacleCube(width/2, height/2, z_max/2, width/2, height/2, z_max/2);
obstacleOcTree = new ObstacleOcTree(obstacleWall, octreeCapacity);
for (float theta : thetaList){
for (float phi : phiList){
obstacleOcTree.insert(new ObstacleTreeItem(x0, y0, z0, r, r1, theta, phi));
}
}

// if there are boids inside of the sphere obstacle, take them off
for (Boid b : flock1.boids){
// for a sphere obstacle
if (sq(b.x-x0) + sq(b.y-y0) + sq(b.z-z0) <= sq(r)){
b.position = new PVector(random(10),random(10),random(10));
}

/* for a torus obstacle
if ( sq(r - sqrt(sq(b.x-x0) + sq(b.y-y0)) ) + sq(b.z-z0) <= sq(r1)){
b.position = new PVector(random(100),random(100),random(100));
}*/
}

for (Boid b : flock2.boids){
// for a sphere obstacle
if (sq(b.x-x0) + sq(b.y-y0) + sq(b.z-z0) <= sq(r)){
b.position = new PVector(random(10),random(10),random(10));
}

/* for a torus obstacle
if ( sq(r - sqrt(sq(b.x-x0) + sq(b.y-y0)) ) + sq(b.z-z0) <= sq(r1)){
b.position = new PVector(random(100),random(100),random(100));
}*/
}

}

void draw() {
background(27);
directionalLight(150, 150, 150, 0 , -1, 0);

// SHOW OBSTACLE

// obstacleOcTree.show(255, 1); // actual points that the boids avoid

// cooler display of the obstacle sphere --> what about a torus ? --> USE PJ5 OR ??
pushMatrix();
noStroke();
ambient(51, 26, 0);
translate(x0, y0, z0);
sphere(r);
popMatrix();

// dispaly bounds of the system
get_box();

// run flocks
octree1 = new OcTree(wall, octreeCapacity);
for (Boid b : flock1.boids) {
octree1.insert(new TreeItem(b));
}

octree2 = new OcTree(wall, octreeCapacity);
for (Boid b : flock2.boids) {
octree2.insert(new TreeItem(b));
}

flock1.run(octree1, octree2);
flock2.run(octree2, octree1);

// SHOW AXES
/*
calculateAxis(500);
cam.beginHUD();
drawAxis(3);
cam.endHUD();
*/

// RECORDING
if (recordVideo){
saveFrame("export/####-export.tga");
if (videoFramesCaptured > VIDEO_FRAME_RATE * SECONDS_TO_CAPTURE){
recordVideo = false;
videoFramesCaptured = 0;
println("end of recording");
}else{
videoFramesCaptured++;
}
}
}

// POV CAMERA DEVELOPMENT
/*
PVector pos = flock1.boids.get(0).position;
PVector vel = flock1.boids.get(0).velocity;

strokeWeight(50);
stroke(255, 255, 255, 20);
point(pos.x, pos.y, pos.z);

camera(pos.x-100, pos.y-100, pos.z-100,
vel.x, vel.y, vel.z,
0, 1, 0);
*/

``````

I was trying to setup a torus obstacle but is seems that there’s no torus() function in processing, I know its present in pj5 but I was wondering if you know some libraries that do 3d surface rendering (like surfaceLib that I’m not able to get working ;( ) ?

1 Like

@Chrisir, I just put the 5 blocks of code from post 3 in 5 tabs and it ran.

1 Like