boids

kostino

here are some videos I made of boids simulation.
The quality is not perfect, but I am working on it...

kostino

Here is one more
ok, this is getting old...

Poersch

Nice! How did you achieve the collision/near-field querying? It doesn't look like brute force. Maybe a quad-tree, spacial hashing or a simple 2D-grid? Multicore support? Gimme infos! :D

kostino

Actually, it is plain old brute-force.
There is the FlockingGame class, which includes an Arraylist of boids. It Passes the ArrayList into each bird and then the bird defines its neighbors by comparing distances, and finally reacts by "Avoid", "Copy", "Center" rules.
I have done some work on them, so that they produce a more "natural" effect.
Other than that, the algorithm works well with up to 1000 - 1500 boids at 30fps in realtime.
So "boids test 2" (10000 boids) for example produced about a frame per 2 seconds...quite slow, one might say
At the moment I do not care that much for real-time animation, although I am generally interested in more effective solutions or approaches.

I am also working on an alternate approach through a 2D matrix (as a field which affects the boids), although I am not yet sure if it will give a significant performance increase... It will, though, for sure offer some quite different ways of interaction.
I will get back on that ^ as soon as I have something new.

Poersch

Ah, great! Yeah, in case your force field eliminates the need for a bird to examine any other bird, it should give you a much better performance.

KesterR

Wow, they're beautiful! It really shows people what self-organization means so clearly.

I'm just a beginner, started learning to code a few weeks ago for my Biology undergrad dissertation project.

Your boids look so realistic! They look properly like murmuring starlings! :-D

I'm actually trying to model sheep flocking and how different types of parasites which affect the behaviour of sheep are likely to influence their collective movement patterns. The ultimate aim is that it might help farmers pick the 5% most likely to be most heavily infected and treat with anthelmintics in a better targeted way so the parasites don't evolve resistance to the drugs so fast and we prolong the useful lifespan of current anthelmintic drugs while not leaving the sheep to suffer in the meantime.

(sheep flock in motion)

Sheep look most like your animated example 2. Please may I ask what ratio of repulsion:orientation:attraction you used to get that pattern?

I've been struggling with Matlab code for a few weeks, I'm nearly running out of time and losing hope, and just discovered Daniel Shiffman's example - http://processing.org/examples/flocking.html So thankful for the line comments explaining what each line is doing! Also the way he's coded repulsion, orientation and attraction in terms of acceleration rather than just direction is both more realistic and very convenient for me because I don't have to then code individual variation in speed for parasitized and un-parasitized separately, but just make a second population of boids which I can set different repulsion, orientation and attraction values for.

So that's my main question: Please how would I add a second population of boids? (I will carry on trying to work it out myself, but you could probably tell me in 20s what it would take me a week to work out by myself at this stage of beginner!)

Secondly, Kostino, please could I possibly look at and maybe use your boids code which produced the beautiful animations above (with proper attribution and referencing in my dissertation, of course)?

Thanks v much

Kester!

kostino

Here is the code (I have about 20 versions of it, but this one also has a "follow" part, in which they follow the cursor). It lacks comments, but may be helpful if you follow it.
In this solution a bird checks every other to see if it is a neighbor. There you could also add a check to see "what kind of bird is it?" friend / enemy and so on and work your way through.
I will get back on that later, tell me if you have any questions on this code:

FlockingGame g;

void setup(){
  size(600,600,P2D);
  frameRate(60);
  g = new FlockingGame(1000);
  background(255);
}

void draw(){
  //fill(255,125);
  //rect(0,0,800,800);
  background(0);
  g.update();
}

class FlockingGame{
  ArrayList birds;
  int num;
  int time;
  Target t;
  FlockingGame(int inNum){
    num = inNum;
    t = new Target();
    birds = new ArrayList();
    for(int i=0; i<num; i++){
      birds.add(new Bird());
    }
  }
  void update(){
    time++;
    t.update();
    for(int i = 0; i<birds.size(); i++){
      Bird b = (Bird) birds.get(i);
      b.findNeighbors(birds);
      b.update(t.getPos());
      float d = b.pos.dist(t.pos);
    }
  }
  void generate(){

  }
}

///////////////////////////////////////////////////////////
//CLASS BIRD
///////////////////////////////////////////////////////////
class Bird {
  PVector pos; 
  PVector vel; //velocity
  PVector tar;
  PVector desiredHeading;
  BirdAI ai;
  float tsa; //turn step angle
  ArrayList neighbors;
  float seeDist;
  Bird() {
    pos = new PVector();
    tar = new PVector();
    pos.x = random(0, 800);
    pos.y = random(0, 800);
    vel=PVector.random2D();
    vel.mult(2);
    desiredHeading = new PVector();
    ai = new BirdAI();
    tsa = PI/50;
    seeDist = 50;
    neighbors = new ArrayList();
  }
  ////////////////////////////////////////////////////////////
  //step 1: collect information (find neighbors)
  ////////////////////////////////////////////////////////////
  void findNeighbors(ArrayList allBirds) {
    neighbors = new ArrayList(); //clean ArrayList
    PVector otherPos = new PVector();
    for (int i = 0; i< allBirds.size(); i++) {
      Bird b = (Bird) allBirds.get(i);
      if (this != b) {//do not compare with self
        otherPos.set(b.pos);
        float dist = pos.dist(otherPos);
        if (dist < seeDist) {
          neighbors.add(b);
        }
      }
    }
  }

  /////////////////////////////////////////////////////////////
  //step 2: take action
  /////////////////////////////////////////////////////////////
  void update(PVector inTar) {
    tar.set(inTar);
    //ai.update(pos, tar, neighbors);
    desiredHeading.set(ai.update(pos, tar, neighbors));
    float r = tsa * sign();
    vel.rotate(r);
    collisions();
    //if (pos.x>600){if (vel.x>0) vel.x*= -1;}
    pos.add(vel);
    render();
  }

  int sign() {
    int a = -(int) Math.signum(vel.y*desiredHeading.x - vel.x*desiredHeading.y);
    return a;
  }

  void collisions(){
    if ((pos.x>600)&&(vel.x>0)) vel.x *=-1;
    if ((pos.y>600)&&(vel.y>0)) vel.y *=-1;
    if ((pos.x<0)&&(vel.x<0)) vel.x *=-1;
    if ((pos.y<0)&&(vel.y<0)) vel.y *=-1;
  }

  void render() {
    fill(0,255,0);
    float s = 1;
    noStroke();
    pushMatrix();
    translate(pos.x, pos.y);
    rotate(vel.heading()+PI/2);
    beginShape();
    vertex(-s, 0);
    vertex(0, -4*s);
    vertex(s, 0);
    endShape(CLOSE);
    popMatrix();
  }
}

class BirdAI{
  ArrayList neighbors;
  Bird me;
  PVector pos; PVector tar;
  PVector avoidHeading; float avoidFactor;
  PVector copyHeading; float copyFactor;
  PVector centerHeading; float centerFactor;
  PVector targetHeading; float targetFactor;
  PVector desiredHeading;
  //Behaviour bhv;

  BirdAI(){
    pos = new PVector();
    tar = new PVector();
    avoidHeading = new PVector();
    copyHeading = new PVector();
    centerHeading = new PVector();
    targetHeading = new PVector();
    desiredHeading = new PVector();
    //bhv = new Behaviour();
  }
  PVector update(PVector inPos, PVector inTar, ArrayList inNeighbors){
    neighbors = inNeighbors;
    pos.set(inPos);
    tar.set(inTar);
    //calculate vectors
    avoidHeading.set(avoidV());          //calculate avoid vector
    copyHeading.set(copyV());            //calculate copy vector
    centerHeading.set(centerV());        //calculate center vector
    targetHeading.set(targetV());        //calculate target vector
    //apply weights
    avoidHeading.mult(1);                //apply heading weight
    copyHeading.mult(4);                 //apply heading weight
    centerHeading.mult(1);               //apply heading weight
    targetHeading.mult(5);               //apply heading weight
    //add them to find the desired heading
    desiredHeading.set(avoidHeading);
    desiredHeading.add(copyHeading);
    desiredHeading.add(centerHeading);
    desiredHeading.add(targetHeading);
    return desiredHeading;
  }
  PVector avoidV(){
    PVector aV = new PVector();
    PVector tow = new PVector();
    for(int i = 0; i < neighbors.size(); i++){
      Bird n = (Bird) neighbors.get(i);
      tow.set(pos); tow.sub(n.pos);
      float d = tow.mag();
      tow.normalize();
      tow.mult(20/d);
      aV.add(tow);
    }
    //aV.div((neighbors.size()+1)/2);
    return aV;
  }

  PVector copyV(){
    PVector cpV = new PVector(0,0,0);
    for(int i = 0; i < neighbors.size(); i++){
      Bird n = (Bird) neighbors.get(i);
      cpV.add(n.vel);
    }
    cpV.div(neighbors.size());
    return cpV;
  }

  PVector centerV(){
    PVector cnV = new PVector(0,0,0);
    float d = 0;
    for(int i = 0; i < neighbors.size(); i++){
      Bird b = (Bird) neighbors.get(i);
      d += pos.dist(b.pos);
      cnV.add(b.pos);
    }
    cnV.div(neighbors.size());
    PVector toC = new PVector();
    cnV.sub(pos);
    //cnV.mult(d/1000);
    //cnV.normalize();
    return cnV;
  }

  PVector targetV(){
    PVector tV = new PVector();
    tV.set(tar);
    tV.sub(pos);
    float d = pos.dist(tV);
    d = pow((d/2000),2);
    tV.mult(d);
    tV.normalize();
    tV.mult(mouseCheck());
    return tV;
  }

  int mouseCheck(){
    if (mousePressed) return -1;
    else return 1;
  }
}

class Target{
  PVector pos;
  Target(){
    pos = new PVector(300,300,0);
  }
  void update(){
    pos.x = mouseX;
    pos.y = mouseY;
    pos.z = 0;
    //show();
  }
  PVector getPos(){
    return pos;
  }
  void show(){

  }
}

kostino

Sheep look most like your animated example 2. Please may I ask what ratio of repulsion:orientation:attraction you used to get that pattern?

It's a bit more complicated than the ratio between these three.
Actually what I've done, is almost like:
-Ok, every bird tries to avoid every other bird...
-Let's say we have bird A and bird B.
-Avoid for bird A, means that it will try to head to the opposite direction than towards B. So It has to try to reach the direction of the vector that goes from B to A.
-Apart from that, there is a "strength" to that vector that concerns us...
-The simpler case would be to say: The closer A is to B, the more A wants to avoid B. Now this could be a linear relationship, or any other. For example I've used the function ["Repulsion strength" = 20 / "distance"] as "seen" in line 181 of the code above. This produces a graph that "explodes" as the distance gets smaller.
-I think this is the main tweak I had to do for the algorithm to flow more "naturally"...
-So every relation of the form "y = a*x" gives linear graphs, and usually "not-so-natural-looking-behaviors" while usually the use of other relations (like "y = a/x" in this example) gives more interesting results.
-Try to think in terms of functions and graphs.

-It also took much tweaking and failing to get there, and much breaking-down the problem into smaller parts.

KesterR

Hi Kostino

thank you very much! I've tried out your code, will take me a while to understand how it's working.

I understand your point about the greater acceleration away from neighbours the closer each boid gets. That makes sense. Sheep seem to have a very small radius of repulsion, if threatened they'll run very tightly packed, but if they're going to collide not aligned then I guess they would accelerate the other way or align themselves very quickly.

So next for my project I need to duplicate the population, and be able to vary the radii of alignment and attraction for each population separately. The parasitized sheep are expected to have larger radii of alignment and attraction, i.e. weaker flocking tendency, because they're more selective about feeding and likely to range further from the flock to feed, and maybe not keep up so well when flocking to avoid a perceived predator.

I've found Daniel Shiffman's textbook with lots of examples of Boids, so I may find the answer in there.

Thanks Kester

kostino

no problem :)

I also took a look at Shifman's book, I had not found that so far.
Seems to me I was kinda reinventing the wheel...

anyway...

KesterR

Hi Kostino

please could I have a look at one of the versions without following the cursor in (but still with the hard boundary in)?

I noticed the boids tend to get stuck in a corner without the cursor directing them back into the middle, especially when I reduced the number of boids to a size more like an average (UK) sheep flock (300). I just looked that up and that was one of the conclusions in Buhl, Couzin et al 2006 too.

I've actually ordered a paper copy of Shiffman's book now, as I'm getting quite panicky about my dissertation project now. We're supposed to finish practical work by the end of this month!

Please could you give me a pointer or two how to duplicate the population, and have separate control variables for each?

I think I need to make a parasitized and un-parasitized population of boids, in the same flock, just slightly different alignment and attraction values (lower for the parasitized, i.e. they tend to forage further from the flock and are more selective in feeding).

Thanks!

KesterR

P.s. please do you have any idea (or even script? ;-) ) for limiting the number of nearest neighbours assessed to e.g. seven, to simulate limited sensory fields (birds or fish flying/ swimming in formation probably can't see or sense many more than a few of their nearest neighbours at a time)?

I understand the influence of neighbouring boids decreases with distance, so it doesn't make a huge difference, but it would be a step more realistic.

kostino

perhaps you could choose the "7" that are closer to it?
Or use a field of view to lomit neighbors?
Not quite sure how random would work...
However, based on the code above, you could do this to limit the number of neighbors to "7" in a random way.

  void findNeighbors(ArrayList allBirds) {
    neighbors = new ArrayList(); //clean ArrayList
    PVector otherPos = new PVector();
    for (int i = 0; i< allBirds.size(); i++) {
      Bird b = (Bird) allBirds.get(i);
      if (this != b) {//do not compare with self
        otherPos.set(b.pos);
        float dist = pos.dist(otherPos);
        if (dist < seeDist) {
          neighbors.add(b);
        }
      }
    }
    //add this "while loop" to the code, inside the bird class
    while(neighbors.size()>7){
      int i = int( random( 0, neighbors.size() ) );
      neighbors.remove(i);
    }
  }

kostino

latest update:

kostino

Here is one more, I finally managed to make a symmetrical approach on the boids. That means that boids close to the edge perceive boids close to the opposite edge as neighbors. This creates a symmetrical (top to bottom and left to right) behavior on the plane, and does not create strange behavior near the edges. Neither bouncing, nor teleportation... just symmetricality...