A Java application was developed to explore the dynamics of movements of large collections of independently moving agents. The simulation is highly geometry-based. Much effort was spent in making the interface pleasant to use. The result is an amusing "toy" application with potential for future development.
The original inspiration for this project came several years ago as I was watching birds move around a plaza. Some people were throwing bits of food to the birds, and it occurred to me to wonder how a bird decided whether to walk or fly to where the food was. The distance to be covered would be a factor, as would the number of competitors in the area, degree of hunger, and doubtless many other variables would influence the decision.
The relation of this project to the original concept could be considered weak. It retains the concept of a goal and of consciousness of other actors in the scene, but there is only one mode of locomotion. Rather than having distance be the difficulty to be overcome, the current project presents the characters with obstacles to be navigated around.
This project was intended to be an initial step in creating a path generation tool for animations involving large numbers of independently motivated characters navigating around obstacles and each other while still progressing toward their individual goals. This type of situation might occur in transportation terminals, pubs, institutional hallways, et cetera.
Previous work in this field has been done by Reynolds (1987, 2001) with his "boids" model of flock, school, or herd motion. This approach is behavior-based, treating each individual "boid" as a self-directed entity that seeks to satisfy various constraints on its motion, such as maintaining a buffer space around itself, moving toward the centre of a flock, and matching velocity with neighbouring "boids". Reynolds' work differs from this project in that there is not as much emphasis on goal attainment, and in that rather than having individual goals for each member of the flock, the "boids" would all tend to move toward the same thing. This is why I have chosen to use the word "crowd" to describe the current work: it is meant to imply that the motion does not have an overall net pattern.
Musse et al. (1999, 2000) have developed an impressive system to animate crowds in real time which far surpasses the work presented here. In my defence, however, I submit that this project's interface is simpler to use, and the application is fairly lightweight and highly portable (it is implemented in Java, using the Swing library). The project has been a valuable learning experience in GUI programming and performing simple animation, and further development of the application is anticipated.
This section will describe the application and how to use it. The application is started simply enough by unpacking the crowd.tar.gz or crowd.zip file and executing "go.bat" (Windows) or "./go.sh" (*nix) from the command line. Two windows will appear on the screen. The first is the Control frame:
The four fields at the top allow the user to manipulate some global constants that affect the movement of actors. kp and kv are the coefficients of the position error and velocity error for the PD controller. ε (epsilon) is a minimum velocity, required because all movement is controlled by manipulating an acceleration vector. Fr is the repulsion force exerted by obstacles on actors to keep them from colliding, and also is scaled by 'importance' and 'friendliness' factors for interpersonal reactions and goal-directed motion.
The four buttons Add Person, Add Square, Add Triangle and Add Goal allow the user to place new actors (all visible objects are called "actors") in the simulation frame. The text field shows some information about the currently "hovered" actor in the simulation.
The Simulation frame is initially blank. Actors (people, obstacles, and goals) can be added using the Control frame, then may be moved and resized. The scale is initially 10 pixels to 1 metre.
The default appearances of the various actors are:
Double-clicking on an actor will call up its Properties frame:
These windows allow the user to specify the actor's color and name. Obstacles (squares and triangles) can be sized precisely. For people, maximum speed may be specified, and goals may be "pushed" onto the person's "goal stack". Note: People may also be Goals. Selecting a person from the New Known Person combo box will effectively "introduce" the person, giving them an "attraction factor" which may be positive or negative.
"Hovering" the mouse over an actor will cause a description of it to show in the Control frame's text area. A Person's velocity vector may also be reoriented and resized using the mouse's left button.
A simpler way to assign goals to people than using the Properties frame is this:
Once the scene is built and the goals are set, press Start on the Simulation frame to see the result. As the people move about, you can see the red acceleration vector change. You can move and resize actors while the simulation is running, and you may also pause the simulation at any time by using the Pause/Start button.
This is the result of a run that included seven goals and five people. Note that the cluster of people on the right side has maintained the personal space requirement of each person. Static pictures can only show so much: the reader is encouraged to download and try the application for her or himself.
The technique for directing the People is one that may have been invented by myself, although it may not be
original. It is geometrically based, using lines, points, and vectors from the geometry package
developed by the author for this project.
If the direct path ("axis") to a goal is blocked by an object, the person queries the blocking object for its left and right edges. The person then chooses one of these edges based on least distance or minimal angular deviation from the axis. A point is then constructed a small distance from the chosen edge, which serves as a secondary goal. This secondary goal is then pushed onto the person's goal stack.
Once a goal (primary or secondary) is visible, a PD-controller constructs an acceleration vector to "push" the person toward the goal. Other influences on the acceleration vector come from anti-collision forces exerted by obstacles and attraction/repulsion forces from known persons.
User testing has been necessarily limited due to the short time between completion of the "beta" application and the submission date, but one test subject (adult, female) did find the program enjoyable to play with, and used it for well over a half hour.
The goal-seeking algorithm gives plausible results in simple layouts, but does get "hung up" easily, for example, it has no notion of "corridor" and so will continually attempt to enter a gap that is too narrow for it, if it is able to "see" the goal it is headed toward, and it may also become stuck in a bistable state, creating endless subgoals if it tries to enter a narrow corridor to reach a subgoal. Some users (myself included) have tried to challenge the people in the simulation to solve maze-like situations -- this did not result in success; after all the algorithm is not about solving mazes, but about constructing plausible paths through cluttered scenes. The distance between obstacles should always be wide enough to permit a person to pass through.
Further development of the application will allow user-designed obstacles and the ability to overlap obstacles to create more complicated barriers. Multiple selection of people will allow goal specification for shared-minded "crowds" much easier. Improved Properties frames will allow selection of the actor to be edited, rather than having separate frames for each actor, which can be annoying when they stack up.
Kuffner, J. Jr. (1999) Goal-Directed Navigation for Animated Characters. (Web page) Stanford CS Robotics Laboratory.
Musse, S.R. and Thalmann, D. (2000) From One Virtual Actor to Virtual Crowds: Requirements and Constraints. in Sierra, C., Gini, M. and Rosenschein, J.S. Proceedings of the Fourth International Conference on Autonomous Agents. ACM Press, Barcelona, Catalonia, Spain. pp. 52-53.
Musse, S.R., Garat, F. and Thalmann, D. (1999) Guiding and Interacting with Virtual Crowds in Real-Time. in Proceedings of Eurographics Workshop on Animation and Simulation, Milan, Italy. pp. 23-34.
Reynolds, C. (2001) Boids (Flocks, Herds, and Schools: a Distributed Behavioral Model (Web page)
Reynolds, C. (1987) Flocks, Herds, and Schools: A Distributed Behavioral Model. Computer Graphics 21(4):21-34.
The 'crowd' simulator is available as a zip or tar.gz archive.