# Behavior trees

> My notes on behavior trees: task switching, ticks, and how the different node types work.

Author: [Luis Padron](https://thoughtsonthings.io/about/)

Canonical URL: https://thoughtsonthings.io/writing/behavior-trees/

Published: 2022-11-20

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?

![A behavior tree with a fallback root that can eat a sandwich, eat an apple, or run a sequence of opening a banana and then eating it](https://thoughtsonthings.io/_astro/tree.fCh9QFas.svg)

- `?` = 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