Boids - Can I improve my method / efficiency?

Hi all, first post!
So this is my first big stab at boids. It’s still kinda wonky - I plan to implement more features and corrections. I’m more looking for any general tips to increase efficiency (I’m not sure if it’s just my computer’s lack of a graphics card but it can be rather laggy.)
I’d be open to any feedback on my methodology or more general tips. I’m basically just teaching myself right now so I don’t really know what I’m doing.
Thanks!

Bird [] birds;

PVector sum, nextP, avgHead, avgLoc, avgLocDirection, avgHeadUnit;
int a, b, count, size, bIndicator;
boolean loop;
float speed, augAvgHeading, augAvgLoc, maxAug, incrAug, 
  finalDir, augSplit, avoidDir, avoidLERP, PS, check, closest;  
int target, num;
color BG;

void setup() {
  colorMode(RGB, 255, 255, 255);
  fullScreen();
  smooth();
  BG = color(240, 230, 230);
  //strokeWeight(4);
  frameRate(30);

  loop = true;
  num = 500;                 //num birds
  avgLoc = new PVector(0, 0);
  avgHead = new PVector(0, 0);
  avgHeadUnit = new PVector(0, 0);
  augSplit = 0.75;   //for lerp: lower weights towards avgLoc, higher towards avgHeading
  maxAug = 0.1;      //augmentation increment (& limit) to each bird's velocity heading, for each round of loop
  PS = 25;          //personal space of each bird
  size = 2;
  avoidLERP = 0.8;  //how much a bird alters its course based on proximity
  noStroke();

  birds = new Bird [num];
  for (int c = 0; c < num; c++) {
    birds[c] = new Bird();
  }
}

void draw() {
  avgHead.set(0, 0);
  avgLoc.set(0, 0);
  textSize(25);
  fill(0);
  stroke(0);
  background(BG);

  for (int c = 0; c < num; c++)  //gets heading and location values from each 'bird'
  {  
    avgHead.add(birds[c].unitVector());  //vector sum of every bird's heading
  }

  if (mousePressed)
  {
    avgLoc.set(mouseX, mouseY);
  } else {     
    for (int c = 0; c < num; c++)  //gets heading and location values from each 'bird'
    {  
      avgLoc.add(birds[c].loc);
    }
    avgLoc.div(num);
  }

  //avgLoc pointer
  stroke(150, 0, 0);
  ellipse(avgLoc.x, avgLoc.y, size, size);

  for (int c = 0; c < num; c++) //calculate angle-augmentation (rotation) for each bird
  {
    incrAug=maxAug; 
    fill(0);

    avgLocDirection = PVector.sub(avgLoc, birds[c].loc);
    finalDir =  ( ( avgHead.heading() - avgLocDirection.heading() + 3*PI ) % TWO_PI ) - PI;  //determines range between two headings
    // weighted average : LERP method    
    finalDir = lerp(0, finalDir, augSplit); 
    finalDir = ((avgLocDirection.heading() +  finalDir   ) % TWO_PI ) ; //determines final resting place of aspired direction
    finalDir = (( finalDir - birds[c].vel.heading()  + 3*PI ) % TWO_PI ) - PI; //determines finalAug

    closest = PS; 
    bIndicator = num+1;
    for (int d = num-1; d >= 0; d--) //check and adjust for bird-bird proximity
    {
      if (c != d) {
        check = PVector.dist(birds[c].loc, birds[d].loc);
      }
      if (check < PS) {
        if (check < closest)
        {
          closest = check; 
          bIndicator = d;
        }
      }
    } 
    if (bIndicator != num+1)
    {    
      avoidDir = (((PVector.sub(birds[c].loc, birds[bIndicator].loc)).heading() - birds[c].vel.heading()  + 3*PI ) % TWO_PI ) - PI; 
      finalDir = lerp(finalDir, avoidDir, avoidLERP);
    }                          

    if (incrAug >= abs(finalDir)) //smooths motion a little
    {
      birds[c].vel.rotate(finalDir);
    } else {
      incrAug = (finalDir / abs(finalDir)) * incrAug;
      birds[c].vel.rotate(incrAug);
    }
    birds[c].updateLoc();

    if (bIndicator != num+1) { 
      fill( 0, 0, lerp(0, 255, -closest/PS+1.5));    //bird turns blue when close to others
    }
    ellipse(birds[c].loc.x, birds[c].loc.y, size, size);
  }
}

//-----------//

void keyReleased() {
  noLoop();
  loop = false;
}

class Bird {

  PVector loc, vel, unit;
  float speed = 12;

  Bird() {  
    loc = new PVector(int(random(width)), int(random(height)));
    vel = new PVector(speed, 0);
    vel.rotate(random(-PI, PI)); //this is just how heading() describes angles
    unit = new PVector();
    unit = unitVector();
  }

  PVector unitVector() {
    unit = vel.copy();
    unit.normalize();
    return unit;
  }

  void updateLoc() {
    loc.add(vel);
  }
}

Hi!
I worked on a 2d boid simulation, and posted it here in the developement section.

I had similar trouble with slow execution. I think that i looked through the boids too many times per time step.
I used the array list example called flocking in the processing examples.

I am rewriting the program for 3d now, and trying to look through the boids fewer times per time step. I will try to run your program later, to see if i can understand your methods of getting average location and velocity.

Try unify the for loops in draw.
Best would be one for loop only.

When comparing the boid to all others:

Use a nested for loop within the primary one
but let the inner one start at c+1

So when you start both for loops at 0 it means you compare A to B and later B to A which is unnecessary when done wisely.

When your inner for loop starts at c+1 you avoid this

I noticed it runs faster with a smaller bird size. Also was confused about stroke and fill, I think it would be faster with noStroke(), leave all the colour and size to fill().
Anyways with those changes I can have a reasonable framerate until 700 or so.
changed code above with these changes

I think one of my fundamental questions is, for ex:
What is the difference in efficiency between implementing two loops or one…

for array
   get num
for array
   do other stuff

   

vs.

for array
   get num
   do other stuff

Thanks! I’ll take some time to look at this. Yeah I’d also like to do a 3D one, eventually.

Thanks! I’ll look into this!

  • Use FX2D mode: fullScreen(FX2D);

  • Put calculation code in a separate method and thread the method.

  • If you are content for boids to be of size 1x1 pixel, writing the pixel array directly is much faster than calling rect() or ellipse() to draw boids.


Pictured: 120000 particles; 4 calc/draw threads drawing at 50fps on a path-following boids sketch using PThreading.

3 Likes

I have the flocking working well in 3d.
I made some changes to speed up rendering a lot.

Trying to add a predator to the mix now.

Reviewing my spherical geometry to be able to point my predator.

1 Like

sounds cool. pass on the code if you feel like it.

Zipped directory with 3 files
Balls04.zip

https://drive.google.com/file/d/11gjozcoZ6uLAe6-zY75I9VzvRg-W_Hdz/view?usp=drivesdk

This version uses the video export library, which may cause problems if not installed.