Behavior trees (BTs) are increasingly deployed in the games industry for decision making and control of non-player characters (NPCs, also named agents or actors) and gameplay. Behavior trees are incrementally created from reactive and goal-oriented behaviors by hierarchically compositing purposeful sub-behaviors. Composite behaviors (branches in the tree) decide which child behavior to run when and react to changing behavior execution states. Leaf nodes of the behavior tree check conditions, or control the execution of game state affecting actions. This chapter introduces a basic behavior tree concept, describes how behavior tree traversal drives NPC decision making via an example, and sketches a memory-compact implementation.
TopBackground
Scripting and finite-state machines (FSMs) have been the primary tools to model decision making, and action selection and execution for computational behavior of agents in games (Champandard, 2007).
Scripting offers the most direct control over the gameplay in a scene. However, it also complicates reuse, analyzation, and maintenance of behaviors, especially if the controlled entities should remain reactive to the actions of the player (Champandard, 2007).
Finite-state machines provide a simple and intuitive mechanism to model reactive behavior (Champandard, 2007). In games, finite-state machines aren’t used to accept languages, but to process and react to continuous streams of events or inputs (Fu & Houlette, 2004). A (finite) set of states corresponds to behaviors while (agent external or internal) events trigger transitions between states.
Diagrams of finite-state machines look conceptually simple but they hide many details necessary to implement them as Isla (2005) observes, e.g., when to follow a transition? Some transitions are voluntary, e.g., when a guard decides to idle instead of searching on for an intruder, while others are forced by an event, e.g., when a trespasser enters a guard’s viewing field and the guard transitions from idle to the attack state.
The more states and transitions are used, the more labor intensive it gets to maintain and understand the flexible transition wiring. Hierarchical finite-state machines (HFSMs) lower this complexity by enabling reuse of smaller HFSMs inside of states of higher-level HFSMs and by allowing transitions between states in the different levels of the hierarchy (Millington, 2006). Though even with hierarchical finite-state machines Isla’s critique and the complexity due to the ad-hoc transition wiring remains, e.g., there is no way to express sequences or explicit selection of behaviors in a straightforward manner with HFSMs.
Isla’s article from 2005 about the artificial intelligence (AI) in Halo 2 describes how behavior trees can be used to handle the complexity of behavior modeling in games. Since then, different flavors of behavior trees have been deployed in addition to finite-state machines by increasing numbers of game developers (Champandard, 2011; Hecker, 2009; Pillosu, 2009).