4
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ I would implement a stack based state machine. Check this tutorial gamedevelopment.tutsplus.com/tutorials/… each state starts by checking if a state should transition \$\endgroup\$ – Felsir Jan 2 '16 at 14:29
  • \$\begingroup\$ Thanks, but I am not interested in FSMs since I have used them before and are now looking into Behavior Trees in particular. \$\endgroup\$ – Mattias Jan 2 '16 at 15:48
  • 1
    \$\begingroup\$ Possible duplicate of Preempting Behavior Trees \$\endgroup\$ – Seivan Jun 7 '18 at 16:24
4
\$\begingroup\$

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:

enter image description here

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'.

\$\endgroup\$
  • \$\begingroup\$ The image isn't exactly compatible as it describes a sequence. The question related more to a selector that picks a an action to commit to. In this case, Flee should have a higher priority in a selector. Also your answer, doesn't tackle what should happen to a running node if the tree evaluates higher priority nodes such as "should_flee" == true while WALK is active. \$\endgroup\$ – Seivan Mar 30 '18 at 16:51
  • \$\begingroup\$ @Seivan As I say in the question, each action should be quick. A walk action should move once and then return true so that other actions can be taken (i.e. a check to see whether the entity should flee). You seem to be imagining each action in the diagram as something that is continuously running, but they are in fact very short actions. 'Eat Food' would not hang around continually eating, it would consume a small amount of food, return and then repeat the sequence - continually polling to make sure it's safe to eat and to make sure the entity only eats when it's hungry and has food. \$\endgroup\$ – Pharap Mar 30 '18 at 18:54
  • \$\begingroup\$ What's the point of having the Running status, if each action must be quick? The whole point of Running is to allow actions that has to tick through before returning a real status. In my case, the Steering Behaviours could be running and stay like that for a while until they're interrupted. \$\endgroup\$ – Seivan Apr 1 '18 at 20:06
  • \$\begingroup\$ @Seivan Again, it seems you're imagining things like 'Running' as some long running action. They're not long-running actions, they're a sequence of checks and actions. The sequence happens once per frame so that the AI has chance to check for things that would interrupt it. Remember that to 'run', something moves a tiny amount per frame, so there's plenty of time to perform other checks like 'are the dangers gone?'. If you're not happy with my answer you're welcome to write your own. \$\endgroup\$ – Pharap Apr 2 '18 at 19:26
  • \$\begingroup\$ I am just interrogative because I am trying to figure it out myself. A running tasks could be an async action that might take some time to complete, meaning it could actually remain in that state for quite some time, so I am wondering how to handle interruptions of it and more importantly, what is an interruption really if not another set of actions. \$\endgroup\$ – Seivan Apr 5 '18 at 10:41
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the answer. I am looking for a more practical use of the different node types already defined in a behavior tree (Sequence, Selector, Priority Selector, Condition, Parallel etc) \$\endgroup\$ – Mattias Jan 2 '16 at 15:51
  • \$\begingroup\$ @Mattias, why would you restrict yourself to those nodes? Obviously they are just the foundation, not the complete set. There have to be extensions just to make the AI actually do something. \$\endgroup\$ – snake5 Jan 3 '16 at 8:22
  • \$\begingroup\$ I'm not restricting me to only these nodes, but wanted an more practical and scenario based example on how to use them. \$\endgroup\$ – Mattias Jan 3 '16 at 8:49
  • \$\begingroup\$ @Mattias I was the same, and I was looking for something within the "spec" of BTs to use, until I realized there is no official spec, and there is nothing right now that helps with the notion of reactive behaviour or abortions. This suggestion is actually the appropriate path. \$\endgroup\$ – Seivan Sep 3 '18 at 10:03
-1
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.