jjacobsson asks about behavior trees: “What is the root conceptually? How does it deal with events? Is the tree evaluated from the root down to a leaf often / all the time?”
The first thing to note is that behavior trees are rather flexible, so they can be applied in a variety of different ways. However, certain approaches are more common that others and maximize the benefits that behavior trees have to offer. I’ll outline these in the rest of this article.
The Main Behavior
The root of the tree is essentially the top-level task. So, you can consider the root task as representing the overall behavior. This task is decomposed recursively into sub-tasks that accomplish simpler behaviors that make up the whole (as explained here).
In practice, the whole tree is often called BEHAVE, and registered in the lookup table so it is accessible to the game logic in a data-driven way. The first few nodes from the root behavior typically do the following:
Repeat the whole behavior no matter how it terminates.
Handle any kind of failure or error gracefully.
Select from multiple sub-behaviors based on the situation.
For a soldier in first-person shooter, the sub-behaviors would provide appropriate responses for the different states of mind: IDLE, SUSPICIOUS and ALERT.
Reaction Tree for Cosmetic Events
Certain events aren’t very important, but they present an opportunity for providing an extra level of believability. For example, when a soldier is on guard and sees a colleague patrolling in a different direction, the behavior could react to that by looking at the other soldier and making a comment.
This kind of cosmetic detail can be handled in a separate REACT tree that gets executed whenever there’s an event (e.g. actor appear). This tree would contain logic to dispatch the event by selecting the appropriate reaction. That whole sub-tree would run concurrently with the main behavior, and would require a set of resource allocators to make sure there are no conflicts. (They are decorators.)
Figure 1: Resource allocators (black) to synchronize subtrees.
Dealing with Opportunities and Threats
Only certain events affect the main tree (as discussed in this article on strategies for handling events purposefully). Events are only relevant for the main behavior if they:
Open up new opportunities.
Present new threats.
The AI logic deals with those by aborting subtrees and enabling other subtrees. In practice, you can achieve this in different of ways:
Using a dynamic selector which keeps rechecking for higher-priority behaviors on a regular basis.
Running conditions in a parallel task for monitoring each tree’s assumptions, to bail out when there’s a problem.
Figure 2: Parallel conditions for monitoring subtrees.
Generally speaking, the behavior is NOT evaluated from the root each update. This would make it more of a decision tree (i.e. a classifier) with poor support for executing and monitoring behaviors over time. For instance, if you reset a behavior tree, then typically the sequences would be reset everytime.
However, as I mentioned, the concept of the dynamic selector and having conditions running in parallel with whole subtrees means there’s always some aspect of the logic that’s active high-up in the tree to deal with special case events. This logic is setup as necessary by the designers, and sprinkled around the tree liberally.
Figure 3: Evaluating a behavior tree incrementally.
In effect, this gives you the benefits of responsiveness and concurrency without having to re-evaluate the tree each frame from the root to adapt to new situations. That would be Memento-style AI which is often used to apply planners in practice, which turns out to be a rather brute force solution in practice.