Behavior Trees for AI



  • Post your questions about the concept, or the article discussed in Lostcast 84.



  • How would you cancel an action?
    For example:

    1. An NPC attempts to open a door and fails.
    2. The NPC then attempts to pick the lock.
    3. While the NPC is attempting to pick the lock, the player unlocks the door for them.

    If I understand correctly, the NPC will keep attempting to pick the lock because that leaf node is “running”?


  • Tiger Hat

    @ken said:

    Post your questions about the concept, or the article discussed in Lostcast 84.

    What’s that quaking, thumping sound? Geoff’s coming! Run! Ken! What have you done!!! I can hear “RRAAAAAARH BEHAVIOUR TREES!!” in the distance!


  • LDG

    RWAAAAARRRRR! cough cough ahem

    Excellent question, Ken! I think this highlights how the concept of behavior trees is pretty abstract and much of the detail lives in how you implement your leaf or “action” nodes.

    First, I don’t think you’d ever want a leaf node that simply repeats an action until successful. A better way to handle that would be to put the “unlock a door” node underneath a “repeat until successful” type decorator. In general, it seems that leaf nodes should be as modular as possible and any kind of flow control (such as looping) should be done using composite and/or decorator nodes.

    Second, it’s really important to think about your success/failure conditions. In your example, the “unlock a door” node might return failure if the NPC tries to unlock an already unlocked door. However, it might make more sense to frame the success as the desired outcome rather than if your particular action was successful. Here’s how I might write the “unlock door” node:

    unlockDoor();
    var success = isDoorUnlocked();
    

    The unlockDoor function would attempt to use a key, or lockpick, or whatever made sense in the game to unlock the door. If that function returned failure since the door was already unlocked, the leaf node would still return success because at the end of the execution the door is unlocked. You could also modify your unlockDoor function to return success right away if the door isn’t locked.



  • @geoffb said:

    The unlockDoor function would attempt to use a key, or lockpick, or whatever made sense in the game to unlock the door. If that function returned failure since the door was already unlocked, the leaf node would still return success because at the end of the execution the door is unlocked. You could also modify your unlockDoor function to return success right away if the door isn’t locked.

    What if the “pick lock” action was based on time? If the “pick lock” action completes after 15 seconds, for example, then the ‘unlockDoor’ function would still be ‘running’ – Ohh, I think I get it now! In that case, you add a condition to the tick of the “pick lock” leaf node that checks if the door is already unlocked? :)



  • This is somewhat related to my other question: does the Behavior Tree get traversed on every tick of the game loop? I know the article said that doing that is inefficient, but how else would you handle “running” nodes? Because if a leaf node is “running”, doesn’t all of its ancestors get set to “running” as well?
    And if you store the “running” nodes in a buffer, won’t they all get “ticked” on the next tick of the game loop, which sort of defeats the purpose of the buffer?
    Unless… all leaf nodes contain a reference to the parent? To call the parent’s tick when it’s done?
    Then that way, you only need to store the “running” leaf nodes?


  • Patron

    (haven’t read the article, so, this might sound stupid)

    What is the advantage of using Behaviour Trees over State Machines?

    What is even the difference?


  • LDG

    @Josue said:

    (haven’t read the article, so, this might sound stupid)

    10/10 Tiger Hats!


  • LDG

    @Josue said:

    What is the advantage of using Behaviour Trees over State Machines?

    What is even the difference?

    I’m not an expert on either technique for AI, but from my understanding they both have their advantages. BTs are more structured, where as FSMs require more “transition” logic to go from one state to another. Since BTs are trees, the logic naturally flows up and down the branches with the use of simple composite nodes such as Sequence and Selector. I’ve read that BTs can more easily detect and adapt to events within the game world, but I’m not sure if that’s completely true. I do think that BTs guide the programmer down a more modular path, though.

    I don’t think BTs and FSMs are even mutually exclusive. I’ve read a tiny bit about HSMs (Hierarchical State Machines) and the concept of combining BTs and FSMs.


  • LDG

    @ken said:

    What if the “pick lock” action was based on time? If the “pick lock” action completes after 15 seconds, for example, then the ‘unlockDoor’ function would still be ‘running’ – Ohh, I think I get it now! In that case, you add a condition to the tick of the “pick lock” leaf node that checks if the door is already unlocked? :)

    Yeah, that’s how I imagine it would work. Maybe something like this:

    var pickLockNode = {
      init: function () {
        this.status = "running";
        this.elapsed = 0;
      },
      update: function (dt) {
        if (!door.locked) {
          this.status = "success";
        } else {
          this.elapsed += dt;
          if (this.elapsed >= TIME_TO_PICK_LOCK) {
            pickDoorLock(door);
            this.status = door.locked ? "failure" : "success";
          }
        }
      }
    };
    

  • LDG

    @ken said:

    This is somewhat related to my other question: does the Behavior Tree get traversed on every tick of the game loop? I know the article said that doing that is inefficient, but how else would you handle “running” nodes? Because if a leaf node is “running”, doesn’t all of its ancestors get set to “running” as well?
    And if you store the “running” nodes in a buffer, won’t they all get “ticked” on the next tick of the game loop, which sort of defeats the purpose of the buffer?
    Unless… all leaf nodes contain a reference to the parent? To call the parent’s tick when it’s done?
    Then that way, you only need to store the “running” leaf nodes?

    I’m not 100% clear on how this works yet, either. It does seem inefficient to traverse the entire tree each tick, but that’s an optimization step I’m not ready to handle just yet. :D

    My gut says that the best way would be to keep a stack of running nodes and only execute the “top” node until it’s finished. Once that node has finished, remove it from the stack and the new top node will be its parent. That parent would then evaluate the status (success or failure) of its current child and act accordingly.



  • Somewhat related, the really fun Machine.js library:

    http://machinejs.maryrosecook.com



  • @geoffb said:

    My gut says that the best way would be to keep a stack of running nodes and only execute the “top” node until it’s finished. Once that node has finished, remove it from the stack and the new top node will be its parent. That parent would then evaluate the status (success or failure) of its current child and act accordingly.

    Unfortunately, that would prevent two nodes from being run concurrently, right? Though I can’t think of any instances right now that could take advantage of that feature anyway, so I guess it’s a fair trade.
    Hmm… So each BT maintains its own stack of nodes, because if there was only one big stack, the other NPCs would stall…
    Alright, thank you, @geoffb! I think I now understand it enough to attept to write my own implementation haha :D



  • Here’s an exciting thought: Behavior Trees running in background threads, using Web Workers. :D


Log in to reply