The was birds flock is one example.
For a long time, birds’ flocking behavior was a mystery.
Some even thought that flocking could not be easily explained with current science.
However, careful study subsequently showed that it was, in fact, very simple.
Craig Reynolds, introduced a system known as “boids” that could simulate something similar to birds’ flocking behavior.
His model of artificial life followed three simple rules:separation: steer to avoid crowding local flockmatesalignment: steer towards the average heading of local flockmatescohesion: steer to move towards the average position (center of mass) of local flockmatesWith only the above rules you can see emergent complexity arise out of almost nothing.
Implementation in PythonBecause we want to see the results, we have to use a library that can take care of graphics.
The library I am using is p5 — a python library based on the original js library.
You can use other libraries as well.
There is a nice Youtube tutorial on this which I will try to follow and implement in Python.
First, we need to install p5:pip install p5Then we need to create some “boids” as our birds.
We will refer to these as boids rather than birds because birds are just one possible model — they could be fishes or any other flocking pattern.
For this purpose we create a class:It’s clear we need a position for each boid, so we create another file named main.
py and put the graphics handling there.
In p5 we have two important functions: setup which prepare the canvas and runs just once at the beginning and the function draw which runs in a loop and is responsible for changes that create the final animation:If you run the code above you should see an empty canvas with defined size and color.
In draw we do the same thing every time: paint the canvas with the defined rgb color.
There is no animation yet.
Now we want to create lots of static boids on canvas.
I add the function show to the class above:the stroke function determines the color of stroke and the circle function create a circle in the defined position with a defined radius.
Now, let's go back to main.
py to create 30 boids with random positions:Notice that the random.
rand generates random numbers.
We now have something similar to this plot:Now, if we want those dots to move, we need to define their velocity and acceleration.
If you remember high school physics you will know that velocity and accelerations are vector objects.
The good news is you don’t need to define the Vector class because p5 has already implemented it, with all its methods and attributes:And another function that updates the values:So, we need to add this to main.
py:the outputs of this step would is a lot of boids that fly around randomly and disappear:How do we keep them inside the box?.We have to make the box the whole world, so whenever a boid leaves the box it reappears on the opposite side.
To do that we have to add another function to boids.
py:After adding that function, this is the output:You can see that the boids start slowly and then they kind of go crazy.
We want smoother movements.
To do this we have to normalize the vectors and create a max_speed limit to them.
In the following code snippet we set max_speed to 5:This is the result:This looks good!.Now it’s time to add behavior to the flock, instead of leaving them floating randomly.
We know from mechanics that the thing that changes speed is called force and that force is equal to acceleration times mass.
We can use acceleration instead of force here.
On the other hand, we have said that every boid just sees the local boids around it.
For alignment we look at local boids and calculate their average direction (which is part of the velocity vector) and follow that.
In the figure above the green boid is the current boid.
The direction of the current boid is shown with the green vector, but the average direction of local flockmates is shown by the blue line coming from it.
We have to exert a force from the current direction, towards the desired direction.
That vector is shown by the the red arrow — the subtraction of the other two vectors:steering = avg_vec — self.
velocityThe algorithm goes as follows:Notice that in the loop for all the boids, we only look for boids at a certain distance — that distance we call the perception (here it is equal to 100).
This makes sense, because in the real world birds only see local flockmates and steer based on local information.
We also have to be careful if a boid is alone to ensure it doesn’t do anything (total>0).
Then we normalize the vector, because we just want the direction, and multiply it by the max_speed.
Finally, we do the subtraction.
We also create another function, apply_behaviour, which is responsible for applying every rule as we proceed:Then we add it to draw function in main.
py:From now on we don’t change anything in main.
py anymore.
The result:It’s looking great so far!.But we have more to do.
Cohesion means steering towards the center of mass of local flockmates.
We do this to force boids to stick close to each other and not divide.
We have to try to force the current boid (the green one) towards the center of mass of local boids — as shown by the the green dot.
Because all the boids are of the same mass, the center of mass is equal to the average position of them.
After finding the center_of_mass we subtract position from it.
In other words:vec_to_com = center_of_mass — self.
positionsteering = vec_to_com — self.
velocityThe function would be similar to alignment:We carry out normalization twice in the code above — once for the vector towards the center of mass and a second time for steering.
Again, we do this because we want direction, the controlling of magnitude should be done by another parameter (here max_speed and max_force).
Now we add the cohesion function to theapply_behaviour function, but we want to see it without the alignment rule:This is what happens if we set the max_force to 1 and max_speed to 10:As you can see, the boids try to stay close to each other, which is exactly what we were expecting.
Now it’s time for the last rule: separation.
Separation is needed so our boids don’t fly into each other and crash.
Each boid should see their own local flockmates and steer away if they are too close.
There is just one subtlety: we want the boid to steer away more from closer boids, compared to distant ones within their view (the circle).
More force is exerted by the closer ones.
We need to use the law of inverse distance :As you can see, in the main loop we keep track of distances and divide the diff vector — the direction of escape — by the distance to that particular flockmate.
If we just add this rule we have:You can see the desire of each boid to steer away as much as possible from all others — as if they don’t like to socialize!Throughout this piece I have used force and acceleration interchangeably.
Now we can apply all the acceleration at the same time using the law of force adding:So we just use vector adding:This is the net result of applying all these rules:This is what I was looking for!.There are a few things to mention.
This is not the behavior of real-world birds in full.
This is an artificial life creation that tries to simulate a real-world phenomenon and demonstrates how real systems can follow simple rules, yet exhibit complex behavior.
The boids show us that complexity can emerge from the self-organization process.
There is something different in this kind of programming: you don’t determine what kind of patterns show up.
Of course, you can tune the parameters to see different classes of behaviors but ultimately the system results in unique patterns.
It is an interplay between rules and randomness.
One technical detailIf you run the codes you will realize it’s very slow when the number of boids is more than 50 (depending on your hardware).
The reason is obviously that the code is inefficient and has a complexity of O(n²) which is very slow in terms of computer science algorithms.
You probably realize that there is no need for each boid to inspect all other boids, so the algorithm can be optimized by dividing the space.
It’s similar in nature to the problem of optimizing the knn algorithm.
You can find some remedies here.
I tried to use Ray library to parallelize the rules but it did not make a huge difference.
You can see it in my GitHub repo.
If you find any solutions that makes major improvements to the speed, send a push request to me!.. More details