Simulating Flocking Behavior In Virtual Agents
In this article, I cover the basics of how boids , an algorithm that simulates flocking behavior, works. I then share a simple model I built using only Excel** to implement a 2-D Boids algorithm. I wrap up with a brief overview on the wider topic of swarm intelligence and a few interesting applications.
[**yes , yes— of course I could have implemented this in something more modern like Javascript or Python but being a sadomasochist I wanted to see how far I could push this within the constraints of a 30 year old programming language]
<NOTE : This article is an updated re-post of an article originally published on my Linkedin profile in June 2020 — I am doing a bit of clean-up to consolidate all my material onto Medium>
Introducing … AI : Artificial Intelligi-”ant”-ce
Aside from a chance to make truly awful puns in the section headings for this article…despite of all the hype deep learning based AI has been receiving, in this post I wanted to go back to some older (but no less interesting) techniques that were created more than 20–30 years ago in the field of Swarm Intelligence algorithms.
A lot of these are actually fairly mature in the world of computer science (In fact some of the articles in the links below date as far back as the early 2010-s era) Some examples of Swarm Intelligence are Ant Colony Optimization and Slime Mold Computing but we’ll be covering the OG example of Flocking Behavior Simulations
You may have seen my earlier posts about modelling disease contagion using an agent based model (built using only excel + vba no less)
In that model rather than using differential equations to simulate the spread of a disease, I used a rule based simulation approach where virtual agents moved around randomly infecting their neighbours.
I wanted to revisit the aspect that really interested me about agent based models, specifically how simple rule based local interactions can produce complex emergent behaviours at a global level.
What Are Boids ? (aka…Boid oh Boid are you in for a treat….)
In the 1980-s, Craig Reynolds from Stanford developed an interesting approach to simulating flocking behavior (Think flocks of birds , swarms of bees , schools of fish or even growth of microbial colonies)
At the time, most of the ‘traditional’ approaches involved some form of centralized control structure.
What was unique about the “boids” approach when it came out in the 1980-s was that it was essentially de-centralised and involved only simple local level rules.
In boids, each boid (or agent) obeys three simple rules:
- Try to move towards the average position of other nearby agents (i.e Cohesion rule)
- Try to rotate to match the average alignment of nearby agents (i.e Alignment rule)
- Try to avoid crowding by ensuring a min separation distance (e.g. Separation rule)
Developing An Excel+VBA Based Flocking Simulator
Based on the above set of rules, I heavily modified my initial “disease spread” model to instead become a “flocking simulator”.
Essentially, the trick was using the already existing piece of formulas where I had an array measuring the distance between each agent with every other agent in the simulation( I needed this to mimic the behaviour of infection spread if agents got too close to each other)
Using that , I basically set up a bunch of new arrays measuring the nearest neighbours for each agent based on a range of vision and then set up vectors to simulate the various cohesion/ alignment/ separation forces rather than letting the agents just roam about randomly in any direction as in the original model
Long story short — how it works is that you adjust the simulation by changing the relative strength between the Cohesion / Alignment / Separation factors and also add in a bit of “random-ness” to the behaviour of the flock.
Also — I know nobody asked for it but since the flocking model was built using the SEIR disease spread model, it can also model disease spread within a group of flocking animals
If you are interested in playing with the simulator I built , here’s the source xlsm file*:-
*Since VBA obviously isn’t the most efficient programming language to implement the algorithm — here’s a link to a Github repo with a Javascript based version of the Boids algorithm
How Boids Are Used TODAY
Since it was initially published, this basic approach has been extended to include many other factors such as the incorporation of object avoidance (eg. Fleeing a predator) or including a chance for individual agents to ‘escape’ the flock. (Sometimes called ‘change of leadership’ factor)
Even modern video game engines such as Unreal use this as the basis for their simulations of flocking objects (3m 49s mark in the video below in case the time marker isn’t working)
And it’s not only in videos game where this concept is used — this is also a relatively mature application in algorithms used to control UAV-s (i.e Drones):
Here’s a fairly ‘sensationalist’ account :
….and to balance it out — here’s a drier more academic article with less hype….
In Conclusion…
In this article I’ve discussed flock simulators but this is only scratching the surface of this wide and interesting topic as there is a whole range of other Swarm Intelligence applications.
Examples are as varied as:
- construction robots that collaborate by imitating termites ;
- algorithms that optimize logistic/delivery routes by mimicking how ant colonies forage for food ; extraction of image features using particle swarm optimisations ;
- ant colony optimisation algorithms to drive efficient allocation of resources amongst IoT devices (e.g. network bandwidth or computing power);
- slime molds being used as the basis for biological computers
*Phew* — If you are more inclined to watch stuff than read — I’ll leave you with this 2014 TED(x) Talk from I stumbled across while researching this topic:
…..But wait there’s more — Bonus Random Info
The music used in the second video with the Excel model is actually a really interesting piece as was algorithmically made based on the protein structure of the coronavirus
“….early part of composition has been described by several SoundCloud listeners as “soothing” and “beautiful.” Buehler said this reflects the ease of the spiked protein entering the human cell, making it so contagious”
