I first came across Boids algorithm when I was in grad school and was given this as an extra credit project to be implemented on iOS. I implemented it, but it was quiet buggy. And being a grad student I was too busy to work on extra credit on a course I knew I’d get an A in. So naturally, I didnt pay attention much back then but this algorithm is such a beauty! Its simple yet produces amazing results! I’ve been thinking about implementing it again for a long time, and when a youtube video of the simulation came across my feed this week, I knew I wanted to implement this as my weekend project!
Boid is shoert for bird-oid object and boids algorithm is basically a way to mimic how birds and other animals which go in flock move. Fun fact the gallimimus dinosaurs flock in Jurrasic Park was actually simulated using this algo!
Without adue lets get to simulating it in Unity! Now I’m not going to describe the algorithm since there is plenty of info out there that you can find about it, but I will give a brief overview of how I’m using it. Once we are done our output will be like this!:
Lets create an empty Unity project, for now we will make this a 2D version, and later update it to a 3D one. Our algorithm needs :
- Boid – individual free moving game objects
- Brain – control how flock should move depending on modifiers
- Modifiers – modify the path of each boid depending on certain factors, sample modifiers:
- Coherence – what is the target of each boids trajectory – usually the center of mass of the flock
- Seperation/Collision – boids too close together will try to move away from each other
- Velocity match – boids try to match each others velocity
Boid
To make a boid graphic, create an empty gamebject and create a sprite as a child to that gameobject. Assign this as sprites target image. Having sprite as child lets us have control over graphic.
Create a new script called Boid.cs and attach it to the boid game object. Now each boid has a direction in which it is moving and speed at which it is moving. Lets create variables for that. I’m also creating a position vaiable which will return boids 2D position(x,y), this will come in handy later.
Since each boid has different speed, lets create a common speed multiplier variable that can be used to speed up all the boids at once.
public class Boid : MonoBehaviour
{
//speed in mps
public float speed;
//move direction of the boid
public Vector2 direction;
//seed up all the boids by a factor
public static float speedMultiplier = 1;
//get position
internal Vector2 position {
get {
return new Vector2(transform.position.x, transform.position.y);
}
}
}The boid movement each frame can be computed as such in the update method.
void Update()
{
transform.Translate(new Vector3(direction.x,direction.y,0) * speed * speedMultiplier * Time.deltaTime, Space.World);
//sets the graphic to point the direction it is moving
//the x direction is aligned with arrow point direction
transform.right = direction;
}If you save the run you should see the boid move in direction specified at speed specified. Now lets add code that can modify the velocity and speed.
public void AdjustVelocityBy(Vector2 targetVelocity, float bias) {
direction = Vector3.Lerp(direction, targetVelocity, bias);
direction = direction.normalized;
}
public void AdjustSpeedBy(float targetSpeed, float bias) {
speed = (speed * (1 - bias)) + (targetSpeed * bias);
}We are adjusting velocity of the object using a bias, if bias is 0 we do not modify the velocity at all, if bias is 1 we completely ignore the current velocity of the boid and instead set target velocity as new velocity. Anything in between is interpolated from one vector to other. Similarly for speed we interpolate between boid speed to taget speed.
Thats it for boid! We are done! Well, for now. There is one last piece of code we can add in there later that will help in collision detection.
Modifiers
Alright, lets get to modifiers. Each modifier will output a target that it needs the boid to move to. Lets start with coherence!
Coherence
public class Coherence : MonoBehaviour
{
public BoidsBrain brain;
public GameObject coherencePointVisual;
Vector2 sumOfAllBoidPositions;
// Update is called once per frame
void Update()
{
sumOfAllBoidPositions = new Vector2();
foreach (Boid boid in brain.boids)
{
sumOfAllBoidPositions += boid.position;
}
}
public Vector2 GetCoherence(Boid currentBoid){
Vector2 centerOfMassOfBoidsEceptCurrentBoid = (sumOfAllBoidPositions - currentBoid.position) / (brain.boids.Length - 1);
coherencePointVisual.transform.position = centerOfMassOfBoidsEceptCurrentBoid;
return (centerOfMassOfBoidsEceptCurrentBoid - currentBoid.position).normalized;
}
}As you can see coherence is pretty simple, every frame we calculate center of mass of all the boids, calculate the vector from current boid to the center of mass and thats it!
Here, to calculate center of mass each frame, I am summing up the positions of all the boids and storing them. Then, for each boid, coherence vector is calculated by simple substracting the current boids position(we dont want that for Center of Mass calculation, we only want center of mass of every othe boid.) from the sum of all postions and divinding it by (number of boids – 1). That is what we get on get coherence.
Collision
This modifier keeps boids from bumping into each other and into unwanted objects like walls. I’m going to call avoiding other boids as soft collision avoidance and avoiding objects as hard collision avoidance. The aim is to avoid objects at all cost but avoiding other boids is okayish!
For soft colissions, each boid needs to check if there is another boid in the direcion it is moving, if there is try to avoid it by modifying direction as little as possible. Now to “modify the direction a little”, I’ll create a set of vectors in object space of the boid that it can move towards. Ex:
The numbers show precendence in which I want the boid to move if the given vector has a collision. i.e. if vector 0 has a collision try vecor 1 if that has a collision too try vector 2 and so on.
To calculate this wheel of directions, lets go back to Boid.cs and calculate these vectors once in start and we can use them in colissions.
public int numberOfPathsToCreate;
internal Vector3[] possiblePathVectors;
// Start is called before the first frame update
void Start()
{
if(numberOfPathsToCreate % 2 == 0) numberOfPathsToCreate++;
possiblePathVectors = new Vector3[numberOfPathsToCreate];
possiblePathVectors[0] = Vector3.right;
float piFraction = 1.618033f;// 1 / (float)numPaths;
float piStart = Mathf.PI / 2;
float angle = 0;
for (int i = 1; i < numberOfPathsToCreate; i+=2) {
angle = piStart + (Mathf.PI * piFraction * i);
possiblePathVectors[i] = new Vector3(Mathf.Sin(angle), Mathf.Cos(angle), 0);
angle = piStart - (Mathf.PI * piFraction * i);
possiblePathVectors[i+1] = new Vector3(Mathf.Sin(angle), Mathf.Cos(angle), 0);
}
}
[Everything in this section is being done in object space of the boid]
Here we first add forward direction of the boid to our possiblePathVectors as we dont want to change directon if there is no collision. Then we add a fraction of pi to calulate vecor 1 and substract the same fraction to calculate vector 2. the fraction is incremented periodically and we get our vectors list in object space.
Now going back to collions to avoid soft collisions we simply do this.
public Vector2 GetSoftColissionAvoidance(Boid current)
{
//for each vector in Possible path vectors
foreach (Vector3 directionVector in current.possiblePathVectors)
{
//raycast for obstacles
if (!Physics.Raycast(current.transform.position, current.transform.TransformVector(directionVector), collisionRaycastDistance))
{
//if no obstacle
// move vector = vector
return current.transform.TransformVector(directionVector).normalized;
}
}
// no way to go
return new Vector2();
}Iterate over available vectors and return the first vector that doesnt yield a collision! And done with that!
For hard collisions its very similar but one more thing we must calculate is how close to a collision we are and depending on that we can adjust our bias dynamically. if we are really close to collision we need bias to be 1 so it can avoid the collision.
public Vector2 GetHardColissionAvoidance(Boid current, out float bias)
{
bias = 0;
RaycastHit hit;
//if ther is hard collision in the current path
if (Physics.Raycast(current.transform.position, current.direction, out hit, collisionRaycastDistance, 1 << LayerMask.NameToLayer("HardCollision")))
{
//if collision is dangerously cloase, increase bias to avoid
bias = 1 - (hit.distance / collisionRaycastDistance);
//for each vector in Possible path vectors
foreach (Vector3 directionVector in current.possiblePathVectors)
{
//if no obstacle in direction vector
if (!Physics.Raycast(current.transform.position, current.transform.TransformVector(directionVector),out hit, collisionRaycastDistance,1 << LayerMask.NameToLayer("HardCollision")))
{
//to the direction
return current.transform.TransformVector(directionVector).normalized;
}
}
}
// no way to go
return new Vector2();
}And with that, any object with a tag “HardCollision” will be treated as impenitrable object! We are done with collision modifier!
VelocityMatcher
This is similar to coherence modifier, but instead of position, we calculate average of move direction and speed!
// Update is called once per frame
void Update()
{
sumOfAllBoidVelocities = new Vector2();
sumOfAllBoidSpeeds = 0;
foreach (Boid boid in brain.boids)
{
sumOfAllBoidVelocities += boid.direction;
sumOfAllBoidSpeeds += boid.speed;
}
}
public Vector2 GetVelocityMatchVector(Boid currentBoid, out float averageSpeed)
{
Vector2 averageVelocityOfBoidsEceptCurrentBoid = (sumOfAllBoidVelocities - currentBoid.direction) / (brain.boids.Length - 1);
averageSpeed = (sumOfAllBoidSpeeds- currentBoid.speed) / (brain.boids.Length - 1);
return averageVelocityOfBoidsEceptCurrentBoid.normalized;
}Voila! we are done with the three modifiers! Now lets use them!
Brain
Brain has very simple task, i.e. for each boid, get the modification vectors from modifiers and add it to boid!
First lets set up our code to create as many boids as we like!
public class BoidsBrain : MonoBehaviour
{
public int numBoids;
public float simulationSpeed;
public float coherence_bias;
public float collision_bias;
public float velocity_bias;
public float speed_bias;
public Coherence coherence;
public Collision collision;
public VelocityMatcher velocityMatcher;
public GameObject boidPrefab;
public Boid[] boids;
void Start()
{
boids = new Boid[numBoids];
for (int i = 0; i < numBoids; i++) {
GameObject b = Instantiate(boidPrefab,transform);
b.transform.position = new Vector3(Random.Range(CreateBounds.xMin, CreateBounds.xMax), Random.Range(CreateBounds.yMin, CreateBounds.yMax),0);
boids[i] = b.GetComponent<Boid>();
boids[i].direction = new Vector2(Random.Range(-1f, 1f), Random.Range(-1f, 1f));
boids[i].speed = Random.Range(1,5);
}
}
}Awesome, now when we run, we can see bunch of boid randomly distributed in the screen with random directions and speeds! Now lets use modifiers! In the late update add this!
void LateUpdate()
{
Vector2 coherenceVector;
Vector2 seperationVector;
Vector2 collisionVector;
Vector2 velocityMatcherVector;
float speedMatch;
Vector2 hardCollisionVector;
float hardCollisionBias;
for (int i = 0; i < boids.Length; i++)
{
coherenceVector = coherence.GetCoherence(boids[i]);
collisionVector = collision.GetSoftColissionAvoidance(boids[i]);
hardCollisionVector = collision.GetHardColissionAvoidance(boids[i], out hardCollisionBias);
velocityMatcherVector = velocityMatcher.GetVelocityMatchVector(boids[i], out speedMatch);
boids[i].AdjustVelocityBy(coherenceVector, coherence_bias);
boids[i].AdjustVelocityBy(collisionVector, collision_bias);
boids[i].AdjustVelocityBy(velocityMatcherVector, velocity_bias);
boids[i].AdjustVelocityBy(hardCollisionVector, hardCollisionBias);
boids[i].AdjustSpeedBy(speedMatch, speed_bias);
boids[i].speedMultiplier = simulationSpeed;
}
}as you can see, for each frame we simply get the modifiers output vector and user bias and adjust the boid using the two values! And we are done!
Here is what the final output looks like!
Hope you enjoyed this! I highly recomend trying it out! I have put the code in my github here : https://github.com/iamrohit1/BoidsAlgorithmUnity3D
I’m thinking about creating a game with this algo! I’ll add it in game dev section when I make it!
Thank you!