Boids algorithms were used in Giant Squid Studios’ Abzu to create a beautiful tornade of fish.Boids are a type of flocking algorithm developed by Craig Reynolds in 1986. Boid stands for bird-oid object, signifying how it has been used to realistically represent flocks of birds or schools of fish without any special intelligence and easily translatable, standardized behaviours. The simple algorithms behind Boids are what make them the best option for performant flocking simulations, with applications in both movies and games. Boids work for both 2D and 3D applications.
Real World Applications of Boids
Using Boids as an automated process in animation as opposed to mimicking and manually creating real life swarms was a massive step forward. The most in-depth implementation of boids in modern video game was in Giant Squid Studios’ underwater explorer Abzu. Abzu used a combination of highly performant shaders and an enhanced version of the boids algorithm to bring thousands of fish to life at once, accurately recreating massive real life bait balls. Boids have also been used by Disney in the 1994 animated movie The Lion King to simulate both herds of wildebeest and birds overhead, creating the iconic stampede sequence.
The buffalo stampede sequence in the Lion King combined boids and a custom art style to portray the scene’s mass panic.Boids are so special because of their ability to adapt to realistic situations with simple algorithms, including fear and attraction, which allows them to be used for accurate predator-prey simulations.
The Big Three of Boids
Despite the perceived complexity and dynamic actions of boids, they are mainly driven by three simple forces: seperation, alignment, and cohesion. Additional rules can be added for more dynamic behaviors such as fleeing and gathering in specific locations.
Setting up a Boids Simulation
Boids rules should be called after they are instantiated in a loop. For example, in a 3D simulation, boids can be placed in random points in a sphere and encapsulated in an array populated with all Boid classes.
Using Boids Rules
Once a loop has been setup, likely in the same rendering loop used by default and called at the same time as the other operations, the boid’s behaviours can be called following the pseudocode example below. This will work in any game engine or framework with proper vector support and a rendering loop.
Boids[] // this is a global variable accesible in other methods
Update()
FOR b in Boids
vector1 = rule1(b) // Boids flock to the center of mass
vector2 = rule2(b) // Boids avoid other boids
vector3 = rule3(b) // Boids try to match the speed of other boids
// additional rules can be added directly after
vector4 = rule4(b)
vectorX = ruleX(b)
finalVector = vector1 + vector2 + vector3 ... + vectorX
b.velocity += finalVector // Adjust direction and speed
b.position += b.velocity // Update the position to the new positionRule 1 — Flocking Towards a Center
The center of mass can be found by averaging the positions of every boid in a flock. Ot provides a general area for the boids to orbit around and interact in, helping keep them together and form the tight flock formation in certain areas. Vectors for every function are used as offsets rather than directly added calculations, because they are calculated frame by frame rather than as a single call.
centerOfMass() // A general rule for finding the overall center
Vector result
FOR b in Boids
result += b.position
result /= Boids.length
RETURN resultHowever, since boids are representative individual entities in a flock, they don’t account for their own position when finding a center. Instead, they look for the perceived center of mass. The perceived center of mass can be found by ignoring the boid at the current index in the array amd accounting for its relative position by subtracting it, as shown in the pseudocode below. Once we find the perceived center, we want the boids to go towards it slowly. For example, we can move 0.5% towards the perceived center when the update method is called each time. synchronize this with the framerate of the device for the best results, with higher frame rates looking smoother.
rule1(Boid b)
Vector pC = <0, 0, 0> // Number of dimensions can change
FOR b2 in Boids
IF b != b2 // Ignore duplicate boids
pC += b2.position
pC = pC / (Boids.length - 1)
result = (pC - b.position) / 200 // 0.5% towards the percieved center
RETURN resultOptimizations
This code can be optimized quite easily. By initially calculating the overall center of mass and the length of the array — 1 and caching them, then they can be used as a starting point for every iteration in the loo. Instead of having to recalculate the center of mass, subtract the position of the initial Boid b in each iteration to improve performance.
Rule 2 — Avoiding Other Boids
This rule is used to prevent the boids from overlapping each other. Since normally boids represent real-world objects, it wouldn’t make sense for them to be going through each other, so this method makes boid steer clear of other boids. This method requires a given distance necessary to avoid other objects. For example, in Abzu fish stay about 1 meter from each other. However, in 2D applications of boids this will be affected by resolution when vectors are not used.
rule2(Boid b)
distance = 100 // Threshold of distance between boids
result = <0, 0, 0>
FOR b2 in Boids
IF b != b2 // Ignore duplicate boids
IF dist(b.position, b2.position) < distance
result -= (b2.position - b.position)
RETURN resultKeep in mind that this applies to not one boid, but two poids next to each other, since they are both the same distance away from each other. So in reality, they’ll be pushed in two opposite directions rather than a single push. This could affect the distance threshold you’ve set. The tighter you want your formation, the lower the distance threshold should be.
Optimizations
This method is already fairly well optimized, as caching variables once for multiple uses isn’t significant here. However, making sure that checks are efficient is important. For example, checking if 2 boids are equal can be made faster by assigning each boid an index value, such as their position in the array and comparing those. This also saves time for a programmer’s checks.
Rule 3 — Matching Boid Velocities
Rule 3 is similar to the first rule except it is centered around velocities instead of the boids’ positions. This time we calculate a perceived velocity, the same way we calculated a perceived center in the first rule. Just like the second rule, this requires a value to increment how much the speed should change in order to take steps to matching other boids’ velocities. I decided to divide by 10, so the boid will take 1/10th of the entire step necessary to match the velocity of the other boids.
Boids[] // this is a global vairable accesible in other methods
Update()
FOR b in Boids
vector1 = rule1(b) // Boids flock to the center of mass
vector2 = rule2(b) // Boids avoid other boids
vector3 = rule3(b) // Boids try to match the speed of other boids
// additional rules can be added directly after
vector4 = rule4(b)
vectorX = ruleX(b)
// limiting speed after all changes to velocity
finalVector = vector1 + vector2 + vector3 ... + vectorX
b.velocity += finalVector // Adjust direction and speed
b.position += b.velocity // Update the position to the new positionSometimes this velocity is calculated only to nearby boids, by checking the distance the same way as is done in the second rule and comparing it to a threshold value. This can be useful for multiple sub-schools of fish or other more segregated behaviors.
Optimizations
Just like in the first rule, the overall average of velocity can be calculated directly in the method, rather than in every iteration of the loop. Once again, because these loops aare nested every additional operation is a squared increase, which is important for boids due to the generally high number of members they have.
Final Pseudocode
Putting these three steps of the boids algorithm together yields the following pseudocode, which includes all the basic steps starting from the rendering loop (or some other call) and moving through the first three steps.
Boids[] // this is a global vairable accesible in other methods
Update()
FOR b in Boids
vector1 = rule1(b) // Boids flock to the center of mass
vector2 = rule2(b) // Boids avoid other boids
vector3 = rule3(b) // Boids try to match the speed of other boids
// additional rules can be added directly after
vector4 = rule4(b)
vectorX = ruleX(b)
// limiting speed after all changes to velocity
finalVector = vector1 + vector2 + vector3 ... + vectorX
b.velocity += finalVector // Adjust direction and speed
b.position += b.velocity // Update the position to the new positio
rule1(Boid b)
Vector pC = <0, 0, 0> // Number of dimensions can change
FOR b2 in Boids
IF b != b2 // Ignore duplicate boids
pC += b2.position
pC = pC / (Boids.length - 1)
result = (pC - b.position) / 200 // 0.5% towards the percieved center
RETURN result
rule2(Boid b)
distance = 100 // Threshold of distance between boids
result = <0, 0, 0>
FOR b2 in Boids
IF b != b2 // Ignore duplicate boids
IF magnitude(b.position - b2.position) < distance
result -= (b2.position - b.position)
RETURN result
rule3(Boid b)
Vector pV = <0, 0, 0> // Number of dimensions can change
FOR b2 in Boids
IF b != b2 // Ignore duplicate boids
pV += b2.velocity
pV = pV / (Boids.length - 1)
result = (pV - b.velocity) / 10 // 0.5% towards the percieved center
RETURN resultLimiting Boid Speeds
The use-case for your boids likely does not expect them to be able to move instantaneously from one point to another. In order to prevent this affect, we can limit the speed without affecting its direction. This requires another variable for the maximum velocity you’d like to set, which is equal to the maximum magnitude of the velocity you’d allow. I decided to set mine to 0.033, or 2/60. Since the max speed I want an object to move is 2m/s, and there are 60 frames in one second on most devices, I divided the maximum move value to be equivalent to the movement in one frame. Keep in mind that this should be done after changes to the velocity are made, which would likely be after all steps are completed.
limitSpeed(Boid b)
Double maxMag = 0.033 // note this is a double, not a vector
IF magnitude(b.velocity) > maxMag
b.velocity = (b.velocity / magnitude(b.velocity)) * maxMagOptimizations
This is another fairly well-optimized calculation, but to reduce the number of variables you can increase the scope of the maximum allowed magnitude to be outside of any loops in order to ensure it doesn't have to be instantiated every step of the loop. Limiting velocity does not require a nested loop, since it is independent of other boids, so this will not have as significant of an effect on performance as making changes in steps 1 and 3.
Other steps can be taken to improve the Boids algorithm or make it adhere better to your goals, which I will talk about in my successor to this article. Some of the things I talk about are predator-prey relationships, moving towards goal-points, and limiting the boids to certain areas.