TreeSharp: Overview

From Buddy Wiki

Jump to:navigation, search

If you have never used Behavior Trees before, we strongly suggest you glean the information from the TreeSharp Wiki article, first. Please pay particular attention to the video introductions to Behavior Trees.


Introduction

Behavior Trees (BT) are nothing more than a classic computer-science tree structure. However, unlike the binary tree we learned in school—which was limited to two children, left and right—a BT may have N children.

The BT is executed by simply walking the tree. Each node in the tree represents a piece of logic to be evaluated by the tree-walker. As far as the TreeSharp tree-walker is concerned, all nodes in the tree are the same type—Composite.

Composite is the base class from which all other TreeSharp node types are implemented. In all candor, Composite is a poorly chosen name, and a class name of "Component" or "TreeNode" would have been better (however these names were taken from the industry-agreed terminology for Behavior Trees used in most Triple A game studios around the world [including developers of games such as Halo, Spore, The Sims, and the like])[1]. Unlike the implication of its name, a TreeSharp Composite implements neither the Composite Pattern, nor does it inherently allow multiple child nodes. (In fact, if you examine the classic Composite Pattern, the TreeSharp Composite implements the "Component" role in the pattern, thus further adding to the confusion.) In short, when you see TreeSharp's Composite class, rename it in your head to "Component" or "TreeNode".


It is convenient to think of the 'types' of nodes provided by TreeSharp as falling into one of the following categories:

  • Actions
Actions are atomic[2] units that issue directives to the WoWclient. When visited by the TreeSharp tree-walker, an Action returns a value of success, failure, or "not done yet". If an action is defined as having no return value (e.g., void), then the tree-walker treats this action as implicitly returning 'success'. (Please note: "having no return value" is not the same thing as "failing to return a value"—the former is a design decision, the latter is a bug.)
  • Conditionals
Conditionals determine whether or not certain nodes should be visited as the TreeSharp tree-walker evaluates the tree.
  • Containers
Containers are collections that hold zero or more child nodes. The child nodes contained therein may be Actions, Conditionals, or even other Container nodes. The container evaluates its children when the TreeSharp tree-walker visits the container node. How the container evaluates its children depends on the particular type of container employed. (This should become clear, shortly.) Once evaluated, the container returns a value of success, failure, or 'not done yet' to the tree-walker.

TreeSharp Structure

We start exploring the TreeSharp framework by looking at its overall structure via a UML class diagram...

Error creating thumbnail: convert: no decode delegate for this image format `/tmp/magick-XXb0Me28' @ constitute.c/ReadImage/503.
convert: missing an image filename `/tmp/transform_d93b621cbaed-1.png' @ convert.c/ConvertImageCommand/2800.

A brief summary of each class is listed in the section below. You will also find more information about each of the significant classes in this diagram by visiting the Related links, at the bottom of this page.


Overview of the TreeSharp Classes

TreeSharp is designed such that each visited node returns one of three values: "success", "failure", or "not done yet". The next node for the tree-walker to visit is determined by the implementation behavior of the specific Composite.


TreeSharp provides for issuing directives to the WoWclient through the following classes:

  • Action
Actions are responsible for accomplishing the work of a behavior tree. For all practical purposes, this means TreeSharp uses these nodes to issue directives to the WoWclient.


The true power of the TreeSharp implementation rests in the containers it provides. All containers hold N child nodes. However, the type of the container determines which of the children will be visited, and what will be Container's return value to the tree-walker. The Containers defined by TreeSharp are the following:

  • PrioritySelector
The PrioritySelector visits each of its child nodes from top-to-bottom. If a child node reports "not done yet", the PrioritySelector continues to visit that child node until a definitive 'success' or 'failure' is returned. If a child node reports 'failure', the PrioritySelector moves to the next child node, and asks for its status. If a child node reports 'success', the PrioritySelector reports 'success' to the tree-walker, and the rest of the PrioritySelector's children will not be evaluated.
Since nodes are always visited top-to-bottom, there is an inherent priority implied by the order of the child nodes within the selector. If control makes it to the bottom of the PrioritySelector then all the children have reported 'failure'. The PrioritySelector subsequently reports 'failure' to the tree-walker.
To summarize, a PrioritySelector succeeds as soon as any of its children report 'success'. The PrioritySelector fails if all of its children report 'failure'.
  • Sequence
Like PrioritySelector, the Sequence contain also visits each of its child nodes from top-to-bottom. What differs, is how Sequence defines 'success' when visited by the tree-walker. If a child node reports "not done yet", the Sequence continues to visit that child node until a definitive 'success' or 'failure' is returned. If a child node reports 'success', then Sequence continues with the next node, and asks for its status. If a child node reports 'failure', Sequence ceases to evaluate child nodes, and reports 'failure' to the tree-walker.
If control makes it to the bottom of the Sequence, then all children have reported success. The Sequence subsequently reports 'success' to the tree-walker.
To summarize, a Sequence succeeds when all of its children report 'success'. A Sequence fails as soon as one of its children report 'failure'.
  • Switch
Like the similarly named programming construct, the Switch evaluates a discriminator, then select only one of several possible nodes to run. The selected node is responsible for returning success, failure, or "not done yet".
The Switch node is also capable of supporting the concept of a 'default' node choice, where no match is found for the discriminator. If there is no match to the discriminator, and no default node, then Switch returns 'failure' to the tree-walker.


TreeSharp chooses to couple Conditionals with Containers to implement the classic Decorator Pattern. As such, you will not see a standalone concept of Conditional within TreeSharp. The Decorators provided by TreeSharp include:

  • Decorator
A Decorator contains a conditional predicate, and a single TreeSharp node—usually representing some form of action, but it may just as easily be a container or another decorator. If the Decorator's predicate evaluates to false, then 'failure' is reported to the tree-walker. If the Decorator's predicate evaluates to 'true', then the associated child node is evaluated, and the child node's return value is reported to the tree-walker.
In general, a Decorator is used in conjunction with some form of Selector container.
  • DecoratorContinue
The DecoratorContinue is very similar to the Decorator—it differs in how it evaluates its predicate. If the DecoratorContinue's predicate evaluates to false, then 'success' is reported to the tree-walker, and the associated child node is never evaluated. If the DecoratorContinue's predicate evaluates to 'true', then the associated child node is evaluated, and the child node's return value is reported to the tree-walker.
In general, a DecoratorContinue is used in conjunction with a Sequence container.
  • Wait
Wait is a convenience decorator that inserts delays into sequences of actions. Wait returns "not done yet" to the tree-walker until the timer expires. Once the timer expires, Wait returns 'failure' to the tree-walker.
Wait also takes a predicate. As long as the predicate is 'false', the wait proceeds. If the predicate evaluates to 'true' before the timer expires, then Wait evaluates the associated child node and returns its status to the tree-walker.
In general, a Wait is used in conjunction with some form of Selector container.
  • WaitContinue
WaitContinue is a convenience decorator that also inserts delays into sequences of actions. WaitContinue returns "not done yet" to the tree-walker until the timer expires. Once the timer expires, WaitContinue returns 'success' to the tree-walker.
WaitContinue also takes a predicate. As long as the predicate is 'false', the wait proceeds. If the predicate evaluates to 'true' before the delay expires, then WaitContinue evaluates the associated child node and returns its status to the tree-walker.
In general, WaitContinue is used in conjunction with a Sequence container.


There are three classes provided by TreeSharp that are largely of no interest to behavior developers. These classes are used to facilitate the implementation of TreeSharp itself, and will not be further discussed in the Wiki:

  • Composite abstract class
This is the base class to all node types implemented by TreeSharp.
  • GroupComposite abstract class
This is the base class to all 'container'-type classes implemented by TreeSharp. The primary value added by this base class is it provides support for harboring N children.
  • Selector abstract class
This is the base class for all 'selector'-type classes implemented by TreeSharp. The primary characteristic of a Selector is it reports 'success' to the tree-walker when any one of its children report 'success'.


A Learning Plan

You are most welcome to start your study with any of the nodes (listed below in the "Related (links)" section). If you are new to TreeSharp and behavior trees, you may find the following order of study to be helpful:

From there, you may find one of the container-type nodes will further your understanding:

Next, learn about the role of Decorators:

Last, learn about the Switch—as it is easily the most involved of the TreeSharp node types:

The following supplemental articles should deepen your overall understanding:


Footnotes:

  1. Naming things 'correctly' is undoubtedly the hardest part of software development. These types of mistakes are made all the time by even the most seasoned of developers. We offer no criticism here—we merely seek to avoid confusion.
  2. "Atomic" here is used in the computer-science sense, meaning 'indivisible'



Related (links):

Articles:




Licensing
Most content in the Buddy Wiki is made available under the CC-BY-NC-SA license. However, in keeping with the spirit of TreeSharp's licensing, the content on this page has been made available under the less restrictive GNU Public License (GPL).