Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 42 down vote accepted

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:

enter image description here

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:

enter image description 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.

share|improve this answer
    
Great explanation and illustrations. So when you say "If all of a child node's conditions are met..." do Selectors and Sequences contain conditions or only leaf nodes, ie the Actions? –  Free Lancer Mar 25 '13 at 16:30
1  
The child nodes are behaviors, actions, conditions or selectors with more children. They're evaluated from left to right. –  Byte56 Mar 25 '13 at 17:41
    
Great post, though I think I still have an outstanding question (will post separately). What did you use to create the animated GIFs? –  me-- Aug 30 '13 at 9:49
    
I used GIMP. Each frame is a layer. Thanks. –  Byte56 Aug 30 '13 at 13:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.