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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
