Interaction with Groups of Autonomous CharactersCraig ReynoldsResearch and Development GroupSony Computer Entertainment America919 East Hillsdale BoulevardFoster City, California [email protected]://www.red.com/cwr/[email protected]: autonomous characters, behavioral animation, steering behaviors, flocks, real time, spatial data structures.AbstractThis paper presents a methodology for constructing large groups of autonomous characters which respond in real time to the user’s interaction, as well as to each other and their envi-ronment. The characters are based on steering controllers under the direction of a simple mental model which mediates between several conflicting behavioral goals. The characters are represented graphically by 3d models with a library of animated motions which are cho-reographed by the behavioral controllers.IntroductionThe real world is a busy and crowded place, full of people, animals and vehicles. In con-trast, many game worlds are relatively static and empty. Usually one character moves under the player’s control, a few other characters move autonomously, and maybe a few bits of the environment move in predetermined cycles. This paper describes techniques for populating a game world with large numbers of autonomous characters which behave in a sensible fashion. As required by their role, they can easily coordinate with or react to, each other, the environment, and the user’s avatar.Three key concepts are discussed in this paper. First, behavioral models: the control pro-grams which serve as the brains of the autonomous characters. Second spatial data struc-tures which are used to accelerate locality queries to allow real time performance. Third, the techniques used to drive animation from behavioral models.A real time demonstration application, a "mini-game", is presented and used as an example of the concepts presented in this paper.Related WorkAutonomous characters of some sort exist in most games. Any character not directly con-trolled by a human player must have some level of autonomy. This includes enemies, allies and sometimes, neutral bit players. The historical trend has been from very simplistic auto-nomous characters (which may just blindly follow scripts with little or no ability to react to their dynamic environment) towards nimble reactive characters [Reyn99], and finally towards characters which can learn [Gran98], reason [Lair00], and plan [Fung99].The concepts presented here are an outgrowth of earlier work on simulating bird flocks [Reyn87] and on the underlying concept of steering behaviors [Reyn99]. An extensive bibli-ography on autonomous characters can be found in [Reyn99]. Directly relevant to the topic of this paper are existing games that contain an element of large groups which interact with, or respond to, the actions of the human user. Many of the Maxis simulation games have this property: SimCity, SimAnt, SimTower, and now: The Sims. Also games in the Lemmings and Populous franchises feature large number of autonomous characters which respond to the user. And in a slightly different vein, games like Myth and Warcraft allow troops to be grouped together and given a goal, which they pursue while avoiding obstacles and each other. Koei’s upcoming game Kessen looks as if it will feature large groups of horse-mounted soldiers as an element of gameplay.Behavioral ModelsAutonomous characters depend on some sort of behavioral model or control program to drive them. In a virtual world, objects might be: static, periodic (running an animation cycle, a flickering flame for example), user controlled (like the human player’s avatar) or they can have some degree of autonomy. Autonomous characters are procedurally driven by a con-trol program which implements a behavioral model. This control program maps the charac-ter’s environment into character actions. The character’s environment consists of its virtual world (external environment, perhaps filtered through locality or its sensory perception) and its memory or other simulated mental processes (internal environment). A character’s de-gree of autonomy can vary widely. On one hand an autonomous "car" might simply drive along a street, stopping when it comes to a red light. (Note that for the purposes of this dis-cussion we will lump together a vehicle and its driver/pilot into a single entity.) On the other hand a character might have all the freedom of action afforded to the human player so it can play the role of an enemy or companion.The characters described in this paper are based on a very simple physical model: a point mass with velocity and a local frame of reference (an orthonormal basis for a coordinate system). The local coordinate system is updated each simulation step to move with the po-sition of the mass and to be aligned with its velocity. The character moves by applying a fi-nite steering force to modify its velocity, and hence its position. Velocity is capped to roughly simulate drag or friction. The local coordinate system is used to attach an animated geo-metrical model to the point mass. As a result the position, velocity, orientation, and visual appearance of the character is driven by the behavioral model, primarily through control of the steering force. (For a more detailed description of these concepts see [Reyn99].)Other kinds of characters can express their behaviors with different kinds of action. A char-acter’s body could be represented by a physically-based dynamically balanced simulation of walking, providing both realistic animation and behavioral locomotion. While a more me-chanical "character," like an autonomous airplane or spaceship, can be realistically por-trayed with relatively simple distributed-mass rigid dynamic model. Another approach for ar-ticulated (legged) motion is to use a simple (say point-mass-based) locomotion model and an adaptive animation model, like an inverse-kinematics driven walk cycle, to bridge the gap between abstract locomotion and concrete terrain. Or a character’s motion can be restricted to a fixed set of pre-animated segments (walk, run, stop, turn left...) which are either select-ed discretely or blended together.eatsleephuntdrinkFigure 1: Finite State Machine diagram showing states and transitions between them for a simple predator character.An autonomous character can have multiple distinct behavioral states. For example a fighter jet