Using Behavior Trees and Events together

Question

I am beginning to work with behavior trees and am unsure how events should be handled within the tree. Lets say we have a space game where the player is dogfighting with a handful of other ships, some friendly some not. The player destroys a ship and the rest of the hostile ships should then start to retreat.

How was should the shipWasDestroyed event effect the other ship's behavior trees so that they start running the retreat behavior?

One way I could think of doing this is have all the conditions I care about be high level nodes that effectively state change the ship. This would mean I'd have to check all of these state change conditions on every frame the behavior tree was run, even if they are very rare occurrences. I'd prefer not doing this for performance and complexity reasons.

From looking at the Halo papers on behavior trees it seems that they handled this by dynamically placing nodes into the tree when the event occurred. It seems like calculating where the new node should go could be problematic depending on the current state of the running behavior.

How is this normally handled?

Answer 1

Behavior Trees are a great way to structure your behavior, but they can suffer from excessive "checking", as you point out. By design, a BT will jump to another branch in the tree if a higher priority behavior becomes available, so the implementation needs a way to check if that's the case.

The easiest and safest way to do it is by polling. The BT will reevaluate the conditions from the top until it either lands on the current node, or somewhere else. This can lead to performance issues, although it won't typically affect your complexity in the same way it would with a state machine, as in a BT you don't have to encode all the connections manually.

A more sophisticated approach is to make the BT event-driven. A possible implementation is that as you traverse the tree, you register observers for the conditions that aren't true (like shipWasDestroyed), until you find a valid node. If any of those observers triggers, you could at that point reevaluate that subtree, to see if you need to switch nodes or not. This approach requires you do to a lot of (error-prone) bookkeeping, but it can be more efficient than simple polling.

An option, somewhat in between, is to cluster certain events and trigger a full reevaluation when they fire. You can call that the "something interesting happened" approach. Traversing the tree then would resolve how to react to that event.

Note that in either case, you'll probably still need to do polling for things like distance checks and whatnot, so it's best to structure your tree so you can combine both approaches (and event-driven conditions are free or very cheap).

Finally, you could keep an external system and inject behavior like Halo. In this case, you won't be able to rely on the natural ordering of the tree, so you'll have to represent priority in a different way. This approach is valuable for reactions that should override normal behavior, like taking a hit or dying. In your case, you could have a list of behaviors with relative priorities associated that trigger based on individual events and override the tree, but be aware that as the complexity of the logic grows, you'll essentially be recreating the BT outside of the tree.

Answer 2

Every game has different design challenges. I would start by drawing out a flow diagram of events. A Behavior Tree typically uses high level "composite" nodes. You can then build out these "composite" nodes into sub-trees.

For instance:

[sequence] --> [Am I Under Attack?] --> [Flee]

The nodes "Am I Under Attack" and "Flee" are composite nodes. You could then build out sub-trees that define how each node works.

[Am I Under Attack] --> [Enemies in range?] --> [return true]

I would consider using both a behavior tree and a state machine to handle game state. Use the behavior tree to "sculpt" low level interactions, then set the state machine based on the result.

Like I said early, every game requires different setups. Always try the simple first approach (K.I.S.S), keep it simple stupid :)