architecture - Difference between Decision Trees & Behavior Trees for Game AI

What are some differences between Decision Trees and Behavior Trees for AI Game Development? For what applications would you use one over the other?

Answer

The two are pretty different. The real indicator is in the names. Decision trees are just for making decisions. Behavior trees are for controlling behavior. Allow me to explain. A major difference in the two is the way they are traversed, likewise the way they're laid out and the node 'types' are different.

Decision trees are evaluated from root to leaf, every time. For a decision tree to work properly, the child nodes of each parent must represent all possible decisions for that node. If a node can be answered "Yes, No, Maybe", there must be three children, Yes node, No node and Maybe node. This means there's always some lower node to traverse, until reaching an end node. The traversal is always down. Graphical form:

Pretty simple. We start at the root, and based on some evaluation, choose 1, 2 or 3. We choose 3. Then we do some other evaluation and choose B or B... Well I reused the graphic from below, sorry. Pretend the B on the left is magic B.

Behavior trees have a different evaluation. The first time they are evaluated (or they're reset) they start from the root (parent nodes act like selectors) and each child is evaluated from left to right. The child nodes are ordered based on their priority. If all of a child node's conditions are met, its behavior is started. When a node starts a behavior, that node is set to 'running', and it returns the behavior. The next time the tree is evaluated, it again checks the highest priority nodes, then when it comes to a 'running' node, it knows to pick up where it left off. The node can have a sequence of actions and conditions before reaching an end state. If any condition fails, the traversal returns to the parent. The parent selector then moves on to the next priority child. I'll attempt a graphical form here:

The traversal starts at the root, goes to child 1, checks the child condition (something like "any enemies near by?"). The condition fails, and the traversal moves back up the tree to move on to node two. Node 2 has an action that's performed (maybe something like finding a path). Then a behavior (something like following the path). The following path is set to running and the tree returns its state as running. The nodes that failed or completed are returned to 'Ready'. Then the next time we check, we start again with the highest priority node. It fails again, so we proceed to node two. There we find we have a behavior running. We also find the behavior has completed, so we mark it completed and return that. The tree is then reset and ready to go again.

As you can see the behavior trees are more complex. Behavior trees are more powerful and allow for more complex behavior. Decision trees are easy to understand and simple to implement. So, you'd use behavior trees when you want more complex behavior, or more control over the behavior. Decision trees can be used as part of a behavior tree, or used alone for simple AI.

Some good understanding of how behavior trees are parsed can be found here.