Preempting Behavior Trees

Question

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?

Answer 1

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.

Answer 2

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.

Also: http://www.valvesoftware.com/publications/2009/ai_systems_of_l4d_mike_booth.pdf

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.