People have long been fascinated by the beautiful patterns that exist in the animal kingdom. Flocks of birds, a school of fish or ant swarms working together. How do they coordinate with each other? How does each member of the Flock know what to do? Look at a flock of swallows – they swoop and swirl and dart about – without any birds colliding and move about in a hypnotic pattern.

Ants may have a queen, but she can’t direct each and every worker from under the ground. What about a flock of birds? Some flocks have a leader, like geese, but most flocks are just that – a flock of birds without one leader deciding where each flock member has to go next. Scientists long speculated that there has to be very complex rules that apply to flocking behaviour. This seems like a great mystery – seemingly chaotic, but there has to be a pattern or recipe that one can determine and then use to model the behaviour.

Boid = Bird-Oid

The big breakthrough came in 1986 when Craig Reynolds, a artificial life and computer graphics expert, developed a artificial life simulation called “Boids”, which stands for “bird-oid”, a shortened version of “bird-like object”.  Reynolds lived in California – not far from his house was a cemetery where huge numbers of blackbirds gathered. Reynolds wondered how difficult it would be to simulate this behaviour on a computer. Being employed by Symbolics computer graphics presented him with the opportunity to put this to the test.

Reynolds reasoned that flocking behaviour might seem complex but it can be reduced to simple rules that govern the movements of each flock member. These rules are applied by the flock member, not by some queen or overlord that makes decisions on behalf of flock members.

His work was ground-breaking, since this is an example of emergent behaviour, where complex global behaviour, like flocking, can arise from the interaction of simple agents (the boids) adhering to simple rules.

Reynolds’ three simple rules are:

Separation – avoid crowding your neighbours.

Alignment – steer towards the average heading of your neighbours.

Cohesion – steer towards the average position of your neighbours.

But wait, it cannot be that simple, I hear you say. It actually is! As hard as it is to believe, when you apply these three rules to a flock of boids, complex flocking behaviour emerges and the same distinctive hypnotic pattern of a flock of birds emerges. Just as in a real flock of birds, there is no overlord making decisions for each boid after observing what is happening with the flock – each boid just applies these three simple rules. Each boid only has knowledge of its immediate neighbours. The neighbours are determined by a set distance from the boid and an angle, measured from the direction the boid is flying in. This angle is in effect the “viewing angle” of a boid – in layman’s terms, how far and wide a boid can see.

Reynolds included the idea of obstacles in the model – much to his surprise when boids encounter an obstacle, they elegantly part and avoid the obstacle, then rejoin to form a flock once they clear the obstacle. There are also rules for “predator and prey” behaviour, queueing up to go through a narrow entrance and rules for following and swarming around a pre-determined path (see the references at the end of the article)

Hollywood Adoption

A direct application of this can be seen in the silver screen. In the Tim Burton film “Batman Returns” (1992) computer generated swarms of bats and penguins marching in Gotham city delights the audience – animations created using this model. The Disney film “The Lion King” also featured a wildebeest stampede which was rendered very realistically using this model.

Even the scattering of a flock (the boids hear a loud noise, for example) is a simple application of rules. It turns out that you don’t have to apply different rules to scatter a flock. You simply negate the influence of the “cohesion rule” (rule 3) and still apply the other two rules. The effect is very realistic – the boids scatter in all directions, then after a few seconds, the flock reforms.

Drones

More practical applications also exist – the control of simple unmanned ground vehicles or drones. There has even been research done by the University of Leeds and Cologne to show flocking behaviour in humans.

Boids form part of the field of study called “artificial life”. Researchers study systems related to natural life, the processes that occur and how life changes – its evolution. This is done using computer simulations – also biochemistry and robotics. Christopher Langton is an American theoretical biologist and considered the father of this field of science. There are three different approaches: soft (for software), hard (for hardware) and wet (for biochemistry). Boids primarily fall under “soft”, but when you apply this model to drones, for example, it would also fall under “hard”. Boids also form part of “swarm intelligence” –  the collective behavior of decentralized, self-organized systems, natural or artificial.

The boids simulation has become a popular project in computer science university departments around the world to explain to students how artificial intelligence, artificial life, and emergent behaviour works.

References:

Craig Reynolds “Boids” https://www.red3d.com/cwr/boids/

Flocks, Herds, and Schools: A Distributed Behavioral Model https://www.red3d.com/cwr/papers/1987/boids.html

Stephen Levy – Artificial Life – A report from the frontier where computers meet biology (1993)

The post Boids: Three Simple Rules to Create a Computer Bird Swarm appeared first on TectoGizmo.