Mega Flies

One area of study that greatly interests many artificial life enthusiasts, myself included, is emergent behavior. Emergent behavior is the concept that, from a few localized simple rules, highly complex group patterns of behavior can "emerge". That is, complex behavior can sort of materialize unexpectedly from far simpler rules than the resulting behavior.

One of the more popular versions of emergent behavior is "flocking." Everyone is familiar with what birds, bees, fish, and herds look like when tens or hundreds of animals are in the same place at the same time. A group behavior can clearly be seen. As one or a couple individuals turn, the entire flock follows. How can animals as simple as bees produce the appearance of a rhythmic swarm as it sweeps about in the air over a field? It is obviously too complex for them to plan and then carry out, lead by a leader bee, who directs every individual such that the proper group behavior is produced. No, instead, each bee (or bird, or fish, or whatever) only pays attention to the other individuals in close proximity to it. They follow fairly simple rules about maintaining a desirable distance from nearby individuals, not too far and not too close, and that's all that is necessary from the group to appear with an uncanny sense of unity and "oneness."

Flocking programs are in no way cutting edge technology anymore. Several such programs have been written by many people for decades, the first of whom was Craig Reynolds with his famous program Boids. All of these programs, (of the ones I've seen), animate tens or hundreds of individuals and their group behavior can be plainly seen on the computer screen. Being so complete a project, with so many flocking programs already in existence, I never bothered writing one of my own. Why reinvent the wheel, I figured.

But then I saw a nature film in which a display of a particular species of martin living on some remote river in Africa was shown. This display was exhibited by no less than 100,000, possibly 1,000,000 individuals. There was a cloud of martins so thick that the sky was hardly visible through what could only be described as a swarm. I noticed that the most beautiful patterns swept through the swarm. Shapes of darkness where the birds were more tightly packed, wispy lines of thinness, circular uprisings, tornado-like swirlings, it was all there. It was a pattern of flocking behavior, of emergent behavior, that I had not seen in any other group of animals (although it reminded me of bees, if perhaps set in slow motion) or any other flocking program I had ever seen. Watching this display I tried to figure out why there were patterns I had never seen before. I came to realize that this was not group bevavior, but MEGA group behavior. Without thousands of individuals, these patterns would be of such low resolution as to be entirely invisible.

Now I had a goal. I wanted a flocking program with the capacity of that swarm of martins. There was one problem however. The reason flocking programs in the past had not encompassed such large populations is that the amount of calculation necessary goes up exponentially. Each individual has to look at every other individual and determine if they are close enough to derive a reaction to each other from. Say, for example, that in a particular flocking program, each individual (from here forward refered to as a "fly") watches its two closest neighbors, maintaining a certain desirable distance from those neighbors. For a given flock, there are (population x population x number-watched-neighbors) calculations that must be performed EVERY iteration of the program. For a population of 10 with two neighbors being watched by each individual, there are 10 x 10 x 2 calculations every iteration, 200 calculations. This isn't so bad. But for a population of 100 individuals, just 10 times the previous population, there are 100 x 100 x 2 calculations, 20,000 in total. This is okay. Most computers can handle this, but it is 200 times the number of calculations for only 10 times the population. For 1000 individuals it gets even worse: 2,000,000 calculations. Now we have a problem. A minimum frame rate of 5 fps is necessary for any resemblance to smooth flight and more is always better. To make matters worse, I discovered while programming Mega Flies, that 1000 individuals is hardly sufficient to produce the patterns I wanted. 10,000 or 100,000 individuals would be far more preferable.

I scouted the Internet for flocking programs, that, while limited to small populations, performed really fast. I found one, Flies by Alex Vulliamy. I asked him for his source code with the intention of modifying it to allow more than 100 individuals. It was so fast a program, I imagined that it might handle larger populations rather well.

I was not entirely correct. His program would not animate thousands of individuals with the speed I desired. However, there were a lot of changes that could be made to speed up the program. These changes had not been worth the trouble to Alex, because for the populations he was animating, the program ran extremely fast. "Necessity is the mother of invention."

Anyway, to make a long story shorter than it could be, I massively sped up Flies by a factor of slightly more than 7, enough to animate a couple thousand individuals at a smooth frame rate, and this was on a 120 MHz 604 PPC processor (512k L2 cache). There are MUCH faster machines that could probably animate Mega Flies with a population of more than 10,000 individuals smoothly.

Perhaps you are wondering how amateur programmers like Alex and myself outdid all the other people who have written flocking programs in the past. Well, we didn't. Alex's program, Flies, cheats when determing the closest neighbors in the flock, and Mega Flies uses the same algorithm, entirely unaltered. I only sped up the efficiency of Flies, not the methodology itself. How do Flies and Mega Flies cheat? Ideally, each fly should check out every other fly in the population in order to accurately determine which flies are the closest and resultantly are the neighbors to which the original fly must pay attention. What Alex came up with is to have the original fly only check its previous neighbors and the neighbors of its neighbors, and take the closest of that small group of flies as the next neighbors. This clever strategy is much faster than the more precise method, but it means that two distinct groups can fly right through each other and never interact. Since the flies are only looking at their last neighbors and the neighbors of those neighbors, they cannot "see" any other flies on the screen. In Mega Flies I offered the togglable option to check one layer of neighbors deeper than Flies does, which slows the program down by 1.5 times. This does not negate the error, but decreases it somewhat. Regardless of this imperfection in the algorithm, the payoff is worth it, as I have taken advantage of Alex's algorithm to produce the first (to my knowledge) flocking program capable of animating multiple thousands of individuals in realtime on a desktop computer, and thus making available the beautiful complexity of emgergent behavior only visible at such large resolutions.

The patterns that emerged are diverse and incredibly complex. They are obviously dependent on the row and column arrangement of pixels on a computer screen, because the patterns are often oriented exactly horizontally or vertically, but this in no way diminishes their beauty and awesome complexity. So far I have seen oscillating and pulsating patterns, orbital patterns (a small group around a larger group), and track-following patterns (generally around the outline of a cross, like a plus sign: +), not to mention other beautiful patterns.

In addition to larger populations and increased speed, Mega Flies also sports a larger window and several brand new controls including the spacing distance between the flies, the number of neighbors that each individual watches, and trail-following to track the movements of individual flies.

Mega Flies is freeware and will run on any Macintosh computer.

Download Mega Flies