Combining State Machines and Behavior Trees

[Dibes 0]

Hey ya'll this will likely be a long post so hang in there! I have been playing around with behavior trees and state machines over the past few days and have formed some ideas around how to combine them to have really nice clear and clean logical structure. I assume you have read the primer Nullable has written and have a cursory understanding of behaviorTrees. This post is mainly to lay out my ideas, and is not a definitive "this is how you should do things" by any means. It is simply another approach and tool in your toolbox!

Let's Talk Behavior Trees

Behavior trees are super cool. They allow you to have resilient and reactive logic that is composable and inherently good at dealing with failed conditions. Nullable has a fantastic primer on it (READ THE LINKED ARTICLE) here. I highly recommend you go check it out. 

A simple example Behavior Tree for Fighting & Banking for example

val tree = behaviorTree {
  repeatUntil(BehaviorTreeStatus.KILL) {
    // High-level selector to decide between banking or fighting
    selector {
      // Banking Sequence
      sequence {
        condition { Inventory.isFull() || !Inventory.hasFood() }
        perform { bankNode() }
      }

      // Fighting Sequence
      sequence {
        // Eating Subtree
        selector {
          condition { isHealthAboveThreshold() }
          perform { eatFood() }
        }

        // Looting Subtree
        selector {
          condition { isNoLootAvailable() }
          perform { lootItems() }
        }

        // Fighting Action
        perform { performFighting() }
      }
    }
  }
}

tree.tick() // Executes the tree

This nice and simple structure will reliably go between Banking and Fighting with eating and looting. Now what do we need to do if we want to add a 3rd thing we want our bot to handle. Let's say for example that we want to generate our own food. To do that we need to fish and then cook what we fished. 

selector {
  // Fishing Sequence: Fish until you have X raw fish
  sequence {
    condition { !isFishingComplete } // Only fish if fishing is not complete, otherwise we will keep going into this sequence after cooking our fish
    condition { getRawFishCount() < targetRawFishCount } // Check if raw fish count is less than the target
    perform { performFishing() } // Mark that fishing is complete for now
  }

  // Cooking Sequence: Cook until no raw fish is left
  sequence {
    condition { isFishingComplete } // Only cook if fishing is complete
    condition { hasRawFishInInventory() } // Ensure there is raw fish to cook
    perform { performCooking() }
    perform { updateFishingCompleteFlag() } // Update the flag when done cooking
  }

  // Fighting Sequence: Do our existing tree
  fightAndBankNode()
  
}

The problem with this approach is there is a bunch of tedium in storing and tracking state around "have we fished". That honestly kind of sucks, what are a couple of ways to solve this?

Way #1 Repeat Until

A simple way to solve this is to make sure our fishing and cooking sequences repeat until they meet a threshold. The downside is that we lose a little bit of our reactivity in the behaviorTree since we are locked in until we meet that condition without specifically breaking out of it.

So our sequences now look like

sequence {
    repeatUntil { getRawFishCount() >= targetRawFishCount } {
      condition { getRawFishCount() < targetRawFishCount } // Check if raw fish count is less than the target
      perform { performFishing() } // Mark that fishing is complete for now
    }
  }

and

sequence {
    repeatUntil { getRawFishCount() <= 0 } {
      condition { hasRawFishInInventory() } // Ensure there is raw fish to cook
      perform { performCooking() }
      perform { updateFishingCompleteFlag() } // Update the flag when done cooking
    }
  }

Way #2 What about State Machines?

State Machine Primer

In case you need a refresher or haven't yet learned about what state machines are, here is a brief primer on them i highly recommend you read!

The code

Another way we could go about dealing with this is by using a State Machine to define our top level state and have each state's action be a behaviorTree to robustly execute that state.

val fishingState = createState {
  tree {
      behaviorTree {
          performFishing()
      }
  }
}

val cookingState = createState {
  tree {
      behaviorTree {
          performCooking()
      }
  }
}

val fightingState = createState {
  tree {
      behaviorTree {
          performFighting()
      }
  }
}

createStateMachine {
  initialState = fishingState

  fishingState on { getRawFishCount() >= targetRawFishCount } to cookingState
  cookingState on { !hasRawFishInInventory() } to fightingState
  fightingState on { Inventory.getFoodCount() <= minimumFoodThreshold } to fishingState
}

The big benefit here is that we can completely move all the "what should we do" code from the "how should we do it". It should allow us to add more high level behaviors without mucking up our behaviorTrees with a bunch of transition logic, thus keeping them smaller, focused, and more efficient.

If this interests you, I wrote the framework for state machines that includes transitions, priorities, and global transitions here. I also re-implemented most of the behaviorTree framework so I could visualize it! All the code is in the framework module in that repository

Viz Example

 

Conclusion

if you made it this far, thank you for reading! I hope I generated some thoughts while reading. This is the result of only around a week of tinkering around, so there is definitely a lot for me to learn in this area. I would love to hear any of ya'lls thoughts on shortcomings of my approach or other ways you would tackle this! 

Edited September 29 by Dibes

[SickBrains 4]

Nice info😀