Hierarchical Finite State Machine Behaviour Tree Hybrid
In todays industry we use Behaviour Trees to perform all kinds of tasks for AI in games. It can range from walking to deciding when to shoot or to eat a banana. This is great until the point when you have a colossus Behaviour Tree which tends to contain a lot of edge cases and conditions.
With the ever expanding use of Behaviour trees we are making things harder for AI programmers and Designers to build trees that aren't filled with tons of duct tape and glue. That is where the Hierarchical Finite State Machine Behaviour Tree Hybrid comes in. As you can see its name isn't the shortest easiest name so during the specialization I am going to refer it as The Chimera System.
Example of a big Behaviour Tree
Blue is a Condition or Decorator
Purple is a Task/Action
Grey is a Composite
This is a behaviour tree I found online to show how big a behaviour tree can become. With a node graph the making of a behaviour can be easy but if you link nodes in Visual Studio then it will difficult and there will be a lot of clutter.
Motivation
AI has always had a special place in my heart. It is both fun to see NPCs going balistic because you "accidently" slap a chicken and when they are doing something so outside the box it just makes you go "Wow that was cool" like the Goal Orientated AI from F.E.A.R. When I started to study game programming at The Game Assembly I couldn't wait to start programming my own AI using Finite State Machines and Behaviour Trees and the rest is history.
​
From my experience I have noticed that only using Behaviour Trees can be very limiting to what could be accomplished if we mix systems. For example Finite State Machines are great at transitioning between states but difficult to setup and it's not as easy to make fast behaviours like Behaviour Trees. So what I want to try is to mix the two and eliminate as many cons as possible whilst keeping the efficiency of the two systems. Hence why I call the Hierarchical Finite State Machine Behaviour Tree Hybrid the name Chimera System.
Beginning
The project I used is an old assignment where different AI types needed to battle each other, basiclly building a minigame from ground up. There I had already made a Finite State Machine and we got a handed down Behaviour Tree. But I had to redo some things like write a new Finite State Machine to contain a Behaviour Tree and rewrite some thing in the Behaviour Tree to learn more about how they function and how to make my own.
Finite State Machine
The Finite State Machine is what keeps track of what state should be updating and also checks if the conditions for a state trasition is met.
The way I wanted to make the Finite State Machine at first was to let it have Root Node, which is the start node for the Behaviour Tree, so that the State Machine was updating the Behaviour Tree. I decided to change this later so that the states contained a Behaviour Tree.
Now that the states contain a behaviour tree it is easier to build a specific behaviour. States also have the conditions that needs to be met in order for it to be able to transition to a new state. So if it was in patrol state it will move around to different positions in the world until it sees a different AI which will then trigger the conditions to trasition from Patrol to Alert or Shoot. This is when the State Machine does the function DoStateTransition which will then make the AI have the Alert/Shoot State Active.
Behaviour Tree
The Behaviour Tree is built with nodes. The different types are
Composite, Decorator and Action/Task Node. All of them will inherit from the Node Class.
Composites are nodes that can select or play things in sequences. They are often called Selectors and Sequencers. As the name might have given away, Selectors will try to select a node that will return Success while Sequencers will try to run all its children in a sequence and will return Success only if they all return Success. These are often used as Root Nodes, The start of the Behaviour Tree
Decorators are nodes that are used for special cases such as if you want a node to always return Success even though it might return Faliure. There is a lot of uses for Decorators such as conditional checks to be able to run a node. I like to call these specific nodes for Conditional Nodes.
Actions/ Tasks are nodes that contain the logic of what the AI should do if it reaches it. For example move, shoot or cry in a corner. These are often the at the end of a tree and are the ones to return a Success or Faliure value up to the Composites and Dectorators.
Every node returns a Status which will tell the AI if an action is a Success otherwise it will return Failure. The Running status is to tell the Behaviour Tree that it is currently running a node and will return a new status when finished with the action it is in.
In every behaviour Tree there is something called a blackboard and this is something that stores different variables that can be used all over the Behaviour Tree. It is a good thing to use when you want to store something that you want to use for later, such as if the AI saw the player or need to know how far something is.
The Chimera AI Soldier
Now that you know a little about how the two systems work let's get to the designing and how I implemented the AI. I have given it the name Chimera AI Soldier because all the other AIs are called something that has to do with their AI system. We have Behaviour AI Soldier, State AI Soldier and Nincompoop AI Soldier.
I originally made three states the Chimera can transition into. They are called Dormant, Combat and Death State. Dormant is the patrol/ idle part of the AI. Combat is the part in which it is alerted/ Shooting at enemies it sees. Death is, well it is death. I later on made another state called Powered Up State but we'll go deeper into that and the other states soon.
In the image we see how the State Machine updates states. We have a pointer that points to the state we are currently in and updates it. The transitioning will happen only when the conditions are met within the state which we will also take a closer look at soon. When a state is able to transition the DoStateTransition will solve it by giving use the new state after we have exited the previous one.
In all of the states we have an Update that will update the Behaviour Tree that is made within that state. Because of this we can make really precies behaviours in those States. I also for safety terminate the tree with a Success to ensure it doesn't start form where I left it.
Here is one of the transitions. This shows us the conditions that needs to be met in order for Dormant State to Transition to Combat State. All states has these but I think this is enough for us to understand how it works.
Now that you know the basic of how the two systems work it's time for me to show you how the behaviours work in the different states! I didn't make a tool to serve as a visual aid on how the different behaiour trees looks like but thanks to Unreal Engines Behaviour Tree Editor I could easily make the different trees.
Old Behaviour Tree
Here is the old Behaviour Tree that we had in the project. It has a lot of different branches to look if certain conditions are met. This in Unreal might be easy to write but writing it in C++ makes it a lot harder to see and to understand. Hence the reason I chose to show of the behaviours in Unreal. To show that having behaviours in states is easier to manage I will use the exakt same Behaviour Tree the Behaviour AI has in the Chimeras states but chopped up.
Dormant State
This state is very basic. It only contains movement actions with some conditions on which things it should move to depending on what is happening in the game.
Old Combat State
This was the first iteration of the Combat State. It has a parallel node that can run two nodes at the same time. I want to be able to shoot and move at the same time. In this case I made it so that both children has to return either Succes or Faliure to become either of the conditions.
The part of the old Combat State I changed was the Movement Type node. Instead of having this extra check I wanted to really show how small Behaviour Trees can be so I made a new state called Powered Up.
The new Combat State has no check on what Movement Type it has. This makes it easier for us to see how it behaves when it doesn't have a Speed boost.
New Combat State
Powered Up State
The Powered Up State looks almost exactly like the Combat State but with some tweaks. The check for if it has taken damage is different and it can move to a waypoint if there isn't any enemies. This was a lot easier to work with than to have more composites.
Now that you have seen how the different trees look like I would like to ask you to think about which of these you would prefer. Would you like to have behaviours that are smaller but more of or have one that is massive.
The AI Showdown
Blue Circle is a Speed Boost
Green Circles are Healing Wells
White Circles are pillars
This video is to show that the Chimera System works in the same environment as the other AIs I have made and well if you have seen the video then you see that it doesn't only work fine but work really well! The force is strong in this AI.
Conclusion
The project has been a lot of fun for me. I got to program and design a new AI that I made out of mixing two different systems and I have learned a lot from this. Mixing the Finite State Machine with the Behaviour Trees will be a little bit of extra work if you don't already have one of them already but the payoff is really worth it because it saves time and makes it easier to debug.
The project I used isn't the biggest but think about how useful this system could have been if I were to implement it in a bigger project like a game project for a AAA studio. Not only would we get quick and easy ways to design behaviours, we would have an easier time looking at the different states and the transitions and understand the fundemental gist of how the AI works. If we want a closer look at a state we could just take a look at its Behaviour Tree. This breakdown makes debugging a lot easier!
Some States don't even need a Behaviour Tree such as an Idle State. This state would just wait where it is and sometimes maybe play different idle animations which also is easier to use in states rather than Behaviour Trees.
You don't even need to implement it the way I did it. Someone suggested that I should make the states into nodes that have behaviours in them, like a Behaviour Tree in a Behaviour Tree. There is a lot of room on how one should implement the system so if you are interested in this I suggest giving it a go!