Behavior Trees and Finite State Machines (FSMs)

Ever wondered how AIs in games work? Well, the structure is pretty simple. The AI will have to make a decision on what to do when they meet an enemy, an ally, a normal NPC or the player. In order to do this, they will have to make a structure which allows the AI to make decisions, both complex and simple. Developers and/or programmers can use either a Finite State Machine, or a Behavior Tree. In games, we use Behavior Trees really often, as it allows the developer to change an add new behaviors at any time, and any where within the tree. Its dynamic. The tree can be used for a really complex AI or a really simple AI.

Behavior Trees

Behavior Trees allows the AI to make complex decisions and actions when encountering the player or any other objects within the game. The decision structure is much like a tree, as shown above. The tree is made up of the behaviors (Actions) and the composite nodes, the selector and the sequencer nodes. Before I explain what each composite nodes do, I need to cover how the tree works. 

How the tree works:

Within the tree, there is a class called Node, or TreeNode, whichever one suits you for that particular behavior tree. Inside this class, there is an enumerator variable, which keeps track of the behavior tree's results (Success, Failed, Running, Ready). 

Success: It means that the AI has completed executing this behavior

Failed: It means that the AI has encountered something which prevented it from executing this behavior

Running: It means that the AI is currently running this behavior

Ready: It means that this behavior is ready to be executed.

Composite Nodes:

Selector: The selector node will check all its children in priority. If one of the children returns a result as success, the selector node will return success, and will run that behavior. 

Sequencer: The sequencer node will check all its children in priority. If ALL of the children returns success, the sequencer node will return success.

How the tree works, related to the image above:

So with the explanations above, I will explain how the image works. The head, or root, of the tree is a selector node. If we were to follow the numbers next to each node within the tree, it shows the flow of how this tree works. 

0 - It will check if any of the children nodes returns success

1 - It will check if any of the children nodes returns success

2 - Plays/checks behavior

3 - It will check if ALL of the children nodes returns success

4 - Plays/checks behavior

5 - Plays/checks behavior

6 - Plays/checks behavior

7 - Plays/checks behavior

8 - Plays/checks behavior

Lets put it into perspective. Lets say we had our own behavior tree. This tree would have:

1 - Selector

1.i - Sequencer

1.ii - Patrol

1.i.i - Chase

1.i.ii - Attack 

So the children of the selector will be the sequencer and the Patrol behavior. The children of the sequencer will be the Chase and Attack behavior. 

The tree will check if the sequencer has returned a result type success. It will check the children, both the Chase and Attack behaviors. If both of them return failed, then the selector node will check the Patrol behavior. If this behavior returns success, the patrol behavior will be executed. The patrol behavior is the default behavior of the AI.