The behavior tree is another pattern used to represent and control the logic behind AI agents. They have become popular for the applications in AAA games such as Halo and Spore. Previously, we have briefly covered FSMs. They provide a very simple, yet efficient way to define the possible behaviors of an agent, based on the different states and transitions between them. However, FSMs are considered difficult to scale as they can get unwieldy fairly quickly and require a fair amount of manual setup. We need to add many states and hard-wire many transitions in order to support all the scenarios, which we want our agent to consider. So, we need a more scalable approach when dealing with large problems. This is where behavior trees come in.

Behavior trees are a collection of nodes, organized in a hierarchical order, in which nodes are connected to parents rather than states connected to each other, resembling branches on a tree, hence the name.

The basic elements of behavior trees are task nodes, where states are the main elements for FSMs. There are a few different tasks such as Sequence, Selector, and Parallel Decorator. It can be a bit daunting to track what they all do. The best way to understand this is to look at an example. Let's break the following transitions and states into tasks, as shown in the following figure:

Let's look at a Selector task for this behavior tree. Selector tasks are represented with a circle and a question mark inside. The selector will evaluate each child in order, from left to right. First, it'll choose to attack the player; if the Attack task returns success, the Selector task is done and will go back to the parent node, if there is one. If the Attack task fails, it'll try the Chase task. If the Chase task fails, it'll try the Patrol task. The following figure shows the basic structure of this tree concept:

Test is one of the tasks in the behavior trees. The following diagram shows the use of Sequence tasks, denoted by a rectangle with an arrow inside it. The root selector may choose the first Sequence action. This Sequence action's first task is to check whether the player character is close enough to attack. If this task succeeds, it'll proceed with the next task, which is to attack the player. If the Attack task also returns successfully, the whole sequence will return as a success, and the selector is done with this behavior, and will not continue with other Sequence tasks. If the proximity check task fails, the Sequence action will not proceed to the Attack task, and will return a failed status to the parent selector task. Then the selector will choose the next task in the sequence, Lost or Killed Player? The following figure demonstrates this sequence:

The other two common components are parallel tasks and decorators. A parallel task will execute all of its child tasks at the same time, while the Sequence and Selector tasks only execute their child tasks one by one. Decorator is another type of task that has only one child. It can change the behavior of its own child's tasks that includes whether to run its child's task or not, how many times it should run, and so on. We'll study how to implement a basic behavior tree system in Unity in Chapter 6, Behavior Trees.