Boids

Boids as described on cornell.edu

Boids is an artificial life program that produces startlingly realistic simulations of the flocking behavior of birds. Each "boid" (which is an abbreviation of "bird-oid object") follows a very simple set of rules. These rules can be summarized as follows:

Separation: boids move away from other boids that are too close
Alignment: boids attempt to match the velocities of their neighbours
Cohesion: boids move toward the center of mass of their neighbours

Bird icon created by Mihimihi - Flaticon

Code

All the code for this project can be found on GitHub.

Project description

In this project I've tried to program my own boids. Some math aspects were inspired by the article mentioned in the introduction but modified to fit my requirements. I've also extended the boids obstacle avoidance behaviour in a realistic albeit not computationally efficient way.

For the project I've heavily used object oriented programming.

Any simulations shown inside text can be clicked on to open a fullscreen view.

First simulation

For my first attempt everything is done using vectors. As an example separation loops over all nearby boids and adds a vector from the current boid to the other boid to a sum. The vectors magnitude is resized proportionally to the amount of nearby boids and by some factor. This separation force is then simply added to the boids velocity. Cohesion and alignment work in a very similar fashion. Steering away from the edges is done by adding a vector which points away from the wall to the velocity if the boid is within a certain margin of the edge. This means that the boids can leave the confines of the screen for a short period of time but it is very effective at keeping them inside the screen.

I've extended this type of boid to create a few slightly different simulations:

Normal boids: The first boid simulation I made and the one shown here.
Small boids: The boids are "smaller" which means their perception range is shorter and they appear to fly slower. This means they form a few small flocks on the screen.
Big flock: This simulation uses the small boids but with a perception range that spans over the entire screen. They form one big flock in the screen. The intricacy here is that they always tend to form a circle where half the boids rotate in one direction whilst the other half rotates in the other direction. This sort of behaviour is not very reminiscent of birds but might show good behaviour for a school of fish.
Grid: By organising the boids into grid cells the size of their perception range radius I can ensure that the only other boids which one boid can see are in its cell or the 9 adjecent ones. For larger simulations with much smaller boids this is a big optimization. Granted the simulation looks way worse and the individiual flocking behaviour is almost impossible to see. That's why I stuck with smaller simulations with larger boids. I kept using the grid however since it abstracted some code away which I needed for each simulation.
Circular obstacle: For this simulation I made the boids steer away from the obstacle in the center if they are heading straight for it. This resulted in the most realistic looking obstacle avoidance but it can happen that boids get pushed into the obstacle. This is usually the case if the boid is flying close to a tangent line and gets pushed into it by separation forces.

Obstacle avoiding boid

Boid with its vision rays

For this simulation I wanted the boids to steer away from obstacles instead of just adding a vector away from the obstacle to their velocity. This could intern be extended so the boids see each other as obstacle and also steer away from each other. To start things off I gave each boid vision rays as seen in the image. Those rays would then need to find intersections with other lines on the screen. I wanted these other lines to be normal lines and circles. For the line on line intersection I tried calculating the formula myself and got very close to getting it to work. However there was a small bug left and for the life of me I couldn't figure it out. So I ended up using the formula I found on Wikipedia. With that I had line-line intersections working. You can check it out in this demo. For the line-circle intersection I went straight to the internet and found a nicely working formula on wolfram.com. Here's the demo for that. When a boid detects an obstacle on one of its rays it steers away from it. Like mentioned above I wanted to treat each boid as an obstacle in circular shape. However this turned out to be horrendously slow as each ray of each boid had to check if it intersected with each other boid in its near vicinity. This approach turned out well-ish to confine the boid in the screen. If the boid steered with about a 45° angle onto two line obstacle in a 90° angle it could wiggle its way out of the screen. This is shown in the video.

To fix this I smoothed out the edges by adding a third obstacle in each corner such that an isosceles triangle is formed. This however further decreased the performance as each ray now had to check double the obstacles for collisions. The solution was pretty effective at keeping the boids within the screen except for some rare edgecases where they got pushed out by other boids. As this simulation is so expensive to run I have not embeded it, but you can find it here.

Predator - prey simulation

As my last simulation I've descided to add a predatory boid to chase the other prey boids. My goal was that the predator chases the boids until they are forced to split up their flock whilst trying to avoid the predator.

The predators are stripped of all their flocking behaviour and follow only one goal: To steer towards the center of mass of the prey boids they can see. Predators have a hunger parameter which increases by 0.05% each timestep. If that hunger parameter reaches a value of 100% they die. They can lower their hunger meter by 25% by killing and eating another boid. To do that they must come close enough to a boid for it to be within their killing range. A predators speed and ability to quickly change direction increases as they get hungrier.

The prey try to steer away from the nearest predator they see whilst keeping their flocking behaviour.

After tweaking some parameters I had a decent looking simulation where the predator is sometimes able to cleanly split the flock of boids. In this simulation I only have one predator and if he happens to die the simulation gets reset after five seconds.

As the predator always steers towards the gravitational center of nearby boids it usually is very indecisive and killing a boid rather depends on luck. To mitigate this I added a targetting range. If a boid gets close enough to a predator the predator will start targetting that boid on solely steering towards its position. Targetet boids are drawn in green. Additionally predators only target boids if their hunger meter is above 25%. You can find this simulation here.