Separation: , Alignment: , Cohesion:
This example shows a fascinatingly simple algorithm called flocking. The particles below are flocking. Initially they start in random locations, however, they soon fill form groups and fly in seemingly complex patterns. You can also click (or touch) a location and the particles will repel from the location you touched.
It might take up to a minute (or so) for well established flocks to emerge. Even after these flocks emerge they will often split and recombine. To start over click "Clear". It is also possible to click "Big Bang", which uses no random initialization at all. The particles are all placed in the middle of the universe and quickly move outward assuming their "complex" patterns.
I will now explain how this program works.
The Flocking Algorithm
Flocking behavior was first simulated on a computer in 1986 by Craig Reynolds with his simulation program, Boids. Flocking seems like a very complex behavior. It is exhibited by many different animals, using many different names. A flock of birds. A swarm of insects. A school of fish. A herd of cows. All different names to describe essentially the same behavior. Some other languages also use different names for the same behavior.
Spanish is the same as English in using different words for each of these behaviors. Una bandada de pájaros. Un enjambre de insectos. Un banco de peces. Un rebaño de vacas. Todos los nombres diferentes para describir la esencia, el mismo comportamiento. Otros idiomas también parecen utilizar diferentes nombres para el mismo comportamiento.
At first glance, a flocking algorithm may seem complex. I would probably create an object to handle the individuals in the flock. I would need to define a flock object to hold flock members. Routines would need to be developed to determine which direction the flock should go. We would also have to decide how a flock should split into two or more flocks. What criteria determines how big a flock can get? How are new members admitted. You can see some real-life examples of bird flocking here.
The flocking algorithm is actually very simple. It has only three rules.
1. Separation - avoid crowding neighbors (short range repulsion)
2. Alignment - steer towards average heading of neighbors
3. Cohesion - steer towards average position of neighbors (long range attraction)
These three rules are all that it takes. Flocking is truly an example of "Simple Complexity".
I wanted to keep this example as utterly simplistic as possible, yet still exhibit seemingly complex behavior. The particles are all moving at a constant speed. Each particle has an angle that defines the direction the particle is moving. The particles cannot speed up or slow down. They can only turn.
The above three rules each specify an "ideal angle" for the particle to move towards. The desire to obey each of the three rules is dampened by a specific percent. These are the three numbers you see at the bottom. You can play with these three and see how they affect things. Many combinations will not produce flocking behavior at all. The default values I provide work well.
If you want to see the effect of one of the three rules in isolation, set that rule to 1.0 and the others to 0.0. For example, if you isolate cohesion, then you will end up with all of the particles converging to a few locations in the universe.
There is no randomness in this universe at all. Other than placing the particles in initial random locations, no further random numbers are generated. You can even click the "big bang" button, and eliminate all randomness from the system. If you click "big bang" all particles will be placed in the center with motion in the same direction. It does not take long for a complex pattern to emerge. Flocking is a great example of how very simple rules can produce very complex systems.
Other Uses for Flocking/Swarming
Flocking can also be used as an search algorithm. This allows it to be used to optimize the parameters of a system. In this way it can be used to train neural networks, Bayesian Networks, Support Vector Machines and other machine learning methods. Encog makes use of flocking in the Particle Swarm Optimization algorithm. More advanced examples of swarming will be demonstrated in future examples.
Other Observations
Flocking is a fascinating topic because it shows how a "universe", such as the program above, can exhibit seemingly complex behavior. Our own universe seems very complex. There are fields of study such as physics, chemistry, biology and others that attempt to develop models to explain natural phenomena. Scientists seek a Theory of Everything to unify all physical laws into a simple set of underlying laws. So no one has made this unifying discovery. The best we have now is a Theory of Almost Everything, or the Fundamental Forces.
The fundamental forces theory is very interesting because it attempts to explain many physical interactions in terms of four fundamental forces, or interactions. The strengths of each of these four forces are governed by universal "constants" in a similar way that flocking is governed by the three constant dampers for the three laws of flocking. Of course the real universe may not be deterministic, as stated by Bell's Theroum. At the atomic level the best we may ever get is a probabilistic outcome. Nevertheless, fitting simple rules to seemingly complex systems observed in nature is an active area of research.