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.
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".
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.)
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)
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 OutputInput:
5, 190 (5 boids, 190 frames)
This is code-golf, so the smallest solution in bytes wins.