Behavior trees

Behavior trees are task-switching structures; another such structure is the finite state machine.

These structures solve the problem: given a set of actions, when and to which action do we switch?

Behavior trees have some advantages over finite state machines:

• Modularity — fewer dependencies between components
• Built-in hierarchical structure — actions exist on many levels (one action may have several sub-actions)
• Graph representation — many algorithms exist for examining and working with these structures
• Explicit handling of sequences, fallbacks, and interruptions
  • a sequence runs its children in order and stops at the first one that fails
  • a fallback tries its children in order and stops at the first one that succeeds
  • an interruption lets a more important task take over a running one

Deciding when to switch

There are typically three fundamental reasons to switch:

• Success (i.e., finished walking to X) — continue the sequence
• Failure (i.e., could not find a path to X) — invoke the fallback
• Interruption (i.e., tripping) — do a more important task

How does a behavior tree work?

• ? = fallback — stops at the first child that returns success (behaves like OR)
• -> = sequence — stops at the first child that returns failure (behaves like AND)

Behavior trees are typically driven by a tick that causes the above operations to be performed.

A tick propagates from the root of the tree and starts traversing down through the tree, left to right:

• If a node in the tree returns a failure, the tick moves up and on to the next child.
• If a node in the tree returns a success, the tick moves to the next sequence.
• If a node in the tree returns that it’s running, the tick moves up the tree and back to the root.

Types of nodes

There are two possible types of nodes in behavior trees:

• Actions — can return success, failure, or running; they execute and change the world
• Conditions — can return success or failure; they never change the world