What is a Boid?
A boid is a bird-oid (bird like) object. Initially coined by Craig Reynolds in his paper on the matter, he outlines a concept called "emergence" where complex behavior emerges from a set of simple rules applied to each individual. Before jumping into exactly what these rules are or how they are applied computationally, why bother simulating this in the first place? Well, it turns out simulating the behavior of birds or schools of fish is useful to a variety of fields, especially computer graphics and animal study. If scientists want to observe how perturbations in a habitat will affect certain animals, they can use boids. If a movie producer needs to simulate a bunch of bats flying around, but they don't have a bunch of bats (or don't want to set them loose on everybody), they can use boids. What a coincidence, that's exactly what Michael Keaton's Batman needed!
They actually used Reynold's boid algorithm here to simulate the bats you just watched. At the time, more complex simulations didn't really give the desired effect within the timeframe or computational limits common in that era. Boids were an obvious choice here because they are quite scalable and rather inexpensive computationally. So, let's get into how we could implement these boids in a computer simulation.
How do Boids Work?
As I mentioned before, the boid algorithm works by taking a group of individual agents and applying simple rules to each one of them. More specifically, these 3 rules:
- Separation: each agent will avoid collisions with its neighbors. This parameter can be altered to change the distance each agent will try and maintain from others.
- Aligment: each agent will attempt to match its velocity (both magnitude/speed and direction) with nearby flockmates. This parameter can be changed to set how quickly the agents will incorporate the new velocity.
- Cohesion: each agent will try and jostle for position to the center of the flock. This is what gives the flocks their characteristic "bulbous" shapes.
With just these 3 rules applied to each agent, we get the boid algorithm. It really is that simple. But for this to be helpful in any of the applications I mentioned before, our swarm has to not only behave like a swarm, but also avoid objects in its environment. It turns out solving this problem in a computationally efficient way uses some shockingly simple concepts implemented in clever ways. But, to give an intuitive view of the math behind how all this works, I'd like to start off in 2 dimensions.
Obstacle Avoidance in 2D
To avoid an obstacle, our boid first needs to "see" it. We can accomplish this by casting a number of rays from the center of the boid, and checking if any of those rays collides with an object. That way, our boid can select any of the valid paths which do not have an obstruction. We still need to figure out how to distribute these rays efficiently so that we don't have any blind spots or areas that have a bunch of rays. Since all of these rays are relative to a single origin point, and are cast out around that point, we'll benefit greatly from shifting our perspective to polar coordinates.
[POLAR PIC]
In normal Cartesian coordinates, we have two components that define each point: an x that tells us how far horizontal the point is, and a y that shows how far vertical the point is in the plane. Polar coordinates instead give us an r that tells us how far out from the origin the point is, and a theta that gives us an angle (relative to some 0 degree angle) which the point is at. We can think of Cartesian coordinates as existing in a rectangular plane, and Polar as a circular plane. We'll also begin to think of each ray as a point, since each ray is just a line between the origin and some end point. We can utilize this new system to help us come up with some ways to efficiently and equally distribute rays so that our boid can finally see. An obvious approach would be to divide 360 degrees by the number of rays to define a turn radius. Then we can place our first point, increase theta by the turn radius we just defined, and then place the next. Once we've placed every point, we're guaranteed to have maximally equal coverage of the circle and an equal amount of distance between each point. So why not take this approach? Unfortunately, it doesn't apply well to 3D. So, we need to come up with a strategy that's similar in computational cost, and allows us to place an arbitrary amount of points while maintaining good coverage of the circle.
Instead of changing our turn radius based on how many rays we'd like to place, we can actually define a constant turn radius. With a constant value, we'll need to make sure that two points are never placed in exactly the same position. A good choice for this is an irrational number that has a non-repeating decimal expansion. All that means is that if we are to represent an irrational number as a decimal, we can always choose a sequence of digits within that expansion that we will never see again. For example, 1/3 is irrational, however its decimal expansion is 0.333333 etc. Since the digit 3 keeps repeating over and over, this is a repeating decimal expansion. Whereas a number like pi has a decimal expansion of 3.1415926535 etc. Or a non repeating sequence. If we're choosing an irrational number, why not choose the "most irrational": the golden ratio (phi). For a more in depth explanation on why phi is the "most irrational" number, check out this great article. By multiplying 360 degrees by phi, and defining this as our turn radius, we can place an infinite amount of points around our circle, and we'll never have overlap. Even better, if we place a decent number of points, we actually get pretty nice coverage around our circle!
Great! So now we can place an arbitrary number of points in a computationally efficient manner, while maintaining our circle coverage criterion. Let's take our first step towards applying this to 3D: evenly distributing points on the surface area of a circle, rather than the circumference of a circle.
Evenly Distributing Points On a Disk
To accomplish this, we need to think back to our definition of polar coordinates. So far, we've only concerned ourselves with theta, or the turn radius, while r has remained constant (since we've just been placing points on the outside circumference of a circle). But, if we are to cover the entire surface area, r will need to change. An obvious solution to this it to divide the radius of the disk by the number of points we're placing and define that as the radial fraction. We can visualize this change in r below.
[VARYING R SLIDE]
This guarantees the last point will be placed exactly at the edge of the circle, and each point will have an equal difference in r compared to the previous. Fantastic, this is exactly what we wanted! However, this leads to a strange undesirable clumping of points in the center of the disk (shown below).
At first, it may not be entirely obvious why this is the case. After all, if every point is an equal r away from its neighbors, why is it so heavily weighted towards the center? Let's take a look at an example to clarify things. In the figure below, we have 3 arcs of varying radius and we're placing 10 points along each. You can see the first point on each falls perfectly along its respective arc, and each proceeding point moves a constant distance away. So, we can verify the point placement follows the method outlined above. However, we can also see a little more clearly now that it doesn't matter how large or small the circumference of a circle is with this point placement method, leading to the 10 points on the small arc being much closer in distance than the ones on the large arc. This is what generates the clumping in the figure above. Getting into the math behind this, it's because the circumference of a circle is proportional to r, not the rate of change of r.
[3 ARC FIGURE]
So, what we have right now is even-radius spacing, and what we actually want is even-area spacing. To accomplish this we can borrow a helpful tool from probability theory called sampling the inverse cumulative distribution function. Essentially what we're doing with this new concept is maintaining our desired distribution (points being placed evenly across some metric) and applying it to its integral; in our case (r2 instead of r). Note that we want the integral of r since that will give us the space under the curve of the radius function, or the surface area. If this still doesn't quite make sense, you can think of this as the relationship between the equation for the circumference of a circle and the surface area of a circle. 2πr and πr2. Note, that the surface area function is the integral of the circumference. Solving for r in our new even radius spacing term, we just have to square root the r term of the original method.
[NEW R TERM]
Utilizing this method to generate points around a disk gives us a really nice distribution.
Now that we've accomplished this even distribution on the surface area, we can move on to applying this to a sphere!
Distributing Points on the Surface of a Sphere
Our previous examples used only two dimensions, so we'll need to adapt our polar coordinates to handle a third. We'll introduce a new term called the azimuth.
[AZIMUTH]
In 3 dimensional polar space, r and theta remain the same as 2D, but the azimuth tells us how far down from the pole (top) of the sphere a point is. With this new dimension, we can begin applying the previous disk method to find our even distribution. Since we're distributing points along the surface area of a sphere, r remains constant and we instead vary the azimuth (and theta like before) to place our points. We follow the same procedure as before, except we find an even azimuth spacing instead of even r spacing. Then we again take the inverse CDF of our distribution to get an even area spacing of points. For a more detailed dive into the math and actual processes involved in making these calculations, check out this great Stack Overflow answer on the topic. Applying our new distribution we get our desired final result!
Something we can see in the disk method and sphere are those spiral patterns our eyes naturally pick out, which are characteristic of the golden ratio. These are of course a result of us using phi as our turn fraction. Even more interestingly we can actually quantify these spirals in our algorithm. Let's take a term from the Fibonacci sequence, say 21. If we highlight every 21st point placed, the selection will form one (or multiple) of the spirals we see in these point distributions. Another thing to note is that using the golden ratio for point distribution is not a novel idea. The original application is the Fibonacci lattice, which uses an incredibly similar procedure to distribute points evenly in a unit square. In fact, the disk and sphere distributions we made are actually just projections of this lattice.
Bringing it Back
After all that math, let's not forget what we were distributing these points for. By casting a ray from the center of the boid to each of the points on the sphere, we have complete 3 dimensional coverage for obstacle detection. In other words, our boid can now see! Applying this to our original boid algorithm, each agent will maintain the vector it calculated based on the three rules until the ray cast out along that vector would result in a collision. If it detects a collision, it updates its vector towards a valid ray with priority over the alignment rule, so that it does not crash. Implementing the obstacle avoidance yields our final simulation result!
In summary, the boid algorithm shown above is an example of swarm behavior simulation. We implemented only 3 simple rules to each red arrow and let the flocking emerge just by the nature of how those rules interact with each other. The simplicity of the rules and obstacle avoidance makes this algorithm a great choice for computational efficiency, allowing scalability in the number of agents that can be present in the simulation. All code for my implementation of this project can be found in my team's github repo for it. Thanks for reading, and stick around to check out some of my other projects!