background and update
by Craig Reynolds
Abstract: This paper presents solutions for one requirement of autonomous characters in animation and games: the ability to navigate around their world in a life-like and improvisational manner. These "steering behaviors" are largely independent of the particulars of the character's means of locomotion. Combinations of steering behaviors can be used to achieve higher level goals (For example: get from here to there while avoiding obstacles, follow this corridor, join that group of characters...) This paper divides motion behavior into three levels. It will focus on the middle level of steering behaviors, briefly describe the lower level of locomotion, and touch lightly on the higher level of goal setting and strategy.
| Online version of the GDC 1999 paper: Steering Behaviors For Autonomous Characters |
 |
OpenSteer is a open source C++ implementation of these steering behaviors, currently a prototype at version 0.7. It includes an application to demonstrate some of the basic ideas. You can also use it to develop and tune your own steering behaviors. |
Java-based animated diagrams of steering behaviors described in this paper:
- Simple behaviors for individuals and pairs:
- Combined behaviors and groups:
- Crowd Path Following
- Leader Following
- Unaligned Collision Avoidance
- Queuing (at a doorway)
- Flocking (combining: separation, alignment, cohesion)
Note that I cannot distribute the source code for these applets. Source code is available for OpenSteer which is a similar implementation in C++.
Related online resources by other authors (sorry, still not particularly well arranged):
Sometimes I hear from people who want to use steering behaviors in their work but never studied the (relatively simple) math and physics concepts on which they are based. As starting points, here are some introductory tutorials that might be useful:
- General steering behavior and related resources:
- Applets for Swarm, Forming Lines, Predator and Tag. From The Examination and Exploration of Algorithms and Complex Behaviour to Realistically Control Multiple Mobile Robots by Duncan Crombie.
- Behavior Library for Autonomous Character Locomotion (demo and code) by Clint Hannaford of Atomic Media written in Lingo(?) for MacroMedia's Shockwave player.
- steeringbehaviors.de is devoted to issues of steering behaviors, by Christian Schnellhammer and Thomas Feilkas, includes applets and source code with documentation. See also this report (in German).
- Simulating Pedestrians and Traffic:
- Steering Autonomous Driving Agents Through Intersections in Virtual Urban Environments [PDF] (2004) , Joseph Kearney James Cremer, and Peter Willemsen (to appear in proceedings of International Conference on Modeling, Simulation and Visualization Methods, Las Vegas, Nevada, June 2004) [new]
- Intuitive Crowd Behaviour in Dense Urban Environments using Local Laws [PDF] (2003) Celine Loscos, David Marchal, Alexandre Meyer [new]
- AI Madness: Using AI to Bring Open-City Racing to Life (2001) by Joe Adzima, describes "urban AI" for pedestrians and vehicles in a virtual cityscape. These techniques were used in the commercial games Midtown Madness 2 and Midnight Club.
- Simulating the Collision Avoidance Behavior of Pedestrians (2000) by Franck Feurtey, this Master's thesis describes a spacetime ("(x, y, t) space") approach to 2d unaligned collision avoidance while minimizing detours and speed variation.
- Generation of Ambient Traffic for Real-time Driving Simulation (1998) by Esmail Bonakdarian, James Cremer, Joseph Kearney and Pete Willemsen describes "bit players" to provide background traffic for virtual driving simulations.
- Discrete Force Model for Pedestrian Motion (including Lane Formation in a Street, Oscillation at a Bottleneck and Interactions at a Crossing), Java applets by Kai Bolay based on the work of Dirk Helbing. See also these related applets simulating: multi-lane traffic and single-lane traffic.
- Cellular Automata Simulation of Pedestrians by Victor Blue including Unidirectional and Bi-directional Pedestrian Flows and Cross-directional and 4-directional Pedestrian Flows.
- Simulating emergency evacuation of human crowds:
- Simulating Dynamical Features of Escape Panic (2000) by Dirk Helbing, Illes J. Farkas, and Tamas Vicsek: an individual-based model of panic evacuations of human crowds from rooms and corridors.
- Simulations of emergency evacuations at Fire Safety Engineering Group at the University of Greenwich.
- Crowd Dynamics Ltd. G. Keith Still's consulting company uses simulations of crowds to help plan safe public spaces.
- Learning and evolving steering controllers
- Learning to Race: Experiments with a Simulated Race Car (1998) by Larry D. Pyeatt and Adele E. Howe uses reinforcement learning to discover a reactive control system for a virtual race car using the Robot Automobile Racing Simulator (RARS). In addition to driving around the track the controller also deals with passing other cars and avoiding obstacles.
- Co-evolution of Pursuit and Evasion II: Simulation Methods and Results (1996) by Dave Cliff and Geoffrey F. Miller
- Competition, Coevolution and the Game of Tag, (1994) by Craig Reynolds [CiteSeer].
- Evolution of Corridor Following Behavior in a Noisy World (1994) by Craig Reynolds [CiteSeer].
- Co-Evolution of Pursuit and Evasion I: Biological and Game-Theoretic Foundations (1994) by Geoffrey F. Miller and Dave Cliff.
- Steering and path planning for games
- Near Optimal Hierarchical Path-Finding (2004) Adi Botea, Martin Müller, Jonathan Schaeffer [new]
- Efficient Navigation Mesh Implementation (2004) John C. O’Neill [new]
- Ribbon Networks for Modeling Navigable Paths of Autonomous Agents in Virtual Urban Environments [PDF] (2003) Peter Willemsen, Joseph K. Kearney and [new]
- Toward More Realistic Pathfinding (2001) by Marco Pinter describes extending A* search on grid-based maps to enforce constraints on turning radii.
- AI Madness: Using AI to Bring Open-City Racing to Life (2001) by Joe Adzima, describes "urban AI" for pedestrians and vehicles in a virtual cityscape. These techniques were used in the commercial games Midtown Madness 2 and Midnight Club.
- Formation-Based Pathfinding With Real-World Vehicles (2000) by Jim Van Verth, Victor Brueggemann, Jon Owen and Peter McMurry. Extends steering behaviors to include multi-vehicle formations and explores more specific vehicle locomotion models.
- Coordinated Unit Movement and Implementing Coordinated Movement (1999) by Dave C. Pottinger describes combining strategic path planning with path execution (similar to steering behaviors) for single characters and groups. Site requires free registration.
- Motion Planning Using Potential Fields (2000) by Stefan Baert starts from the assumption that all units (game characters) are the same size and move on a discrete grid, it discusses using potential fields to address several issues in navigation, while avoiding some of the typical shortcomings of potential field techniques.
- Models for the locomotion level of an autonomous vehicle:
- Other topics:
- Pursuit-evasion games from Machine Learning in Games by Jay Scott
- Navigational overview by Bjørn Reese
- Hunter-Prey, Foraging and Flocking strategies implemented in the VehicleGuide 2.0 system by Jan Beutler
- Sensor Based Motion Planning at the Caltech Robotics Group
- Robotic Experiments in Cricket Phonotaxis by Henrik Hautop Lund, John Hallam and Barbara Webb
- Peter Stone's page on RoboSoccer and his papers.
- Procedural Animation controllers in the materials for Matthew Lewis' VRML course: Building 3D Virtual Environments
- Dynamically Simulated Characters in Virtual Environments (1997, 1998) by Jessica K. Hodgins, David Brogan and Ronald Metoyer. Describes autonomous steering behaviors for robot "sheep" and bicycle racers. The sheep are being herded into a pen by a human user playing the part of a Border Collie. The cyclists ride on the same VR race track as a human participant providing both teammates and opponents. The full CG&A paper [PDF 0.4MB] is available online.
- Vectors - Motion and Forces in Two Dimensions (from The Physics Classroom)
- Interactive vector tutorial (from Math Forum)
- On-Line Geometric Modeling Notes (from UC Davis Visualization and Graphics Research Group)
- Vectors in a Plane and Real Vector Spaces (from MATH-abundance)
- xxx [new]