# Preempting Behavior Trees

I'm attempting to get my head around behavior trees, so I'm spiking out some test code. One thing I'm struggling with is how to preempt a currently running node when something of higher priority comes along.

Consider the following simple, fictitious behavior tree for a soldier:

Suppose that some number of ticks have gone by and there was no enemy near by, the soldier was standing on grass, so the Sit down node is selected for execution:

Now the Sit down action takes time to execute because there is an animation to play, so it returns Running as its status. A tick or two goes by, the animation is still running, but the Enemy near? condition node triggers. Now we need to preempt the Sit down node ASAP so we can execute the Attack node. Ideally the soldier wouldn't even finish sitting down - he might instead reverse his animation direction if he only just started to sit. For added realism, if he's past some tipping point in the animation, we might instead to choose to let him finish sitting down and then stand again, or perhaps have him stumble in his haste to react to the threat.

Try as I might, I have not been able to find guidance on how to handle this kind of situation. All the literature and videos I've consumed over the past few days (and it's been a lot) seem to skirt around this issue. The closest thing I've been able to find has been this concept of resetting running nodes, but that doesn't give nodes like Sit down a chance to say "hey, I've not finished yet!"

I thought of perhaps defining a Preempt() or Interrupt() method on my base Node class. Different nodes can handle it how they see fit, but in this case we'd attempt to get the soldier back on his feet ASAP and then return Success. I think this approach would also require that my base Node has the concept of conditions separately to other actions. That way, the engine can check conditions only and, if they pass, preempt any currently executing node before starting the execution of the actions. If this differentiation wasn't established, the engine would need to execute nodes indiscriminately and could therefore trigger a new action before preempting the running one.

For reference, below are my current base classes. Again, this is a spike, so I've attempted to keep things as simple as possible and only add complexity when I need it, and when I understand it, which is what I'm struggling with right now.

public enum ExecuteResult
{
// node needs more time to run on next tick
Running,

// node completed successfully
Succeeded,

// node failed to complete
Failed
}

public abstract class Node<TAgent>
{
public abstract ExecuteResult Execute(TimeSpan elapsed, TAgent agent, Blackboard blackboard);
}

public abstract class DecoratorNode<TAgent> : Node<TAgent>
{
private readonly Node<TAgent> child;

protected DecoratorNode(Node<TAgent> child)
{
this.child = child;
}

protected Node<TAgent> Child
{
get { return this.child; }
}
}

public abstract class CompositeNode<TAgent> : Node<TAgent>
{
private readonly Node<TAgent>[] children;

protected CompositeNode(IEnumerable<Node<TAgent>> children)
{
this.children = children.ToArray();
}

protected Node<TAgent>[] Children
{
get { return this.children; }
}
}

public abstract class ConditionNode<TAgent> : Node<TAgent>
{
private readonly bool invert;

protected ConditionNode()
: this(false)
{
}

protected ConditionNode(bool invert)
{
this.invert = invert;
}

public sealed override ExecuteResult Execute(TimeSpan elapsed, TAgent agent, Blackboard blackboard)
{
var result = this.CheckCondition(agent, blackboard);

if (this.invert)
{
result = !result;
}

return result ? ExecuteResult.Succeeded : ExecuteResult.Failed;
}

protected abstract bool CheckCondition(TAgent agent, Blackboard blackboard);
}

public abstract class ActionNode<TAgent> : Node<TAgent>
{
}


Does anyone have any insight that could steer me in the right direction? Is my thinking along the right lines, or is it as naive as I fear?

• You need to have a look at this document: chrishecker.com/My_liner_notes_for_spore/… here he explains how the tree is walked, not like a state machine, but from the ROOT at each tick, which is the true trick to reactivity. BT should not need exceptions or events. They are pooling systems intrinsically, and reacts to all situations thanks to always flowing down from the root. Which is how preemptivity works, if an external condition of higher priority checks, it flows there. (calling some Stop() callback before exiting the active nodes) – v.oddou Feb 16 '15 at 5:09
• this aigamedev.com/open/article/popular-behavior-tree-design is also very nicely detailed – v.oddou Feb 18 '15 at 3:33

I found myself asking same question as you and I had great short conversation in comment section of this blog page where I was provided with another solution of the problem.

First thing is to use concurrent node. Concurrent node is a special type of composite node. It consists of sequence of precondition checks followed by a single action node. It updates all children nodes even if it's action node is in 'running' state. (Unlike sequence node which must start it's update from current running child node.)

Main idea is to create two more return states for action nodes: "cancelling" and "cancelled".

Failure of precondition check in concurrent node is a mechanism which triggers cancelling of it's running action node. If action node does not require long-running cancelling logic then it will return 'cancelled' immediately. Otherwise it switches to 'cancelling' state where you can put all needed logic for correct interruption of the action.

• Hello and welcome to GDSE. It would be great, if you could open up that answer from that blog to here and in the end link to that blog. Links tend to die, having answer fully here, makes it more persistent. Question has 8 votes now, so good answer would be awesome. – Katu Sep 18 '13 at 17:39
• I don't think anything that brings behavior trees back to finite state machine is a good solution. Your approach seems to me like you need to envision all exit conditions of each state. When this IS actually the drawback of FSM ! BT has the advantage of starting back at the root, this creating a fully connected FSM implicitely, avoiding us to explicitely write exit conditions. – v.oddou Feb 16 '15 at 1:58

I think your soldier may be decomposited into mind and body (and whatever else). Subsequently, body may be decomposited into legs and hands. Then, every part needs its own behaviour tree, and also public interface — for requests from higher or lower level parts.

So, instead of micro-managing every single action, you just send instant-shot messages like "body, sit down for some time" or "body, run there", and body will manage animations, state transitions, delays and other stuff for you.

Alternatively, body may manage behaviours like this by its own. If it has no orders, it may ask mind "can we sit here?". More interestingly, because of encapsulation, you may easily model features like tiredness or stun.

You may even interchange parts — make elephant with intellect of zombie, add wings to human (he wont even notice), or whatever else.

Without decomposition like this, I bet you are on risk of meeting combinatorial explosion, sooner or later.

• Thanks. Having read your answer 3 times, I think I understand. I'll read that PDF this weekend. – me-- Sep 13 '13 at 12:35
• Having thought about this for the past hour, I'm not sure I understand the distinction between having completely separate BTs for mind & body versus a single BT that is decomposed into sub-trees (referenced through a special decorator, with build-time scripts tying everything together into one big BT). It seems to me that this would provide similar abstraction benefits and might actually make it easier to understand how a given entity behaves because you don't have to look across multiple separate BTs. However, I'm probably being naive. – me-- Sep 13 '13 at 13:35
• @user13414 Difference is that you will need special scripts to build tree, when just using indirect access (i.e. when body node must ask its tree which object represents legs) may be enough and also won't require any additional brainfuck. Less code, less errors. Also, you will lose ability to (easily) switch subtree at runtime. Even if you don't need such flexibility, you'won't lose anything (including execution speed). – Shadows In Rain Sep 13 '13 at 19:11

Laying in bed last night, I had something of an epiphany as to how I might go about this without introducing the complexity I was leaning towards in my question. It involves the use of the (poorly named, IMHO) "parallel" composite. Here's what I'm thinking:

Hopefully that's still fairly readable. The important points are:

• the Sit down/Delay/Stand up sequence is a sequence within a parallel sequence (A). On every tick, the parallel sequence is also checking the Enemy near condition (inverted). If an enemy is near, the condition fails and so too does the entire parallel sequence (immediately, even if the child sequence is midway through Sit down, Delay, or Stand up)
• upon failure, the selector B above the parallel sequence will jump down into selector C to handle the interruption. Importantly, selector C would not run if parallel sequence A completed successfully
• selector C then tries to stand up normally, but can also trigger a stumble animation if the soldier is currently in too awkward a position to simply stand up

I think this will work (am going to try it in my spike soon), despite being a little more messy than I had envisaged. The good thing is that I would eventually be able to encapsulate sub-trees as reusable pieces of logic and refer to them from multiple points. That will alleviate most of my concern there, so I think this is a viable solution.

Of course, I'd still love to hear if anyone has any thoughts on this.

UPDATE: although this approach technically works, I've decided it sux. That's because unrelated sub-trees need to "know" about the conditions defined in other portions of the tree so that they can trigger their own demise. Whilst sharing sub-tree references would go some way to alleviating this pain, it's still contrary to what one expects when looking at the behavior tree. Indeed, I made the same mistake twice on a very simple spike.

Therefore, I'm going to go down the other route: explicit support for preempting within the object model, and a special composite that allows a different set of actions to execute when preemption occurs. I'll post a separate answer when I have something working.

• If you really want to re-use subtrees then the logic for when to interrupt ("enemy near" here) should presumably not be part of the subtree. Instead maybe the system can ask any subtree (e.g. B here) to interrupt itself due to a higher-priority stimulus, and it would then jump to a specially marked interruption node (C here) that would handle getting the character back to some standard state, e.g. standing. A bit like the behavior tree equivalent of exception handling. – Nathan Reed Aug 31 '13 at 3:29
• You could even incorporate multiple interruption handlers depending on what stimulus is interrupting. For example if the NPC is sitting and starts taking fire, you might not want him to stand up (and present a larger target) but rather stay low and scramble for cover. – Nathan Reed Aug 31 '13 at 3:33
• @Nathan: funny you mention about "exception handling". The first possible approach I thought up last night was this idea of a Preempt composite, which would have two children: one for normal execution, and one for preempted execution. If the normal child passes or fails, that result propagates up. The preempt child would only ever run if preemption occurred. All nodes would have a Preempt() method, which would trickle through the tree. However, the only thing to really "handle" this would be the preempt composite, which would instantly switch to its preempt child node. – me-- Aug 31 '13 at 7:25
• Then I thought of the parallel approach I outline above, and that seemed more elegant because it doesn't require extra cruft throughout the API. To your point on encapsulating sub-trees, I think wherever complexity arises, that would be a possible substitution point. That could even be where you have several conditions that are frequently checked together. In that case, the root of the substitution would be a sequence composite, with multiple conditions as its children. – me-- Aug 31 '13 at 7:27
• I think Subtrees knowing the conditions they need to "hit" before executing is perfectly appropriate as it makes them self contained and very explicit vs implicit. If that's a bigger concern, then don't keep the conditions within in the subtree, but at the "call site" of it. – Seivan May 31 '18 at 3:17

Here is the solution I have settled on for now...

• My base Node class has an Interrupt method which, by default, does nothing
• Conditions are "first class" constructs, in that they are required to return bool (thus implying that they are fast to execute and never need more than one update)
• Node exposes a collection of conditions separately to its collection of child nodes
• Node.Execute executes all conditions first and fails straight away if any condition fails. If conditions succeed (or there are none), it calls ExecuteCore so the subclass can do its actual work. There is a parameter that allows skipping of conditions, for reasons you'll see below
• Node also allows conditions to be executed in isolation via a CheckConditions method. Of course, Node.Execute actually just calls CheckConditions when it needs to validate conditions
• My Selector composite now calls CheckConditions for each child it considers for execution. If the conditions fail, it moves straight along to the next child. If they pass, it checks whether there is already an executing child. If so, it calls Interrupt and then fails. That's all it can do at this point, in the hopes that the currently running node will respond to the interrupt request, which it can do by...
• I've added an Interruptible node, which is kind of a special decorator because it has the regular flow of logic as its decorated child, and then a separate node for interruptions. It executes its regular child to completion or failure as long as it isn't interrupted. If it is interrupted, it immediately switches to executing its interruption handling child node, which could be as complex a sub-tree as required

The end result is something like this, taken from my spike:

The above is the behavior tree for a bee, which collects nectar and returns it to its hive. When it has no nectar and is not near a flower that has some, it wanders:

If this node was not interruptible it would never fail, so the bee would wander perpetually. However, since the parent node is a selector and it has higher priority children, their eligibility for execution is constantly being checked. If their conditions pass, the selector raises an interruption and the sub-tree above immediately switches to the "Interrupted" path, which simply bails ASAP by failing. It could, of course, perform some other actions first, but my spike doesn't really have anything to do other than bail.

To tie this back to my question, though, you could imagine that the "Interrupted" path could attempt to reverse the sitting down animation and, failing that, have the soldier stumble. All this would hold up the transition to the higher priority state, and that's precisely what the goal was.

I think I'm happy with this approach - especially the core pieces I outline above - but to be honest, it's raised further questions about the proliferation of specific implementations of conditions and actions, and tying the behavior tree into the animation system. I'm not even sure I can articulate these questions yet, so I'll keep thinking/spiking.

I fixed same issue by inventing "When" decorator. It has a condition and two child behaviors ("then" and "otherwise"). When "When" is executed, it checks condition and depending on its result, runs then/otherwise child. If condition result changes, running child is reset and child corresponding to other branch is started. If child finishes execution, whole "When" finishes execution.

The key point is that unlike initial BT in this question where condition is checked only at the sequence start, my "When" keeps checking condition while it is running. So, the top of the behavior tree is replaced with:

When[EnemyNear]
Then
AttackSequence
Otherwise
When[StandingOnGrass]
Then
IdleSequence
Otherwise
Hum a tune


For more advanced "When" usage, one would also want to introduce "Wait" action that simply does nothing for a specified amount of time or indefinitely (until reset by parent behavior). Also, if you need only one branch of "When", other one can contain either "Success" or "Fail" actions, that respectiveley succeed and fail immediately.

• I think this approach is closer from what the original inventors of BT had in mind. It uses a more dynamic flow, which is why "running" state in BT is a very dangerous state, which should be used very rarely. We should design BTs always in mind the possibility of coming back at the root at any time. – v.oddou Feb 16 '15 at 2:00

While I'm late, but hope this can help. Mostly because I want to make sure I haven't personally missed something myself as I've been trying to figure this out as well. I've mostly borrowed this idea from Unreal, but without making it a Decorator, property on a base Node or strongly tied with the Blackboard, it's more generic.

This will introduce a new node type called Guard which is like a combination of a Decorator, and Composite and has a condition() -> Result signature alongside an update() -> Result

It has three modes to indicate how cancelation should occur when Guard returns Success or Failed, the actualy canceling depends on the caller. So for a Selector calling a Guard:

1. Cancel .self -> Only cancel the Guard (and its running child) if it is running and the condition was Failed
2. Cancel .lower -> Only cancel the lower priority nodes if they are running and the condition was Success or Running
3. Cancel .both -> Both .self and .lower depending on the conditions and running nodes. You want to cancel self if its running and would condition to false or cancel the running node if they're considered lower priority based on the Composite rule (Selector in our case) if the condition is Success. In other words, it's basically both concepts combined.

Like Decorator and unlike Composite it only takes a single child.

Although Guard only take a single child, you can nest as many Sequences, Selectors or other types Nodes as you want, including other Guards or Decorators.

 Selector1 Guard.both[Sequence[EnemyNear?]] Sequence1 MoveToEnemy Attack Selector2 Sequence2 StandingOnGrass? Idle HumATune 

In the scenario above, whenever Selector1 updates, it will always run condition checks on the guards associated with its children. In the case above, Sequence1 is Guarded and needs to be checked before Selector1 continues with the running tasks.

Whenever Selector2 or Sequence1 is running as soon as EnemyNear? returns success during a Guards condition() check then Selector1 will issue an interrupt/cancel to the running node and then continue as usual.

In other words, we can can react to either "idle" or "attack" branch based on a few conditions making the behaviour far more reactive than if we settled on Parallel

This also allows you to guard single Node that have higher priority against running Nodes in the same Composite

 Selector1 Guard.both[Sequence[EnemyNear?]] Sequence1 MoveToEnemy Attack Selector2 Guard.both[StandingOnGrass?] Idle HumATune 

If HumATune is a long running Node, Selector2 will always check that one first if it wasn't for the Guard. So if the npc got teleported onto a grass patch, next time Selector2 runs, it will check the Guard and cancel HumATunein order to run Idle

If it gets teleported out of the grass patch, it will cancel the running node (Idle) and move to HumATune

As you see here, the decision making relies on the caller of Guard and not the Guard itself. The rules of who is considered to be lower priority remains with the caller. In both examples, it's the Selector who defines what constitutes as a lower priority.

If you had a Composite called Random Selector, then you would get to define the rules within the implementation of that specific Composite.