18
\$\begingroup\$

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:

Crude drawing of two "boids", one facing left, and the other facing right.

  • 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:

190-frame animation of the Boids Algorithm with 5 boids.

Winning criterion

This is , so the smallest solution in bytes wins.

\$\endgroup\$
  • 7
    \$\begingroup\$ "There is, of course, more to the algorithm, so I highly recommend checking out the source." - is everything necessary here or not? If not I'd recommend fixing that. \$\endgroup\$ – Jonathan Allan Jan 28 '18 at 22:23
  • 1
    \$\begingroup\$ Please use the sandbox before posting challenges, as advised on the ask page. \$\endgroup\$ – flawr Jan 28 '18 at 22:26
  • \$\begingroup\$ @JonathanAllan Yeah, everything necessary is here, but more in-depth explanations that may make more sense to other users are available at the source. \$\endgroup\$ – iPhoenix Jan 28 '18 at 22:29
  • 11
    \$\begingroup\$ This is an interesting challenge (I find flocking behaviours fascinating) but it will need to be well specified, especially for a code-golf, otherwise the pressure to reduce the length of the code will cause every possible deviation from the spirit of the challenge to be incentivised. \$\endgroup\$ – trichoplax Jan 28 '18 at 22:34
7
+50
\$\begingroup\$

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:

boids

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Can 2*PI not become TAU to save a byte? \$\endgroup\$ – Jonathan Frech Feb 2 '18 at 18:09
  • \$\begingroup\$ @JonathanFrech Yes it can; I originally had -PI,PI and I was going that way, but got sidetracked. \$\endgroup\$ – Phlarx Feb 2 '18 at 18:51
  • \$\begingroup\$ My program (which was written in js and html) didn't export a gif, but it drew an image and I used a screen capturing program and converted the video it exported to a gif. There is one thing I did notice, though. The boids have a blue outline, which doesn't follow the spec :) \$\endgroup\$ – iPhoenix Feb 2 '18 at 20:52
  • \$\begingroup\$ Just another friendly reminder, this answer does not follow the spec, so it won't get the bounty. \$\endgroup\$ – iPhoenix Feb 5 '18 at 0:06
  • 1
    \$\begingroup\$ I don't know Processing, but I think you can golf the following things: ,i, to ,i=0, and then remove the i=0 inside the for-loop. (-1 byte); frameCount%f==0 to frameCount%f<1 (1 byte); && to & in the final if 2*d>=p.dist(m)&q.angleBetween(v,q.sub(m,p))<=5*PI/6 (-1 byte). Again, not sure if these are possible, but since Processing seems fairly similar to Java, I think it is. Also, you could try creating a gif with screentogif.com. \$\endgroup\$ – Kevin Cruijssen Feb 5 '18 at 12:47
4
\$\begingroup\$

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>

\$\endgroup\$
  • \$\begingroup\$ The boids don't seem to interact when I run the snippet \$\endgroup\$ – Jo King Feb 7 '18 at 5:39
  • \$\begingroup\$ @JoKing it should be fixed now \$\endgroup\$ – Patrick Roberts Feb 7 '18 at 6:33
  • \$\begingroup\$ The problem was because the babel minifier shadowed a global variable in one function with a parameter name, and the implicit typecast to a number didn't throw an error, so the function just failed silently and never detected any neighbors. \$\endgroup\$ – Patrick Roberts Feb 7 '18 at 6:38
  • \$\begingroup\$ I'll try to make an interactive demo tomorrow night but I've run out of steam for tonight. \$\endgroup\$ – Patrick Roberts Feb 7 '18 at 6:47
  • \$\begingroup\$ Just a note: where it reads t.a+v+l/10+f/50, if you change that to t.a+v/3+l/10+f/50, it produces somewhat more interesting behavior, but the current program is smaller and still to spec. \$\endgroup\$ – Patrick Roberts Feb 7 '18 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.