Behavior Tree with interrupted sequence

Question

I'm reading up on Behavior Trees and would like to know how a good implementation for a scenario where the conditions can change or where a selector with a higher priority interrupts the current one.

To keep it simple I will use only tree "states".

FLEE

IDLE (/DECIDE NEXT POSITION)

WALK

WALK is running as long as the player has a target position. IDLE is running when player reached position or if player has no position.

Now to my question. FLEE should always interrupt the other nodes. How is this achieved in a good way?

I know this can be done in a lot of different ways so I just want to know how you would solve it.

(Sorry for no fancy node graphic. I'm on my mobile)

Answer 1

Firslt remember that a decision tree is not the same as a state machine. You have listed three 'states' but they are not exactly 'states', they are compositions of other actions. Because of this, I will call them 'nodes'.

In the 'idle' and 'walk' nodes, make the logic poll for something to flee from after every fixed time period or step. If there is something to flee from, transition the logic to fleeing.

Behaviour trees are like compositions of coroutines - they must be cooperative to make sense.

---

If you have not already done so, I recommend reading Chris Simpson's Gamasutra article about behaviour trees.

It was an image of his that inspired this answer:

Note that all of these nodes are very small, quick, actions/checks. That is a very important principle of behaviour trees - to make sure that all nodes are small, fast actions and that longer running actions are merely the repetition of smaller actions, hence walking can consist of a sequence of moving once and then checking for danger without incurring overhead. If danger has been spotted, the walk 'fails' and some higher up node transitions the AI to 'flee'.

Answer 2

Interrupt masks (sets) and ordering resolution by priority.

Some general rules:

• any unhandled interrupts abort actions
• interrupts are handled in the order of most important to last important
• while they're handled, the current and less important interrupts are temporarily disabled
• disabling interrupts means preventing them from entering the interrupt set (bitwise mask or excluded set query)
• the interrupt set can be queried by the actions at convenient times to stop execution prematurely (forced aborting is possible but not always convenient)

The tree would look like this (increased indent = subnodes):

- <some AI behavior>
- if HIGH_PRIORITY_EVENT in current_interrupt_set do
  - disable interrupts HIGH_PRIORITY_EVENT and LOW_PRIORITY_EVENT
    - <handle this interrupt>
- if LOW_PRIORITY_EVENT in current_interrupt_set do
  - disable interrupts LOW_PRIORITY_EVENT
    - <handle this interrupt>

This structure is pretty much the same as that of exception handlers in code. (And, in fact, something not told often enough - behavior trees are basically abstract syntax trees describing code that will be cooperatively executed in parallel - so they have lots of structural similarities with code).

I implemented interrupt set as an integer where bits specify interrupts (not planning to have more than 32) but an unordered set should be fine for this as well.

Answer 3

I believe ultimately you can implement this as a push down automaton (PDA). The high level design is that you want some actions to take priority over others, so lets delve deeper.

It's actually not that much deeper.

(IDLE) --[NO TARGET POSITION] --> (IDLE)

(IDLE) --[TARGET POSITION]--> (WALK)

(WALK) --[NO TARGET POSITION] --> (IDLE)

(IDLE) --[UNDER ATTACK] --> (FLEE)

(WALK) --[UNDER ATTACK] --> (FLEE)

(FLEE) --[NO TARGET POSITION, NOT UNDER ATTACK] --> (IDLE)

(FLEE) -- [TARGET POSITION, NOT UNDER ATTACK] --> (WALK)

Turns out you can use an FSM. It's possible your example is not truly representative of what you are trying to do. Interestingly enough every FSM can be represented with a directed graph which is also how you represent a behavior tree. So you could represent your behavior tree with a directed graph and equivalently a FSM.

You could in fact create behavior tree's which are not representable by an FSM, but they probably wont make sense. To do so in a manner that is not "repairable" you would need to create a behavior tree where a node has a path to two different nodes for the same condition. This seems to be an unlikely condition because it probably doesn't make sense. Consider a behavior tree where being attacked resulted in fleeing and idle.

Furthermore, if you want your character to return to their initial state AFTER a behavior, you can use a PDA. In this case you simply PUSH their current state, and then continue on your merry way to the next state. When it is completed it pops your previous state and returns to it.

IDLE -> WALK -> (UNDER ATTACK) -> PUSH STATE (WALK) -> FLEE -> (NOT UNDER ATTACK, TARGET POSITION) -> (POP) -> WALK