Nature has so much to teach us. In fact, data scientists draw inspiration from it to simulate mass behaviour. How do they do this? Thanks to the flocking algorithm. Find out how this model works, what it can be used for and how it can be implemented using Python.
What is the flocking algorithm?
The flocking algorithm was first developed in 1987 by Craig Reynolds in his article “Flocks, Herds, and Schools: A Distributed Behavioral Model”.
This is a computer model inspired by collective behaviour in nature. In particular, birds in flight and schools of fish. By observing these species, Craig Reynolds discovered that it was possible to simulate collective behaviour within a group made up of autonomous entities.
The 3 rules of the flocking algorithm
The flocking algorithm begins with the observation of flocks of birds (called ‘boids’ in Craig Reynolds’ article). Even if they are following a set direction, the birds can suddenly change trajectory. And without even a leader directing the flock. Why this behaviour?
Because birds move according to rules of avoidance (or separation), alignment and coherence. And it is precisely on the basis of these 3 simple rules that we can recreate collective behaviour:
- Cohesion: agents tend to move closer together. To form compact groups, they must move towards the average position of their neighbours, while respecting their average speed.
- Alignment: agents move in such a way as to align themselves with the average heading of their neighbours. This creates a coordinated movement within the group.
- Separation: by maintaining a certain distance from each other, they avoid collisions and the formation of dense clusters.
Modelling behaviour
By applying these three rules, we obtain a fluid grouping model. The group maintains a common trajectory. It almost merges into a single entity, even though it is made up of a multitude of mutually autonomous agents.
So for the flocking algorithm to work properly, each agent must be able to steer itself and be aware of its local environment (in particular its neighbours, the direction it is following and the distance).
Good to know: The Flocking algorithm doesn’t just apply to groups of birds and schools of fish. It can be applied to any other species that behave socially in nature, such as bees, rats, etc. or even human beings. Which means it has a wide range of interesting applications.
How do I apply the flocking algorithm?
Aimed at modelling complex dynamic systems, the flocking algorithm can be applied in a multitude of situations:
- Video games: for non-player characters (such as a squadron, a crowd of zombies, etc.), video game designers often use the flocking algorithm. This enables their behaviour to be programmed to make the game coherent and realistic.
- Drones: thanks to the flocking algorithm, they can fly in a coordinated manner, avoiding collisions and adapting to changes in the environment in real time.
- Surveillance robots: they can patrol with coherent movements and maintain effective coverage.
- Autonomous delivery systems: the flocking algorithm facilitates parcel delivery by avoiding congestion and defining optimal routes.
- Road traffic simulation: local authorities can also use the flocking algorithm to improve traffic flow. By modelling vehicle behaviour through cohesion, alignment and separation rules, it is easier to avoid traffic jams.
Whatever the field of application, the flocking algorithm brings to light complex behaviours arising from simple local interaction between agents.
How do you implement the flocking algorithm in Python?
To create a video game based on the flocking algorithm, you can already create a simulation with Python and Pygame. Here are the steps to follow:
- Install Pygame: if it is not already installed, you can use Pip.
- Import the necessary modules: like Pygame, random and math.
- Initialise Pygame: you can do this using pygame.init().
- Define the screen dimensions and colours.
- Define the flocking parameters: such as the number of entities, the maximum speed, the perception radius and the separation distance.
- Create the Entity class: this represents the entities in the simulation. For each entity, you must also define a position and a speed.
- Implement the entity behaviours: in the Entity class, update the position and velocity according to the positions and velocities of the neighbours.
- Wrap edges: implement a method for wrapping entities around the screen. When they reach an edge, they should reappear on the other side.
Calculate the distance between the entities. - Create the herd: this is designed from a list of entities. At the beginning, it is possible to initialise the entities with random positions and speeds.
- Initialise the Pygame screen: with the dimensions specified beforehand.
- Set up a main loop: the one that will run the simulation. Within the loop, you must update the positions and speeds.
Discover the flocking algorithm with DataScientest
Because of its wide range of applications, the flocking algorithm is an essential data science model. But to master it, you need to know the basics of machine learning, programming languages, databases and so on.
Hence the importance of taking a training course with DataScientest. At the end of your course, you will know how to implement a flocking algorithm to create video games or any other application requiring the simulation of collective behaviour.
