Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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:

enter image description here

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:

enter image description here

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?

share|improve this question

5 Answers 5

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

share|improve this answer
    
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:

enter image description here

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.

share|improve this answer
1  
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
1  
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

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:

enter image description here

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:

enter image description here

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.

share|improve this answer

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.

share|improve this answer
    
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 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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