Behavior Tree Iteration Rate

Question

How is a Behavior Tree iterated in a game? For example, let's assume you have an extremely large Behavior Tree with about a hundred Actions/Conditions. If we were to run one action or condition every Frame Tick that would take about 100 Frames to reach the very last Action in the Tree.

So my question is, do we iterate the whole tree until we find a "runnable" action, run it, then return. Or do we iterate the whole tree and run as many actions as we can before getting to an action that takes multiple frames/updates to finish running?

Answer 1

This is the way I see it, but really this is a decision you need to make based on what types of conditions/actions/behaviors you have.

• Actions: Running a function to process data. For example finding a path with A*. These happen in the background and aren't seen by the user. They usually happen in a single frame, but can stretch to a few frames if needed.
• Conditions: A simple data test. For example testing if enemies are in range. Again, these happen in the background and aren't seen by the user. They happen in a single frame.
• Behaviors: An activity in game. For example, following a path. These happen in game, and are usually visible to the user. These will almost never happen within a single frame.

For each iteration on the tree, multiple conditions can be processed. Actions and behaviors are different. This is up to you. You might want actions like finding a path to take place in the same frame as starting to follow the path. Or you may want to find the path, then on the next iteration you start the behavior of following that path.

You may have multiple actions per frame, but since actions can be a bit hefty, you may want to limit some of them. Having ten actions that take "just less than a frame" to run, means you're slowing your game down a lot by running them back to back.

Behaviors will almost always take multiple frames.

So there's an easy solution and a more challenging solution. The easy one is to only ever allow one action per tree iteration. The more challenging is to have a running timer and estimates for how long your actions take to run. If running the next action puts you over budget, then save it for next time.

Answer 2

I simply iterate, in one frame, until the whole tree finishes, or until an action/condition requests to suspend the traversal.

Generally you would design your computation-heavy actions so that they only initiate a request to start their processing (instead of actually doing it there and then), which will then be handled by a different part of the game. You would have some sort of function to check if that computation is finished, then you resume traversing the tree.

Commonly this is done by having a signal called "Running" that your nodes can return (alongside Success or Failure), to indicate to the traversal code that it needs to pause itself.

It also depends on the specifics of your game. If you have a turn-based game, when to traverse is a lot easier to think about (i.e. at the start of the turn).