Behavior tree implementation details

Question

I have been looking around for implementation details of behavior trees, the best descriptions I found were by Alex Champarand and some of Damian Isla's talk about AI in Halo 2 (the video of which is locked up in the GDC vault sadly).

However, both descriptions fall short of helping one actually create a BT, one particular question has been bugging me for a while.

When is the tree in a behavior tree evaluated?

Furthermore:

If the tree is in the middle of executing a sequence of actions (patrolling waypoints) and a higher priority impulse comes in (distraction sound) , how to switch to that side of the tree seamlessly without resorting to a state machine like system and if it is decided that the impulse was irrelevant (the distraction is too far away to affect this guard), how to go back to the last thing that the guard was doing ?

I have quite a few questions like this and I don't wish to flood the board with separate queries so if you know of any resource where questions like these can be answered I would be very grateful.

Answer 1

If you have the computational resources, it is best to evaluate the tree every frame. If CPU time becomes an issue, you may switch to event-driven BTs or update with lower frequency.

Behavior Switching

To properly handle switch to a different behavior, it is vital, that all your nodes enforce an init-update-done lifecycle. That is, prior to switching to a different behavior in a selector, you call done() on the subtree you are terminating and then init() on the new subtree, only after both finish you start sending updates.

The init/done calls propagate through the tree the same way regular updates do. In the articles on AIGameDev, Alex supposes, that the init/done calls are instantaneous, but if your game features more complex logic, it might be useful to allow the init and done operations to take more than one frame, that is the node can now have much more states:

• none (prior to initialization)
• initializing (the init operation requires more updates)
• running (init finished, executing normal updates).
• stopping (node is requested to stop but requires more updates)
• done (node has finished)

Note that if a selector is about to change which branch is executing, it first signals the currently running branch to stop and only after the branch transitions to "done" does it start executing the new branch. This requires more complex logic in the sequences/selectors/decorator nodes but may save you a lot of headache in the long run. It also lets you to create special nodes that have a whole subtree to perform for when initializing/stopping. E.g. you have a behavior when your character is drinking in a pub, in the init subtree you perform a sitting animation and notify the barman that you want a beer. In the stopping subtree you perform a standup animation a notify the barman that you are leaving.

Handling distractions

If the tree switches to a different subtree upon a sound distraction only to realize it was not actually a distraction and switches back, you are doing something wrong. The subtree should be switched only when the impulse is actually considered important. A parallel node may help you to run some more complex code to evaluate the impulse without interrupting the guard behavior. If the code in the parallel branch decides the distraction is important, it sends the impulse to the selector to do the actual change (e.g. sets a variable).

If you for some reason need to maintain state when the NPC switches to a different behavior, you may have two kinds of operations to stop execution of a subtree:

1. Stop - stops the execution and clears state (as usual)

2. Suspend - stops the execution without clearing the state (e.g. a sequence node remembers the index of currently executed node).

A selector then may decide whether to stop or suspend the tree. Once again, you may need intermediate state "suspending" to let suspend take more than one frame.

Answer 2

I've been working to implement a behavior tree in Unity for the last week or two, now, and I've found that it's much better to use very generalized task nodes when developing these things. For example: It seems (to me, at least) to be a lot simpler to have only one type of sequence and one type of selector, and to have "decorator" nodes that can change the behavior of whatever comes after them.

Additionally, I've found that polling from the root out, every frame, is a bit wasteful when one is only really executing one task at a time, so I've been using a simple interrupt system, much like most modern CPUs do, rather than constantly polling a piece of hardware that is doing a task that can take quite some time to check if it's done yet, and keeping a reference to the "current task" (lowest level) that is being executed.

When the interrupt is sent, depending on the reason for the interrupt, the current action decides how to handle it.

If the interrupt is coming back because the task either completed successfully or failed, it tells its parent task to move on past it, and to continue with its operations.

If the interrupt is coming back because of a stimulus that took higher priority than the current task being executed, I set the current task (the reference I mentioned earlier) to the root of the tree, and poll. If your system is set up properly, your higher priority nodes should be earlier in the base few layers' selectors' lists, and so should be found needing before whatever it was that the agent was doing earlier would even be checked if it should execute.