19.2 Flocking Systems

A variation of the particle system was used by Craig Reynolds to model the flocking and schooling behavior of birds and fish. In this particle system the particles are used to represent what Reynolds called “boids”. In this case, each particle is an entire polygonal object rather than a graphical primitive, each particle has a local coordinate system, and there are a fixed number of particles that are not created or destroyed. The attributes which control the boids behavior is dependent on external as well as internal conditions, allowing a boid particle to react to what other particles are doing around it. Some characteristics of this system include:

• Collision avoidance – a boid is constrained from colliding with other boids or obstacles;
• Velocity matching – each boid attempts to go the same speed and direction as neighboring boids;
• Flock centering – each boid attempts to stay close to nearby flockmates.

According to Reynolds:

Typical computer animation models only the shape and physical properties of the characters, whereas behavioral or character-based animation seeks to model the behavior of the character. The goal is for such simulated characters to handle many of the details of their actions, and hence their motions. These behaviors include a whole range of activities from simple path planning to complex “emotional” interactions between characters. The construction of behavioral animation characters has attracted many researchers, but it is still a young field in which more work is needed.

Reynolds’ 1986 computer model of coordinated animal motion was based on three dimensional computational geometry. The flocking model placed an individual “boid” in a flock, and determined the motion path using the steering behaviors that were based on the positions and velocities nearby flockmates:

• Separation: steer to avoid crowding local flockmates
• Alignment: steer towards the average heading of local flockmates
• Cohesion: steer to move toward the average position of local flockmates

Each boid has direct access to the whole scene’s geometric description, but it needs to react only to flockmates within a certain small neighborhood around itself. The neighborhood is characterized by a distance (measured from the center of the boid) and an angle, measured from the boid’s direction of flight. Flockmates outside the local neighborhood are ignored.

Reynolds produce a short film for the SIGGRAPH 87 electronic theatre called Stanley and Stella in: Breaking the Ice. to demonstrate the basic flocking and schooling algorithms in his system, which he called BOIDS. The film was made in conjunction with Symbolics and Whitney/Demos Productions.

Reynolds flocking algorithm was not the first such algorithm. For the famous film Eurhythmy produced at Ohio State, Susan Amkraut implemented what she referred to as a “force-field” flocking algorithm. She describes her approach in an interview with later collaborator Paul Kaiser:

Yes, I’d started working on the problem of flocking. Whereas Michael’s [Girard] project [at Ohio State] was to look at the human body in motion, mine was to take a mathematical algorithm and to see where it could lead. I’d begun by animating particles using force-fields in 3D. These force-fields would attract, or repel, or shape the movement of the particles. So, for example, I could have a sink that drew all the particles in, or a source they’d funnel out of, or even a spiral they’d fly around. I soon saw how this could lead to an elegant solution for flocking.

The problem posed by flocking is this: you have multiple creatures who don’t want to run into each other, but also want to stay very close together — and they have to avoid hitting any external obstacles as well. Algorithms had been developed in which a lead bird guided the flock. But real flocks behave in a more interesting fashion: they have no leader. So, neither did my algorithm, which worked like this. I put a little force-field around every bird, so that if any other bird got near, it was told to go away. And of course each bird had a corresponding attraction field, so that if the other bird got too far away, it was told to come closer. So every bird at every frame of the animation considers every force-field around it, and moves accordingly.

It’s a difficult algorithm to work with because you can’t tell where you are at any given point in time unless you know where you started and have computed all the way back up from there. My interest in this went beyond wanting to simulate actual flocks. I wanted to create a flock of birds all flying realistically as individuals, but flying collectively in patterns that could never happen in the real world.

As Reynolds points out on his web site, since 1987 there have been many other applications of the boids model in the realm of behavioral animation. The 1992 Tim Burton film Batman Returns was the first. It contained computer simulated bat swarms and penguin flocks which were created with modified versions of the original boids software developed at Symbolics. Andy Kopra (then at VIFX, which later merged with Rhythm & Hues) produced realistic imagery of bat swarms. Andrea Losch (then at Boss Films) and Paul Ashdown created animation of an “army” of penguins marching through the streets of Gotham City.

A similar approach was used to produce the famous Wildebeest stampede in the Disney movie The Lion King. According to the film notes at http://www.lionking.org/text/FilmNotes.html

For the pivotal scene in the film where Scar enacts his plan to do away with his royal relatives, Mufasa and Simba, directors Allers and Minkoff wanted to create something with the same visual impact as the dramatic events that were unfolding. The script called for thousands of stampeding wildebeests to pour over the hilltop into the gorge below. Feature Animation’s CGI (Computer Generated Imagery) department was called upon to help pull off this amazing feat and to enhance the emotional impact of the scene. Five specially trained animators and technicians in this department spent over two years creating the impressive 2-1/2 minute sequence, which represents a new level of sophistication for the art form and a dramatic highlight for the film.

Starting with a 2-dimensional model sheet and some conventional hand-drawn rough animation, created by supervising animator Ruben Aquino, Johnston and his CGI team were able to generate 3-dimensional representations of a wildebeest inside the computer. Once this digitized computer version existed, the camera could be placed anywhere to allow different angles during the course of a scene.

“Since the scene called for a stampede, we had to come up with a way that our animators could control the behavior of herds of wildebeests without having them bump into each other,” says Johnston. “We developed a simulation program that would allow us to designate leaders and followers within each group. We were also able to individualize and vary the movement of each animal within a group to give them a certain random quality. Effectively they could all be doing different things with the library of behavior including slow and fast gallops, various head tosses and even a few different kinds of leaps.”

In the end, the hand-drawn animation of Simba and Mufasa was composited with the CGI wildebeest stampede and the film’s other hand-drawn elements (backgrounds and effects). “The object is to make the wildebeests look like the other characters in the film,” says Johnston. “We don’t want them to stand out. We just want a dramatic effect.”

The flocking algorithms developed by Reynolds and others have advanced significantly, and variations on the same approach have been used (coupled with new technologies such as motion capture) to generate crowds and large numbers of animated characters for motion pictures. In the movie Sharkslayers, large schools of fish are animated. There are armies in Star Wars, The Mummy, and Lord of the Rings, colonies of ants in Antz, insects in A Bug’s Life, and passengers on the Titanic. Production companies such as PDI and ILM have developed their own approach to crowd control, and software packages like Houdini and Character Studio have included crowd animation components.

Several articles by Barbara Robertson of Computer Graphics World have dealt with crowd animation, including Crowd Control in the February, 1998 issue, Faces and Crowds in the July 1998 issue, A Bug’s Eye View in the November 1998 issue, and more recently The Two Towers (February 2003).

Movie 19.6 Eurhythmy Motion Studies (1985)

https://www.youtube.com/watch?v=qVcyttQbKP0
Produced at Ohio State by Michael Girard and Susan Amkraut, it uses Amkraut’s flocking behavior for the birds animation

Movie 19.7 Stanley and Stella in Breaking the Ice

https://www.youtube.com/watch?v=3bTqWsVqyzE
Animated by Phillipe Bergeron using Craig Reynolds behavioral animation techniques (1987)