Introduction

In Gertie, Interrupted, the scene in which a pack of rats flees a building about to be stomped on only to be squished themselves is sure to bring an audience to laughter. Special care was necessary to ensure that as the rats ran away, they would run around debris and each other. If one would use traditional key framing techniques, animating this would be either tedious or lead to unrealistic results. Thus, I wrote a plug-in for Maya that automates each rat's movements.



Watch my flocking plug-in in action in a scene from Gertie, Interrupted. (9 MB)

The Algorithm

My plug-in is an implementation of Craig Reynolds' paper Flocks, Herds, and Schools: A Distributed Behavioral Model (SIGGRAPH '87). In the paper, he coined the term bird-oid, or ‘boid’, to refer to a member of such a group. Reynolds found that if each boid followed only three rules that a group of them can be animated realistically.

These rules are:

1) Each boid wants to match the velocity of its neighboring boids.

Each of these rules can be written in terms of changes in acceleration. Additional rules can be added to make the boids look more realistic or to give the animator greater control.

My Implementation

To implement this, I created a C++ boid class which was shared by both a Maya plug-in and an OpenGL program. By writing a separate OpenGL application to fine-tune the algorithm, developing the plug-in became much easier and allows one to see the algorithm without having Maya. In the pictures above (from an older version of the program) you can see how the boids split apart as they reach an obstacle.

For each boid, I maintain a history of its position. In this way, velocities can be calculated by taking the difference between the previous two positions, and accelerations can be calculated by taking the difference between the previous two velocities. To simulate flocking, I calculated an acceleration vector for each of the three boid rules.

The velocity-matching rule was implemented for each boid by calculating the average of all boids located within an arbitrary distance of it. (I set it to 200.) The acceleration vector is then defined as a weight multiplied by the difference between the previous velocity and the average velocity.

The flock centeredness rule was implemented by calculating the centroid of all neighboring boids in the flock. This was computed by averaging the boids’ locations. Then, a velocity was calculated that would move the current boid to the centroid over one clock cycle. Because we do not want the boid to move to the centroid immediately, the velocity’s magnitude was multiplied by a weighting factor. Again, an acceleration vector was calculated by multiplying the difference between the old velocity and this new velocity by another weighting factor.

Finally, the avoidance acceleration was calculated by moving the boid away from all other boids and obstacles proportionally to how far away it is. This produces a bounce-like effect, since as the boids moves farther away from its collision, it accelerates more. It is important to keep the weight for avoidance low to make the bouncing less noticable.

Several problems result from this implementation. First, velocities grow quickly. We do not want rats to run at 60 mph! [Although I think they ran at about 20-30 mph in the movie ;)] To prevent this, when the velocity grows higher than a maximum, the final acceleration vector’s magnitude is decreased to set the new velocity to the maximum. Additionally, because we are adding together three accelerations, the heading and centeredness acceleration might dominate the avoidance acceleration, causing rats to collide with obstacles and other rats despite their attempts not to. To reduce this problem, accelerations were calculated in a priority order (avoidance, centeredness, velocity matching), and the acceleration was capped at a maximum. In this way, if a boid has a large avoidance acceleration, then it might not have any centeredness or heading accelerations.

But this still has problems, which I did not resolve. One problem is that boids wlll often collide with each other. This is because the basic flocking algorithm only includes collision avoidance. One way to fix this is to alter the weights of the different acceleration vectors until the collision is avoided. You can experiment with this in the OpenGL program. Reynolds discusses further methods in a later paper that can be found off of his website.

Finally, the basic flocking algorithm presents additional problems to an animator. An animator wants to control where a flock is located at a particular time. To aid the accomplishment of this goal, I allow the user to set a target, and apply an acceleration vector toward this point. Unfortunately, even after doing this, the animator still does not have precise control. This is because even if one calculates the necessary acceleration rate so that the boids reach their target at the appropriate time, one needs to account for the changes in velocity that occur when the boids maintain their distance from each other and from obstacles. In Gertie, Interrupted, it was important to time the animation such that the rats leave the house right before it gets crushed and that they arrive underneath the foot just as the mech is about to stomp on them. I resolved this problem by running the algorithm multiple times, with different maximum velocities and maximum accelerations. I think that it would be possible to automate the adjustments of parameters through the use of a space-time constraint solver, although this was not implemented.

The Plug-in

My first attempt at a Maya plug-in was a command-line version. In this plug-in, the user can select the boids and then specify parameters to customize flocking behavior.

Here is a brief explanation of how to use the commandline plugin. The first thing that the user should do is select all of the objects that he or she considers to be boids. Next, the user needs to load the flock plugin. Finally, the user needs to type in the following command:

flock [startframe] [endframe] [ignore y axis? (1=ignore, 0=use)]
[max velocity] [max accel] [collision distance] [boid radius]
[target X] [target Y] [target Z]
[obstacle1 X] [obstacle1 Y] [obstacle1 Z] [obstacle1 radius]
[obstacle2 X] [obstacle2 Y] [obstacle2 Z] [obstacle2 radius]
...

Here, the maximum acceleration and velocity are expressed in Maya units per frame squared and Maya units per frame, respectively. The avoidance distance is how close boids can be to each other and to obstacles, expressed in screen units. You will need to specify if the boids can accelerate over the y axis. If you are working with objects that cannot fly, then you should choose to ignore the y axis so that the boids do not fly. The boid radius is the radius of the bounding sphere for each of your boids. You can specify a target in terms of its X, Y, and Z coordinates. You can include obstacles by giving their X, Y, Z coordinates and the size of their bounding spheres. When you run the plugin, it will create keyframes for each boid over each frame.

To make a more user-friendly plug-in, I decided to attempt a node plug-in. Node plugins are much more complicated, but also much easier to use. Unfortunately, by the time that I developed a working understanding of the Maya API, it became necessary to work on other aspects of production so I did not have enough time to spend debugging it to get it working correctly.

Here is what I wanted it to do:

When the user creates a flock node, it must be attached to a shape. This shape represents the target that the boids will move toward. The user can key-frame the position of the flock node to control where the boids will move toward at each frame. Also, because the plug-in would be a node, the boids’ paths would be recalculated every time an obstacle is moved or its initial position gets changed.

The flock node would also have parameters for an avoidance distance, maximum velocity, and maximum acceleration. An advantage to making these parameters is that they can be keyframed so the user can effectively tell the rats to move farther apart at a certain point. An object would be classified as a boid or as an obstacle based on the beginning of objects’ names. The sizes of boids and obstacles would be read from the scene and approximated as bounding spheres.

It took me awhile to realize that it would be necessary to create an attribute for each boid. You can see the results of my non-working node plug-in below.

Downloads

OpenGL executable
Maya plug-in (command line)
Maya plug-in (node … in progress) (requires MEL script)
C++ source code (requires OpenGL, FLTK to compile)