Comp 239 final project paper
May 3, 1998
Flocking, Boids and Tag
My final project is a simulation of a complex, natural behavior: flocking.
The model of flocking is derived from Craig Reynolds's '87 SIGGRAPH paper,
but I added several additional components to the behavior, including chasing
a target, and playing the game of Tag. I also allow the user to ride along
with a member of the flock, and control its motion. It this way, the user
can either sit back and observe, or jump in and participate in the life
of the flock.
My virtual world consists of an outer bounding box, a few obstacles, a
flock of boids, and the user. The term "boid" stands for "bird-oid" and
comes from [reynolds87]. It is a convenient term for any animal or artificial
creature that flocks (or herds, or schools).
The behavior of a boid is modeled using a priority-based scheme. A boid
has several goals, possibly conflicting, as discussed below. Each one produces
a desired acceleration direction, and a weight between zero and one which
is a measure of its urgency. The goals are sorted by priority and added
into an accumulator in that order. The magnitude is added into a scalar
accumulator, and the acceleration direction times the weight is added into
a vector accumulator. If the scalar accumulator exceeds one, the vector
is trimmed back in proportion. This allows a high priority behavior, like
avoiding collisions, to temporarily exclude low priority behaviors, like
maintaining a cruising speed, and therefor avoids dithering or averaging
two accelerations to produce an unacceptable result.
Listed below are the behaviors included in my system, in order of priority.
Several behaviors involve the boid's "neighbors". These are the boids within
a sensory sphere around the boid; if there are no boids in this sphere,
then it has no neighbors and those behaviors are inactive.
Static collision avoidance. The boid tries to avoid a static obstacle in
the environment. First, objects are identified by casting a ray in the
direction the boid is moving. They are considered a hazard if they are
within some probe distance, which increases as the boid moves faster. The
acceleration generated is the normal vector of the obstacle's surface,
weighted by the inverse distance to the object. This works well most of
the time, but lets the boids oscillate when moving into a corner.
Chase. This behavior is specific to a boid playing tag. The boid finds
the nearest neighbor within its sensory sphere, and tries to chase it by
returning the vector from its position to the target's position, times
a constant weight.
Dynamic collision avoidance. The boid tries to avoid crashing into its
neighbors. It finds the nearest neighbor, and checks to see if the neighbor
is closer than its cruising distance. If so, it returns the vector from
the neighbor's position to its position, weighted by the inverse square
of the distance between them (it gets more urgent as they get closer, and
can exceed magnitude one if they get very close).
Flock centering. The positions of the boid's neighbors are averaged, and
the boid returns a vector towards than position. The weight is usually
a small constant, like 0.1.
Velocity matching. The boid finds its nearest neighbor, and returns a vector
in the same direction as the neighbor's velocity. The weight is usually
a small constant, like 0.05.
Target chasing. Each boid has an individual target position and target
direction. They also have flags to determine whether the boid should target
a position or direction at all. For a position, the boid returns a vector
towards the target. For a direction, the boid returns the direction vector.
Each is modified by a constant weight. The position can be set each frame,
so the boids can chase the user's hand position, or another boid. Since
this is low priority, this chasing behavior will only modify the already
existing flocking behaviors. The boids also have a flag indicating whether
they should avoid the target. In that case, they merely negate their returned
Cruising velocity. The boid tries to maintain a cruising velocity, typically
0.2 times maximum velocity. If the boid is moving too slowly, the vector
returned is along the current velocity. If the boid is moving too fast,
the vector is opposite the current velocity.
Level flight. The boid tries to fly level. The vector returned is the negative
of the vertical acceleration so far.
This is a screen shot, showing the boids orbiting a target cube. The
purple boid is It, and the other objects in the scene are obstacles the
boids will avoid.
Having complete control over the behavior of virtual creatures is engrossing.
The flock's behavior is completely in the user's control, but only indirectly.
A small change in the parameter's value often makes a subtle change which
takes a few minutes of observation to detect. For instance, if the boids
are targeting a position, often they will orbit the target, because they
are moving too quickly and do not have sufficient acceleration to turn
towards the target and hit it. If the neighbor avoidance behavior is off,
the boids will tend to clump together and move together as a unit. If it
is on, with a moderate weight, and velocity matching is off, the boids
will appear to swarm the target, each moving individually, often making
sudden changes in direction to avoid running into their neighbor. If the
velocity matching is now turned on, with a small weight, the boids will
slowly coalesce into groups of four or five, each heading in the same direction,
still orbiting the target. Boids with a low maximum acceleration seem relatively
relaxed in their behavior, while those with a high maximum acceleration
seem quick and aggressive.
"Boid cam" was a valuable addition to my project. By riding along with
a boid, you can see the other boids' reactions to a specific boid, and
get a very different feel for the world. Doing this in an HMD can be disorienting,
but it makes the flocking behavior even more compelling to watch.
The game of Tag adds an interactive challenge for the user. One boid
is It, and uses the Chase behavior to chase its target. The user can control
a boid and run away from It, or get tagged and chase another boid. The
boids who are not it have their target positions updated with It's position,
and they can ignore It, move towards or away from It, depending on how
hard the user wants the game of Tag to be. Because It always chases its
nearest neighbor, the game is not that hard for the user, but with some
further modifications it could become more challenging.
I started with the viewer we wrote for homework #2, and rewrote it. I now
have an object-oriented design, which separates the functional units of
the code. My openGL graphics routines are all isolated from the tracker
routines, for example. I have these classes: World, Tracker, Hand, Button,
HMD, Mouse, Graphics, Boid, SimObject, among others. For the flocking behavior,
I started from a program available on the web, written for Open Inventor.
I made the software work with my viewer and graphics classes, and then
added to and heavily modified this base. One major change involved finding
all the "magic" numbers in the software and changing to variables, and
adding a tcl/tk interface that allowed the 20+ parameters of the flocking
model to be adjusted individually while the program is running.
Finally I designed user interface elements. The user has the same functionality
in the HMD and sitting at a workstation. The mouse has full viewpoint control,
analogous to the HMD, the user can move about the world by flying, and
the user can switch to "boid cam" and driving a boid with the mouse or
python. The tcl/tk controls are only accessible at the monitor, however.
Craig Reynolds in his 1987 SIGGRAPH paper describes the basic flocking
model and the accumulator I used to control my boids [reynolds87]. I added
additional behaviors for chasing targets, moderate speed, and level flight.
In [brogan97], the authors describe a somewhat different flocking algorithm
based on an average distance from neighbors in the flock. In particular,
they use a proportional-derivative controller for their creatures, which
I thought would provide a more stable motion for the flock, but I was unable
to determine how to integrate it into the flocking model I was using.
There are many, many other papers on controlling creatures. [blumberg95]
and [tu94] both describe hierarchical controls systems which allow complex
behaviors to written in terms of simpler ones. [grzeszczuk95] describes
how to evolve a layered controller, first by evolving simple controls for
moving forward and turning, then abstracting those controllers using Fourier
analysis and composing them into more complex controllers, like one for
doing a trick. Finally [sims94] describes a method for evolving both the
shape and controller of a creature. I hope to investigate the search techniques
and behavior control methods described in these papers later on.
"My project will be complete when I have predators and grazers in a virtual
world competing with each other, and when the user can take on the role
of a creature. I believe I will have the creatures' behavior evolving,
but I am not confident this will get done."
Instead of having predators and grazers, I have the boids playing a
game of tag. The user can fully take on the role of a boid, either riding
on its back and watching its behavior, or taking control and steering the
boid to take part in the game of tag. I was right, I didn't have time to
evolve the boid's behavior. The boids also have somewhat more complex behavior
than I originally intended, because they have a prioritize flocking model.
Behaviors are not necessarily separable through observation. I had problems
getting the boids to avoid each other for over a week. Finally, I discovered
that the avoidance behavior was not even active. This was not obvious from
the boids' overall behavior, and only after I got the avoidance working
did I realize how much difference it could make. Because the boids are
constantly avoiding each other, they can look more like an insect swarm
than a flock.
While the individual behaviors as described all work, there are a few
problems. The collision avoidance algorithm needs to be improved so it
can handle approaching the concave corner of a box without oscillating.
I believe a simple memory for the last obstacle seen would fix this problem.
The boid could continue to avoid whichever obstacle was closer instead
of oscillating between the two. I believe the neighbor avoidance and the
velocity matching behavior might both be made less jerky by taking into
account several neighbors, instead of just the nearest neighbor.
I would like to provide a richer environment for the flock. The best way
to do this would be to allow the user to move and place obstacles.
I would like to investigate using genetic algorithms to evolve behavior
and shape, as in [sims94]. One problem is that he does a full physically-based
simulation, which is not real-time, so it wouldn't fit into my current
Reynolds mentions using boid-centered coordinates for all behaviors.
This means all vectors are scaled so they are in terms of the body-length
of the boid. Currently, the behaviors are half in world coordinates, and
half in boid coordinates. I would like to make this consistent, so it is
easy to introduce new boid geometry.
I would like to do more investigation of user interaction inside the
HMD. In particular, it would be good to be able to control the flocking
parameters inside the HMD. This means adding some kind of menu system,
or 3D widgets of some kind, useable and recognizable while fully immersed.
[blumberg95] B. Blumberg, T. Galyean. Multi-Level Direction of Autonomous
Creatures for Real-Time Virtual Environments., ACM Computer Graphics,
Proceedings of SIGGRAPH'95, August 1995.
[brogan97] D. Brogran, J. Hodgins. Group Behaviors for Systems with
Significant Dynamics. Autonomous Robots, 4, 1997. Kluwer Academic
Publishers, Boston, pages 137-153.
[grzeszczuk95] R. Grzeszczuk, D. Terzopoulos. Automated Learning of
Muscle-Actuated Locomotion Through Control Abstraction, ACM Computer
Graphics, Proceedings of SIGGRAPH'95, August 1995.
[reynolds87] C. W. Reynolds. Flocks, Herds, and Schools: A Distributed
Behavioral Model, in Computer Graphics, 21(4) (SIGGRAPH '87 Conference
Proceedings), pages 25-34.
[sims94] K. Sims. Evolving virtual creatures. In SIGGRAPH 94 Conf.
Proc., pages 15-22, Orlando, Florida,
[tu94] X. Tu and D. Terzopoulos. Artificial Fishes: Physics, Locomotion,
Perception, Behavior. In SIGGRAPH 9 Conf. Proc.,
Orlando, Florida, July 1994.