The summer after my freshman year in college my family and I went on a boating trip to the Canadian side of the 1000 Islands region of Lake Ontario. On our way back we stopped in Kingston, Ontario to do a little shopping, and I stumbled upon a used copy of Steven Levy's book Artificial Life: Quest for a New Creation.

Levy's book blew my mind. The idea of artificial creatures living, breeding, interacting and evolving within a computer sparked my imagination and renewed my confidence in computer science. Artificial life brought back the excitement that was lost when I realized artificial intelligence wasn't all it cracked up to be. For about a year all I talked about was genetic algorithms, Lindenmeyer systems, flocking, etc.

I started reading papers and books on the subject, but never took it any farther. After my sophomore year things started to change. I went to SIGGRAPH '95 in Los Angeles that summer, where everyone and their grandmother seemed to be excited about A-life. Soon after I left L.A. I started my fall co-op job at The Mitre Corporation in McLean, Virginia, where I got my first chance and doing something useful with A-life.

No, not the Mitre that makes soccer (football for the Europeans in the crowd) equipment! This Mitre is a large not-for-profit organization which has its hands in just about everything. The bulk of their work is split between military work for the Department of Defense and civilian aviation work for the FAA and foreign countries. I worked for the FAA part of the company, in the Center for Advanced Aviation System Development.

Craig Reynold's Boids Program:

The image above is from Craig's original software. You can learn more about Craig and the boids by visiting his web page.

Of course, planes do not normally fly in flocks! But what we were really interested in was the idea of "self-separation", where planes could maintain the appropriate distance from and relative position to one another without control from any centralized authority.

Right now aircraft are controlled by a central authority, the air traffic controller, and the control mechanism is "predictive". The controller views the incoming traffic in a given sector, tries to predict conflicts, and then orders the pilots to change course appropriately to prevent the conflict from occurring. This is different from the "reactive" style of navigation where the pilot adjusts his course in reaction to conflicts occurring at the immediate point in time.

While this a good method of control at an airport, it's really inefficient when planes are over the ocean or in the middle of Iowa where air traffic is sparse and the planes are flying at high altitudes. The FAA is currently implementing a long-term plan known as "free-flight" which will give pilots a greater amount of freedom in choosing their course of flight. While this will not eliminate the predictive element of control, it will increase the "reactive" element of the path planning process because pilots will be making more decisions without consulting the other pilots and without knowledge of the "big picture" that the controllers have at their disposal.

The boids algorithm is completely reactive, so we believed that air traffic could be treated as a giant flock of birds, granted that the "birds" would be several miles apart instead of several feet.

The Mitre Boids:

You can look at a screenshot or download the SGI Irix 5.3 binary. You need 24-bit color to run this program, because otherwise the dithering hides the planes.

Unfortunately, I didn't have a lot of time to work on the boids because it was a side project; my primary responsibilities at the time were working on Graphics Service (the graphics library used in the airport simulation and the flight simulator) and the autopilot software. However, I did manage to get a simple boids implementation together. Though it used plane models in the animation, these boids behaved nothing like real planes. I think the best word to describe their behavior would be "cute"; they behaved a lot like fish in a tank. Towards the end of my first work term at Mitre a co-worker, Dr. Craig Wanke, helped me with modify the dynamics of the boids so that their responses were closer to that of actual airplanes. When we plugged this back into the boids program, the flocking failed miserably, for several reasons.

The maneuvering capabilities of (civilian) aircraft are highly limited. While birds might not have a problem pulling a 3g turn, passengers on an aircraft would most certainly spew their lunch on the seat in front of them. Planes are also more rigid and weigh a great deal more than your average bird, and hence must carefully manage their attitude (roll, pitch, yaw) and power in order to maintain altitude.

While immediate conflicts are currently resolved reactively through systems like the Traffic Alert Collision Avoidance System (TCAS is extensively deployed in the field and TCAS II is in development) that provide auditory instructions for resolution, these systems resolve conflicts primarily by adjusting altitude as opposed to velocity or heading. This tends to limit the flock to two dimensions. Also, since aircraft maneuvers are so limited, potential conflicts need to be identified and resolved while the planes are still far away, and resolving future conflicts is the domain of predictive methods, not reactive ones.

Though I'm not doing any boids research for Mitre right now, Rob and I still toss around the idea of plane-boids, though the flocking behavior might have to be modified or dropped. However, the most important concept, that of decentralized emergent behavior via simple rules, would remain. Only the rules would change.

The New and Improved Boids:

A screenshot, source code, and SGI Irix 5.3 demo binary are available. The binary should run decently on an SGI R4400-based Indy at 3fps. You can alter the frame rate in the source code to achieve smoother animation if you have faster graphics hardware (such as a Reality Engine). Also, the demo requires the boid.iv model to be in the same directory as the executable.

I felt bad about not doing more with the boids after I left Mitre to return to school, especially since Craig Reynolds and others had been so kind in helping me with the project. So in May of 1996 I started re-writing the boids software from scratch on my own time, so that I could release the code publicly. Initially they were written as an object type for the Virtual Reality Railroad simulation system that I helped develop. However, the VRRR project is highly modular, making it easy to separate out the boid code from the rest of the system.

The code is comprised of several classes, some of which are modified versions of the VRRR library code:

• SimObject [header]
Class for any type of generic "object".
• Boid [header | source]
Class for a a boid. Derived from SimObject. After setting up a boid, the user needs only to call update() periodically with the elapsed time in order to animate it. The boid automatically interacts with all other boids that have been created and attempts to avoid all obstacles that have been added to its obstacle list.
• Obstacle [header | source]
Class for creating obstacles and performing ray-obstacle intersection calculations. Information can be obtained regarding if a particular ray will intersect a given obstacle, where the interection occurs in 3-space, and what the normal to the obstacle at the point of intersection is. Currently supported obstacles include spheres, boxes, and convex planar polygons with an arbitrary number of vertices. Also includes a helper class for maintaining and iterating a list of obstacles.
• Vector [header | source]
Class for performing standard vector operations.
• NamedObject [header | source]
• Class for maintaining a list of SimObjects, iterating through the list, and inserting, deleting, and querying the list elements by name.

• Example Program [header | source | Makefile | model]
Class for maintaining a list of SimObjects, iterating through the list, and inserting, deleting, and querying the list elements by name.