Aron Helser

Aron Helser
Comp 239 final project paper
May 3, 1998

Flocking, Boids and Tag

Abstract

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.

Description

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 vector.
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.

Compelling Aspects

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.

Method

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.

Related Work

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.

Completion Criteria

"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.

Problems

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.

Future Work

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 work.

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.

References

[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, July 1994.

[tu94] X. Tu and D. Terzopoulos. Artificial Fishes: Physics, Locomotion, Perception, Behavior. In SIGGRAPH 9 Conf. Proc., Orlando, Florida, July 1994.