Search Unity

  1. Unity 6 Preview is now available. To find out what's new, have a look at our Unity 6 Preview blog post.
    Dismiss Notice
  2. Unity is excited to announce that we will be collaborating with TheXPlace for a summer game jam from June 13 - June 19. Learn more.
    Dismiss Notice

Behavior Trees and Finite State Machine Discussion

Discussion in 'General Discussion' started by mikeNspired, Mar 26, 2017.

?

What do you use?

  1. Behavior Trees

    65 vote(s)
    21.0%
  2. FSMS

    107 vote(s)
    34.6%
  3. Both

    137 vote(s)
    44.3%
  1. mikeNspired

    mikeNspired

    Joined:
    Jan 13, 2016
    Posts:
    82
    I notice a lot of these AI tools on the asset store's like Node Canvas, and Behavior Designer have both of these built in(Behavior Trees and FSMs).

    I have seen some discussions on one vs the other, but what about using them together? Watching youtube and reading forum discussions its seems people seem to manage different states within a single large behavior tree.

    For people using these assets or similar assets, what are your opinions on using them individually versus using them together?

    What are the advantages of either or?

    Not having much experience with either, I seem to want to manage different states. Wandering, Attacking, Farming in an FSM, but each of those states run a separate behavior tree.
     
    Last edited: Mar 26, 2017
  2. Kiwasi

    Kiwasi

    Joined:
    Dec 5, 2013
    Posts:
    16,860
    I see it as a hierarchy. Start with a simple if-else block. If the problem is too complex for that, move to a FSM. If the problem is more complex then that, switch to a BT.

    It fact someone cleverer then me could probably demonstrate that each of the steps is a subset of the next.
     
  3. cdarklock

    cdarklock

    Joined:
    Jan 3, 2016
    Posts:
    455
    A behaviour tree is a finite state machine. Consider the process of "making a sandwich."

    In a behaviour tree, you perform the actions "get first slice of bread," "get filling," and "get second slice of bread."

    In an FSM, you have the states NO_BREAD, EMPTY_BREAD, and OPEN_FACE.

    NO_BREAD -> "get first slice of bread"
    EMPTY_BREAD -> "get filling"
    OPEN_FACE -> "get second slice of bread"

    They're the same damn thing. Use whichever one feels more natural to you.
     
  4. Billy4184

    Billy4184

    Joined:
    Jul 7, 2014
    Posts:
    6,056
    As BoredMormon said, just start with a string of if/else statements and move on to the next thing only if it's not good enough.

    Anyway, here's a brief look at the each of them as I understand it, highlighting what makes each of them unique from the others:

    Finite State Machine (FSM)

    This is the simplest type:
    • You have a collection of states that the AI can be in;
    • The AI is in one of these states at any given time;
    • The choice of whether to continue the behaviour or move onto something else is evaluated completely inside the behaviour that the AI is currently in, i.e. there is no hierarchy.
    Here's an example, you have one script each for Idle, Attack, and Run, and on each of these scripts is a coroutine which ticks the behaviour implementation. Inside each coroutine would be a complete evaluation of the game state and whether to move onto something else. You can see that:
    • You will be re-writing a lot of code, e.g. "If enemy disappears, go to idle" would be a part of the evaluation in both the Attack and the Run scripts. And this means..
    • Nodes are coupled tightly to all other nodes, i.e., modifying the Idle script would directly affect whether it was still relevant to be called from any of the other behaviour scripts, or it might mean that you would have to update contextual information across all of the other scripts so that you don't get some weird behaviour. For example if you modify the Idle script to have the character wipe their brow after running from the enemy, then if it was not called from the Run behaviour it would be illogical, and then you'd have to update the context for each time Idle was called, making 'breaking' the AI very easy.

    Hierarchical FSM (HFSM)

    The only difference between the HFSM and the FSM is that in the HFSM there is a hierarchy of choices, meaning that choices are evaluated at a high-level before getting into the details.

    For example, instead of the Attack, Run and Idle behaviours being completely self-contained, you would have a hierarchy that began with two states "EnemyFound" and "EnemyNotFound". Attack and Run would then be children of the EnemyFound state, while Idle would be a child of the EnemyNotFound state. Since you're starting from the top each tick, you can then remove the transition to Idle from the Attack and Run states, and move it up into the parent state (writing it only once). This enables better organisation of the transitions, removes a lot of re-written code etc.

    However the weakness is still that in each sub-group of a hierarchy, there may be nodes that are basically a re-write of nodes in a different sub-group, because the nodes in each hierarchy are still not modular, they are still coupled tightly to their hierarchy. This is where behaviour trees come in.


    Behaviour Tree (BT)

    To put it simply, a behaviour tree is like an HFSM, except that the nodes in the hierarchy are modular, uncoupled and self-contained, running on a context basis from any part of any sub-group of the hierarchy.

    In fact, any piece of the behaviour tree is modular, and can be called from anywhere else in the tree. This makes it possible to skip to a different area on the tree and do something else if the current evaluation finds that it is no longer relevant.

    The way this is achieved is by using a Blackboard which is a cache of information that can be accessed by any of the nodes in the tree, and which contains information that makes it possible to provide a context for each node that does not depend on where it was called from, keeping it completely modular.

    And instead of creating ten different versions of a behaviour depending on where it was called from, you could simply call various modular behaviours in sequence.


    So...

    You can see that really, these three types are not completely different, they're just improvements on eachother. In my view the main difference in terms of implementation is the overhead of building the infrastructure - BTs being more time-consuming to set up, but ultimately great for huge behaviour structures. But because BTs have a modular nature, then for smaller structures they aren't very good for keeping information together in front of a programmer's eyes, so they aren't worth it for simple AI.
     
  5. Kiwasi

    Kiwasi

    Joined:
    Dec 5, 2013
    Posts:
    16,860
    I have to disagree here. A finite state machine by definition can ony be in one state at a time. Where as a behaviour tree is commonly in multiple states at the same time.

    So you can create a BT to represent every possible FSM. But you can't make an FSM to represent every possible BT.

    Behaviour trees tend to be more natural for things like decision making, goal planning and similar. FSMs tend to be more natural for things that are natural state machines, like animation states.

    Conflating the two concepts is to ignore the power and unique characteristics of each.
     
  6. cdarklock

    cdarklock

    Joined:
    Jan 3, 2016
    Posts:
    455
    A combination of states is, by definition, a state. If you might be cold and hungry and wet, an FSM with three distinct states - enum { AM_COLD, AM_HUNGRY, AM_WET } - may implement this as where you can only be in one state through state = AM_COLD which is checked as if(state == AM_COLD), or as a bit vector where you can be in any combination of states through state |= 1 << AM_COLD which is checked as if(state & AM_COLD). This principle can be extended to arbitrary length.

    I don't think that's true. Starting at the root of the tree, any BT can have its root node replaced with an FSM that selects among its child subtrees. This process can obviously be applied recursively, which implies that replacing any BT with an FSM is always possible.

    Kind of like how any binary tree can be replaced by an array of pointers. The root is at pos[0]; for any node pos[k] the left child is at pos[2k + 1], the right at pos[2k + 2], and standard AVL algorithms will automatically optimise for size. The tradeoff is that when you're debugging the code, it's harder to visualise a tree from an array.

    Similarly, human beings do not tend to think naturally in FSM terms, so using a BT instead may help the human beings on the team understand what is going on. But the computer doesn't care.
     
    leni8ec and frosted like this.
  7. mikeNspired

    mikeNspired

    Joined:
    Jan 13, 2016
    Posts:
    82
    Isnt that one of the biggest differences between the two. FSM's run individual states unless running multiple FSM's, vs Behavior trees where we can run parallel branches.

    As I learn more about trees, it does seem pointless to use both at the same time, when i can run sub trees as states instead, and run parallel sub trees to achieve simultaneous states.
     
  8. Kiwasi

    Kiwasi

    Joined:
    Dec 5, 2013
    Posts:
    16,860
    What is being described in the post is a general state machine. A finite state machine is a special case which can only exist in one state at a time.
     
    LaneFox likes this.
  9. cdarklock

    cdarklock

    Joined:
    Jan 3, 2016
    Posts:
    455
    if you're running two different branches of a BT concurrently, this is mathematically indistinguishable from tracking two independent states of an FSM.

    You're thinking of a transition system, which can represent a theoretically infinite number of states. A state machine which represents the state as a bit vector, rather than an enumerated value, still has finite states.
     
  10. angrypenguin

    angrypenguin

    Joined:
    Dec 29, 2011
    Posts:
    15,633
    No, he's not. He's thinking of an FSM as per the generally accepted definition among computer scientists. By that definition an FSM has a distinct set of defined states, a set of defined transitions between states, and may exist in exactly one state at a given time.

    Fair enough if that's not the thing you want to work with, but then it's not an FSM - it's one of the many variations on the concept.
     
  11. Billy4184

    Billy4184

    Joined:
    Jul 7, 2014
    Posts:
    6,056
    The fact is that none of them are very different, and all these names are just a way to make a small improvement sound revolutionary. You can actually do whatever you want with it, and name it whatever you like! :)

    @cdarklock I don't really see your point. The whole point of these naming conventions is to distinguish minor differences in anatomy and operation. So the moment that you use it in a certain way, it actually becomes whatever acronym has been made for that mode of operation.
     
    phobos2077 and Kiwasi like this.
  12. Kiwasi

    Kiwasi

    Joined:
    Dec 5, 2013
    Posts:
    16,860
    Another key conceptual difference to consider is that a FSM requires explicit transitions to be described into and out of states. A BT has implied transitions based on the tree structure.

    This makes a FSM ideal for a system where transitions are important. Animation controllers are a classic example.

    On the other hand the lack of explicit transitions makes it much easier to add and remove new nodes from a BT. Which is why BTs are popular for large and complex behaviours like AI.

    FSMs become more complex to maintain as the number of states increases, as each new state adds a new set of possible transitions. BTs don't suffer this limitation.
     
  13. cdarklock

    cdarklock

    Joined:
    Jan 3, 2016
    Posts:
    455
    Mathematically, behaviour trees and finite state machines are identical. Anything which can be represented in one form can be represented in the other. Whichever one you like can be used for everything, because the decision is not dictated by the task. It's just an arbitrary choice, as far as the problem domain is concerned.

    Similarly, if you want to say an FSM is not the entire problem space that FSMs can mathematically be proven to cover, but only this specific part of the problem space you like to use FSMs for covering... that's just an arbitrary choice.

    And if you want to argue about what arbitrary choice should be made about a problem, I really don't see the point.
     
  14. LaneFox

    LaneFox

    Joined:
    Jun 29, 2011
    Posts:
    7,566
    Well practically and literally, they're fundamentally different. So i technically don't see what you're actually arguing about.
     
  15. cdarklock

    cdarklock

    Joined:
    Jan 3, 2016
    Posts:
    455
    No, they're not. Anything you can do with one, you can do with the other. That's just a fact. You may prefer using this one over here and that one over there, but it's certainly not because you have to.
     
  16. LaneFox

    LaneFox

    Joined:
    Jun 29, 2011
    Posts:
    7,566
    Finite State Machine cannot be in more than one state. Behavior Trees can simply add parallel tasks.

    If you're implying that in order to do the same thing with an FSM that you could simply create more states and conditionally pass through them to emulate the same results you could get with a BT then you're missing a the point which is that this would be a misuse of an FSM.

    I suppose you would argue that machine code == C# since you could get similar results with it. Even if similar results are possible, it doesn't mean its a good idea.
     
  17. cdarklock

    cdarklock

    Joined:
    Jan 3, 2016
    Posts:
    455
    I am saying that outright. The idea that you should not do this is an arbitrary distinction. It can be done. If you choose not to do it, that's fine, but it can still be done. That's a fact.

    Your CPU only understands machine code. You may be writing C#, but you are running machine code. Again: fact.

    Facts are funny. It doesn't matter whether you like them or believe them. They just are, and nothing you say or do can change that.
     
  18. LaneFox

    LaneFox

    Joined:
    Jun 29, 2011
    Posts:
    7,566
    So why do they matter when no one is going to recommend misusing the two objectively different systems? It seems irrational to vigorously defend technicalities when they don't really offer any practical value.
     
    trombonaut, gwelkind and maya-papaya like this.
  19. cdarklock

    cdarklock

    Joined:
    Jan 3, 2016
    Posts:
    455
    Why do facts matter?

    I... never mind.

    ("Unwatch thread")
     
  20. Billy4184

    Billy4184

    Joined:
    Jul 7, 2014
    Posts:
    6,056
    I don't think anybody is saying that you can't take an FSM and do whatever you like with it. The point is that if you use an FSM as a behaviour tree, it ceases to be an FSM. 'FSM' is not some label that resides in the fabric of spacetime, it simply refers to the way that your code calls and runs behaviours.

    In the end, it's all just a collection of behaviours, and the only difference is the way that you call them.
     
    maya-papaya, leni8ec and mbbmbbmm like this.
  21. frosted

    frosted

    Joined:
    Jan 17, 2014
    Posts:
    4,044
    In my gut I agree with @cdarklock, but I've recently started to come around to the other side.

    This is how I tend to think as well, if they are functionally identical then they're the same. But that's just not how people's brains work, for most cases, the name is often more important than the functionality itself.

    I've spent so much time trying to train my brain to parse things more like the machine does that I tend to lose track of that. Especially when it comes to higher level concepts and patterns - which tend to really border on social constructions rather than functional ones.

    It is worth noting though in the fsm vs bt thing that even though both approaches can represent the same functionality, how they'll actually look when fleshed out will be really different.
     
    Last edited: Mar 27, 2017
  22. asacafrw35tyth

    asacafrw35tyth

    Joined:
    Nov 17, 2015
    Posts:
    8
    Hmm... Is there a semantics board on unity forums? "Mathematically" you can do anything you can do in a FSM or BT by writing in assembly. Do you see the stupidity of arguing for mathematical equivalence in a forum that discusses tools and how to apply them practically?

    I know this was ancient but this just irked me hard haha.
     
  23. zenGarden

    zenGarden

    Joined:
    Mar 30, 2013
    Posts:
    4,538
    AI is not just BT or FSM, behind there is detection, lot of things like multi threaded and raycast, environment systems like EQS or navmesh and obstacle cover tags, or some very fast spatial octree generation for flying AI creatures, character crowd system and avoidance.
    In Last of Us 2 they pushed even more the AI with physics environment contextual movement using a huge library of pre made animation they mix in the fly, or AI communication and AI able to seek for player around the last seen position.

    Anyway, about BT or FSM, some AAA games uses an hybrid solution with BT and FSM mixed, or derived system. Other combine Goap.There is many ways, what matters is you achieve the AI you want to make.
    You can do a lot with BT already, if i had to choose, i would use BT indeed, because BT is based on decisions and has features like parallel, interruption, first fail or success, priority, random and many others it will be hard to emulate in FSM because FSM is based on states and it is more linear.
     
    Last edited: Jun 17, 2018
    maya-papaya and leni8ec like this.
  24. Arowx

    Arowx

    Joined:
    Nov 12, 2009
    Posts:
    8,194
    Isn't the new ECS system a lite FSM?
     
  25. Arowx

    Arowx

    Joined:
    Nov 12, 2009
    Posts:
    8,194
    What about Unity's machine learning isn't that a trainable Black Box FSM?
     
  26. ben-britton

    ben-britton

    Joined:
    Feb 7, 2015
    Posts:
    15
    The Mecanim system depends on Animation Controller which is sort of a Finite State Machine (FSM)-style system.
    Behavior Designer provides AI-like behaviors, using a Behavior Tree system that interfaces with Animation Controller.
    Thus using BT and HSFM here. Using Unity Navmesh for navmesh, but wish i could edit it inside Unity with ProBuilder.

    We would like to locate a library of public domain BT templates that portray common human behavior archetypes.
    We are using Behavior Tree models to portray personality, the goal in our use is artistic, to express human conditions.
    It is tricky, imho, to master various author's toolsets, interface them together, and fulfill an artistic goal, but trying,

    Low-level developers, please consider adding facial bones to your character rigs. Especially Mixamo. Plugins for Blender, Maya, Max, for humanoid "bipeds", would they please provide the option to include Unity-compatible facial rigs? I cannot tell you how astounded and grateful I am for Mixamo automatic rigging. Any chance it could have a facial rig added?

    For AI, we need to express emotions, so we need a standard for a library to be built as a reference for learning. AI developers should convene a symposium with top psychologists to codify a list of emotional states for a common standard that works with a standardized humanoid facial rig.

    I haven't found the machine learning capability helpful yet, because wrestling with custom animations, controllers, navigation and graphics is more pressing in practice. These tools need standardization and ease of use development. The new built-in machine learning may become useful soon.
     
  27. laurentlavigne

    laurentlavigne

    Joined:
    Aug 16, 2012
    Posts:
    6,421
    What? Where are FSM in behavior designers?!
     
  28. mikeNspired

    mikeNspired

    Joined:
    Jan 13, 2016
    Posts:
    82
    I think MikeNspired from 4 years ago may have been confused. I cant find anything about it in 2020 about opsive ever making them.
     
    aer0ace likes this.
  29. laurentlavigne

    laurentlavigne

    Joined:
    Aug 16, 2012
    Posts:
    6,421
    4 years ago you were knee deep in NodeCanvas that's why. What are you using these days?
     
    mikeNspired likes this.
  30. mikeNspired

    mikeNspired

    Joined:
    Jan 13, 2016
    Posts:
    82
    Haha, true.
    Now: I haven't done any AI stuff. I'm a VR developer in my day job now which sadly has zero AI.
    I did mess around with bolt state machines, mostly coded in C# and used the state machine for visuals for easy debugging, but Bolt caused more frustration than anything, but that was before Unity Acquired it. So sadly I have zero input on what's cool for AI.
     
  31. laurentlavigne

    laurentlavigne

    Joined:
    Aug 16, 2012
    Posts:
    6,421
    That's exactly what I need!
    Also FSM to handle decision cycles at the top but i'm into a bit of a pickle:
    • BD code is beautiful and simple and seems fast, but no FSM and super clunky UI (no bugs though). I don't think I can add FSM in BD because of its cycle detector.
    • Nodecanvas has FSM, action stacks are fantastic and that super expressive UI is so easy to debug in, but it's very glitchy, the code base is meh so I have no idea how well this performs and the deal breaker is that serialization breaks easily when you make your own nodes and when that happens you lose the ability of editing any trees in the project even if the custom node works or was removed.
    • Bolt 1 code looks like a big mess with guaranteed crap performance so I won't touch it.
     
    mikeNspired likes this.
  32. aer0ace

    aer0ace

    Joined:
    May 11, 2012
    Posts:
    1,513
    Thought I'd add a little insight with my experience with Behavior Designer (BD).
    As my turn-based tactical game has grown, I've had the need to run game code (including AI) outside of the Unity framework for autotests. Generally speaking, it's fantastic to have decoupled my game-related code outside of Unity, so I can technically run my game AI outside of Unity.

    I've built a lot of my AI agent logic in BD tasks, which require GameObjects, so that needed to change. After several refactorings, I was able to extract the AI logic out of the BD tasks. Since the BD runtime also requires Unity, I needed a substitute, and I discovered Fluent Behavior Trees, which is basically BTs authored in code.

    http://www.what-could-possibly-go-wrong.com/fluent-behavior-trees-for-ai-and-game-logic/
    https://github.com/ashleydavis/Fluent-Behaviour-Tree

    Ironically, the author has since moved on to using Behavior Designer...

    I integrated Fluid BT (which is based on Fluent Behavior Tree). It includes a runtime BT visualizer in the Unity Editor, but it isn't as full-featured as the Behavior Designer one.

    Depending on your AI needs, all this may or may not help. For the grand scheme of my game, I'm implementing utility-based decision making as the inputs into the BT; something that Behavior Designer already supports with its UtilitySelector, which is nice. Implementing a utility selector isn't difficult though; just pointing it out.

    I used FlowCanvas for a bit, for basic animation states (of unskinned object animations), but found it to be too heavy-handed for my needs. For skinned animations, I highly recommend Animancer.

    As far as BTs and FSMs being identical (I know it's an old thread), I'm not a subscriber of that, but I can kind of see it. It just doesn't help the game developer any to argue identical or not, because there are clear, inherent advantages to use one over the other as you are building it. So I guess you can argue that BTs are FSMs with their own built-in decision-making paradigm, but implementation-wise, I can't understand why anyone would say that they are "identical".