Implement the Boids algorithm

Question

Introduction

The Boids Algorithm is a relatively simple demonstration of emergent behavior in a group. It has three main rules, as described by its creator, Craig Reynolds:

The basic flocking model consists of three simple steering behaviors which describe how an individual boid maneuvers based on the positions and velocities its nearby flockmates:

• Separation: steer to avoid crowding local flockmates.
• Alignment: steer towards the average heading of local flockmates.
• Cohesion: steer to move toward the average position of local flockmates.

Each boid has direct access to the whole scene's geometric description, but flocking requires that it reacts only to flockmates within a certain small neighborhood around itself. The neighborhood is characterized by a distance (measured from the center of the boid) and an angle, measured from the boid's direction of flight. Flockmates outside this local neighborhood are ignored. The neighborhood could be considered a model of limited perception (as by fish in murky water) but it is probably more correct to think of it as defining the region in which flockmates influence a boids steering.

I am not perfect when explaining things, so I highly recommend checking out the source. He also has some super informative pictures on his site.

Challenge

Given the number of boids (simulated entities) and the number of frames, output an animation of the simulation.

• The boids should be rendered as a red circle, with a line inside of the circle showing its heading, which is the direction the boid is pointing in:

• The angle of each boid (as described by Reynolds) should be a full 300 degrees. (not 360)
• The starting heading and position of each boid should be uniformly random (but seeded, so that the output is still determinate), as well as the position.
• If the radius of the boid is 1, than the radius of the neighborhood should be 3.
• The number of boids will be anywhere from 2-20.
• The number of frames will be anywhere from 1-5000
• The animation should be played with a minimum of 10 milliseconds per frame and a maximum of 1 second times the number of boids. (2 boids = 2 seconds per frame max, 3 boids = 3 seconds per frame max, et cetera)
• The output animation should be at least 5 boid-radii by 5 boid-radii, times half the number of boids. So, the minimum size for 2 boids would be 10 boid-radii by 10 boid-radii, the minimum for 3 boids would be 15 boid-radii by 15 boid-radii, et cetera.
• The radius of each boid must be a minimum of 5 pixels and a maximum of 50 pixels.
• The speed of each boid needs to be limited so that it doesn't move more than 1/5th of its radius in one frame.
• The output needs to be determinate, so that the same input will produce the same output if run multiple times.
• If a boid reaches a border, it should wrap back to the other side. Likewise, the neighborhood around each boid should also wrap around the borders.

Rules for the algorithm

In this case, each boid has a sector around it spanning 300 degrees, centered on the boid's heading. Any other boids in this "neighborhood" are considered "neighbors", or (to use Reynolds' term) "flockmates".

1. Each boid should adjust its heading to avoid collisions and maintain a comfortable distance of one boid-radius with its neighbors. (This is the "Separation" aspect of the algorithm. The one boid-radius may be bypassed, but it should be like a rubber band, snapping back into place.)

2. Each boid should additionally adjust its heading to be closer to the average heading of the other boids in its neighborhood, as long as it doesn't interfere with the first rule. (This is the "Alignment" aspect of the algorithm)

3. Each boid should turn itself towards the average position of its flockmates, as long as this doesn't cause collision or significantly interfere with the second rule.

In his paper on the subject, he explains this as follows:

To build a simulated flock, we start with a boid model that supports geometric flight. We add behaviors that correspond to the opposing forces of collision avoidance and the urge to join the flock. Stated briefly as rules, and in order of decreasing precedence, the behaviors that lead to simulated flocking are:

• Collision Avoidance: avoid collisions with nearby flockmates
• Velocity Matching: attempt to match velocity with nearby flockmates
• Flock Centering: attempt to stay close to nearby flockmates

More detailed description of movement:

• The standard implementation of the Boids Algorithm usually does a calculation for each of the rules, and merges it together.
• For the first rule, the boid goes through the list of neighboring boids within its neighborhood, and if the distance between itself and the neighbor is less than a certain value, a vector pushing the boid away from is neighbor is applied to the boid's heading.
• For the second rule, the boid calculates the average heading of its neighbors, and adds a small portion (we'll use 1/10 in this challenge) of the difference between its current heading and the average heading to its current heading.
• For the third and final rule, the boid averages the positions of its neighbors, calculates a vector that points towards this location. This vector is multiplied by an even smaller number than what was used for rule 2 (for this challenge, 1/50 will be used) and applied to the heading.
• The boid is then moved in the direction of its heading

Here is a helpful pseudocode implementation of the Boids Algorithm.

Example Input and Output

Input:

5, 190 (5 boids, 190 frames)

Output:

Winning criterion

This is code-golf, so the smallest solution in bytes wins.

Answer 1

Processing 3.3.6 (Java), 932 931 940 928 957 917 904 bytes

^{-1 byte from Jonathan Frech
+11 bytes to better match the spec
-2 bytes from Kevin Cruijssen
-12 bytes for changing args to t()
+29 bytes because I was doing ghosting wrong, see commented version below
-40 bytes for using for loops instead of separate calls for each ghost
-13 bytes for using default frameRate, 30}

Well, it's a start, for someone who doesn't Java-golf. :)

int n=15,f=400,i,j,z=255,w=500;float d=200./n;PVector m;B[]a=new B[n];void setup(){size(500,500);fill(z,0,0);randomSeed(n);for(i=0;i<n;a[i++]=new B(new PVector(random(w),random(w)),m.fromAngle(random(TAU))));}void draw(){background(z);for(B b:a)b.u();if(frameCount%f<1)setup();}class B{PVector p,v,e,q,r;ArrayList<B>n;B(PVector m,PVector o){p=m;v=o;}void u(){e=v.copy();n=new ArrayList();for(B b:a){if(b!=this)for(i=-w;i<=w;i+=w)for(j=-w;j<=w;j+=w)t(i,j,b);}if(n.size()>0){q=new PVector();r=q.copy();for(B b:n){q.add(b.v);r.add(b.p);if(p.dist(b.p)<=d)e.add(p).sub(b.p);}e.add(q.div(n.size()).sub(v).div(10));e.add(r.div(n.size()).sub(p).div(50));}p.add(e.limit(d/10));v=e.mult(10);p.set((p.x+w)%w,(p.y+w)%w);noStroke();ellipse(p.x,p.y,d,d);stroke(0,0,z);line(p.x,p.y,p.x+v.x,p.y+v.y);}void t(int x,int y,B o){m=o.p.copy().add(x,y);if(2*d>=p.dist(m)&q.angleBetween(v,q.sub(m,p))<=5*PI/6)n.add(new B(m,o.v));}}

I don't know any reasonable way to do input in Processing, so the first two variables are the inputs (and I didn't count their values (5 bytes) toward the byte count). If this is a problem, I can try other things.

I also don't know of a good way to allow trying it online (the Processing.js project can't deal with this code style) without hosting things myself; and that is something I'm not eager to attempt. Let me know if there is anything clever I can do.

Formatted code, with comments

int n=15, // Number of boids
    f=400, // Number of frames
    i,j,z=255,w=500; // temp*2, and two constants
float d=200./n; // Boid diameter
PVector m; // temp
B[]a=new B[n];
void setup(){ // This is automatically called at startup
  size(500,500); // Can't use variables for this without extra bytes for settings()
  fill(z,0,0);
  randomSeed(n); // seeded from number of Boids, so that n=19 is very different from n=20
  for(i=0;i<n;a[i++]=new B(new PVector(random(w),random(w)),m.fromAngle(random(TAU))));
}
void draw(){ // This is automatically called each frame
  background(z);
  for(B b:a)
    b.u();
  if(frameCount%f<1) // When desired frames length is hit, reset everything.
    setup();         // Could also use noLoop() instead of setup() to just stop instead.
                     // Or, remove this if statement altogether to go on to infinity.
}
class B{ // Boid
  PVector p,v,e,q,r; // Position, Velocity, Next velocity, and two temp vectors
  ArrayList<B>n; // List of neighbors
  B(PVector m,PVector o){
    p=m;
    v=o;
  }
  void u(){ // Update function, does rules and redraw for this Boid
    e=v.copy();
    n=new ArrayList();
    for(B b:a){ // Test a Boid and its eight ghosts for neighborship
      if(b!=this) // Note: Assumes neighborhood diameter < min(width,height)
        // The ghosts are to check if it'd be closer to measure by wrapping
        // We need eight for wrapping north, east, south, west, northeast,
        // northwest, southeast, and southwest. And also the non-wrapped one.
        // The above assumption ensures that each ghost is further apart than
        // the neighborhood diameter, meaning that only one neighbor might be
        // found for each boid. To test this, place a boid in each corner, right
        // to the edge, facing away from center. Each boid should find three
        // neighbors, that are the three other boids.
        for(i=-w;i<=w;i+=w)for(j=-w;j<=w;j+=w)t(i,j,b);
    }
    if(n.size()>0){
      q=new PVector();
      r=q.copy();
      for(B b:n){
        q.add(b.v); // Velocity matching, pt 1
        r.add(b.p); // Flock centering, pt 1
        if(p.dist(b.p)<=d)  
          e.add(p).sub(b.p); // Collision avoidance
      }
      e.add(q.div(n.size()).sub(v).div(10)); // Velocity matching, pt 2
      e.add(r.div(n.size()).sub(p).div(50)); // Flock centering, pt 2
    }
    p.add(e.limit(d/10)); // Update vectors
    v=e.mult(10);
    p.set((p.x+w)%w,(p.y+w)%w); // Wrapping
    noStroke();
    ellipse(p.x,p.y,d,d); // Draw Boid, finally
    stroke(0,0,z);
    line(p.x,p.y,p.x+v.x,p.y+v.y);
  }
  void t(int x,int y,B o){ // Test if a Boid (or a ghost) is a neighbor
    m=o.p.copy().add(x,y);
    if(2*d>=p.dist(m)&q.angleBetween(v,q.sub(m,p))<=5*PI/6)
      n.add(new B(m,o.v));
  }
}

Sample output

n = 15, frames = 400:

Or, the same animation, but showing the neighborhood of each boid.

Answer 2

JavaScript (ES6) + HTML5, 1200 bytes

Here's my current solution using the Canvas API. The eval() returns a curried function whose first input is the Boid population, and second is the number of animation frames. You can use Infinity for continuous animation.

The eval(...) is 1187 bytes and <canvas id=c> is 13 bytes, making a total of 1200. The CSS is unnecessary, but for convenience, it allows you to see the edges of the canvas.

eval("L7F7{function B8{t=this,t.a=o8*T,t.x=o8*S,t.y=o8*S}C=this.c,D=C.getContext`2d`,({abs:z,random:o,atan2:k,cos:u,sin:g,PI:P,T=2*P,G={c:_7A[r='filter'](b7b!=t)[i](9)79)),n:_7A[r](b7b!=t)[i](9)7({a,x,y:y-S})),s:_7A[r](b7b!=t)[i](9)7({a,x,y:y+S})),e:_7A[r](b7b!=t)[i](9)7({a,x:x-S,y})),w:_7A[r](b7b!=t)[i](9)7({a,x:x+S,y}))},M=I7[I,I+T,I-T][p]((a,x)7z(x)<z(a)?x:a)}=Math),B.prototype={d8{with(D)save8,translate(x,y),rotate(a),beginPath8,arc(0,0,5,0,T),fillStyle='red',fill8,beginPath8,moveTo(0,0),lineTo(10,0),strokeStyle='blue',stroke8,restore8},n:_7(({c,n,s,e,w}=G),c8.concat(n8,s8,e8,w8)[r](b7(d=b.x-x,f=b.y-y,400>d*d+f*f&&z(z(k(f,d)-a)/P-1)>1/6))),s8{q=(j=t.n8).length,v=t.v8||0,l=t.l8||0,f=t.f8||0,a=t.a=(t.a+v+l/10+f/50)%T,t.x=(x+u(a)+S)%S,t.y=(y+g(a)+S)%S},v:_7([d,f]=j[r](b7225>(b.x-x)**2+(b.y-y)**2)[p='reduce'](([d,f],b)7[x+d-b.x,y+f-b.y],[0,0]),d||f?M(k(f,d)-a):0),l:_7j[i](b7M(b.a-a))[p]((a,x)7a+x,0)/q,f:_7([d,f]=j[p](([d,f],b)7[d+b.x,f+b.y],[-x*q,-y*q]),d||f?M(k(f,d)-a):0)},S=C.width=C.height=50*L,A=Array(L).fill().map(_7new B),R=_7{D.clearRect(0,0,S,S),A[i='map'](b79=b).d8),A[i](b79=t=b).s8),F--&&setTimeout(R,10)},R8}".replace(/[789]/g,m=>['=>','()','({a,x,y}'][m-7]))
(10)(Infinity)

canvas{border:1px solid}

<canvas id=c>

Edit

As requested, another snippet with an input for Boid population:

b.onchange=()=>{eval("L7F7{function B8{t=this,t.a=o8*T,t.x=o8*S,t.y=o8*S}C=this.c,D=C.getContext`2d`,({abs:z,random:o,atan2:k,cos:u,sin:g,PI:P,T=2*P,G={c:_7A[r='filter'](b7b!=t)[i](9)79)),n:_7A[r](b7b!=t)[i](9)7({a,x,y:y-S})),s:_7A[r](b7b!=t)[i](9)7({a,x,y:y+S})),e:_7A[r](b7b!=t)[i](9)7({a,x:x-S,y})),w:_7A[r](b7b!=t)[i](9)7({a,x:x+S,y}))},M=I7[I,I+T,I-T][p]((a,x)7z(x)<z(a)?x:a)}=Math),B.prototype={d8{with(D)save8,translate(x,y),rotate(a),beginPath8,arc(0,0,5,0,T),fillStyle='red',fill8,beginPath8,moveTo(0,0),lineTo(10,0),strokeStyle='blue',stroke8,restore8},n:_7(({c,n,s,e,w}=G),c8.concat(n8,s8,e8,w8)[r](b7(d=b.x-x,f=b.y-y,400>d*d+f*f&&z(z(k(f,d)-a)/P-1)>1/6))),s8{q=(j=t.n8).length,v=t.v8||0,l=t.l8||0,f=t.f8||0,a=t.a=(t.a+v/3+l/10+f/50)%T,t.x=(x+u(a)+S)%S,t.y=(y+g(a)+S)%S},v:_7([d,f]=j[r](b7225>(b.x-x)**2+(b.y-y)**2)[p='reduce'](([d,f],b)7[x+d-b.x,y+f-b.y],[0,0]),d||f?M(k(f,d)-a):0),l:_7j[i](b7M(b.a-a))[p]((a,x)7a+x,0)/q,f:_7([d,f]=j[p](([d,f],b)7[d+b.x,f+b.y],[-x*q,-y*q]),d||f?M(k(f,d)-a):0)},S=C.width=C.height=50*L,A=Array(L).fill().map(_7new B),R=_7{D.clearRect(0,0,S,S),A[i='map'](b79=b).d8),A[i](b79=t=b).s8),F--&&setTimeout(R,10)},R8}".replace(/[789]/g,m=>['=>','()','({a,x,y}'][m-7]))(+b.value)(Infinity);b.remove()}

input{display:block}canvas{border:1px solid}

<input id=b><canvas id=c>