Simulating a Swarm Algorithm in C#

I just finished reading Michael Crichton's Science Fiction/Horror book Prey and I admit I could not put the book down. The book combines the concepts of the Swarm Algorithm with nanotechnology to create a very frightening concept( I won't go into detail, because I don't want to spoil it for the reader). What is so fascinating about some of Michael Crichton's books is that he mixes and explains real state of the art technology with his storyline. He also presents possible inventions and breakthroughs in the current technology to fill the implausible gaps of the story, the mark of a great science fiction writer. After reading the book, I decided to go out on the web and see what has been done with modeling swarms in the computer world. (There is also an impressive bibliography of papers and texts in the back of Prey pointing to references on artificial life, genetic algorithms, and intelligent agents).

Figure 1 - The Swarm Algorithm Coming to Life

In my short-lived research I found an article that embeds a java app simulating swarm behavior written by Alex Vulliamy and Jeff Cragg. Rather than reinvent the wheel, I took this code and translated it into C# to demonstrate the swarm behavior in a Windows Form using GDI+. The algorithm is exactly the same and also a fairly simple one.  In order to understand the algorithm let's first talk a little bit about the social behavior of birds in a flock.

I think we can all agree that birds are not exactly the brightest of animals (hence the term "bird-brain"), so how do they know how to fly so organized in a flock? (This question was pointed out in Crichton's book by the way).  The way each individual bird determines how he will fly is simply by seeing where its neighbors are in the flock and adjusting its velocity so as not to collide with the bird in front of it. If you put this series of simple behavior together for all birds, the combined result is birds flying in a nice formation. Another words, its not like these birds got together and said, "Hey let's form a big V, like the cheerleaders for Villanova". No, they simply rely on their neighbor to determine their behavior.

So how does this all pan out as a mathematical algorithm? Well, let's say you are a bee. You would then obey  the following rules (according to this particular program): 

1. Accelerate towards your two closest neighbors.
2. If you get too close, repel your neighbor.
3. Don't ever exceed your maximum speed (after all you are a bee, not a rocket ship).
4. If you hit a wall, reverse your direction.
5. Try to have a tendency to accelerate towards the center of the enclosed space
6. Check the proximity of your neighbors' neighbors. If they are closer, follow them.
7. Every once in a while randomly choose some other set of neighbors to follow.

That's all there is too using your limited intelligence as a bee. Just follow a few simple rules and the combined result produces an interesting effect shown in figure 2.

Figure 2 - Simulated bee swarm following each other around

The "bees" seem to follow each other around in a group in a 3D mass not unlike a real bee swarm. (Its hard to tell much from the picture because you can't really see the motion, so you'll just have to run the simulation ;-)

Below is the UML design of our simple Swarm Simulation. It consists of only two classes: the Form and Swarm3D.  The Form displays the simulation, and the Swarm3D class contains the Simulation thread, simulation rules, and the code to draw the bees inside the form:

Figure 3 - UML Design of Simulation Program reversed using WithClass 2000

The architecture goes something like this: The Form constructs an instance of the Swarm3D class and calls start to kick off the swarm simulation thread. Each time the simulation needs to update the screen with new swarm positions, it invalidates the form so it will repaint itself. When the form repaints, it calls the Draw method of the Swarm3D class.

The swarm algorithm is implemented in the run routine of the Swarm3D class shown in Listing 1 below. The listing follows all of the rules we have listed above. Most of the rules (1-5), such as follow your neighbor, avoid colliding with your neighbor, don't exceed maximum speed, and bounce off the walls are handled in the processfly method. doneighbors checks the proximity of the neighbors' neighbors and applies rule # 6. Rule #7 is handled by the randomize method in order to pick new neighbors every once in a while. 

Listing 1 - run method simulating the swarm:

The most interesting method as it applies to our swarm algorithm is the processfly method which invokes a majority of the rules (1-5) shown in Listing 2. In this method, we compute a 3D Velocity vector for the bee based on the swarm rules.  Then we add the velocity vector to the 3D position vector of the bee to determine its new position in the swarm. Note that we need to check each of the x,y, and z directions vectors against the rules of the algorithm.

Listing 2 - processfly method applying rules 1 - 4

Conclusion

The swarm algorithm may seem like a novelty, but it is actually useful for optimization problems in physics, economics, and chemistry. You can add a genetic algorithm to the swarming algorithm to produce emergent behaviors or generate "new rules" to follow in order to achieve a particular goal. Just make sure the goal doesn't exceed its boundary's as they did in Michael Crichton's unfolding tale. 

References

Michael Crichton's Prey on Amazon
Simulating Social Behavior
Alex Vulliamy's Home Page
Ariel Dolan's ALife Experiments
AI Depot