1. (Hierarchical) Finite State Machines & Behavior Trees - MauriceJohannssen/BehaviorTrees GitHub Wiki

Introduction

The first part of this project was to research older and newer techniques used for AI in games. While researching, two became apparent really quickly: Finite State Machines and Behaviour Trees. On this page, I want to briefly talk about both techniques and their similarities and differences.

Finite State Machines

In a short way of explaining, Finite State Machines or FSM's represent a specific behavior by using a set of predefined states. These states can have one or more transitions to other states, depending on whether it is a deterministic or a non-deterministic state machine. Generally, states in deterministic state machines can transition to one other state, whereas states in non-deterministic state machines can have multiple transitions to other states. Each state has different preconditions to decide on when a transition is valid, and which state to use next. Now, one problem with an FSM is its scalability. When using a lot of states, FSM's tend to become really complicated and labor-intensive as they grow. A lot of states with a lot of transitions create a difficult-to-understand system. This is partially being solved by using hierarchical FSM's. The idea here is to group states together so a transition between different collections of states is possible, but essentially this shifts the previously mentioned scalability issues one level up.

Behaviour Trees

Behavior trees are structurally different. A tree consists of different individual nodes that make up the tree. Each behavior tree has a root, where the evaluation of the tree starts. Essentially, there are three different types of nodes: root, composite nodes, and leaf nodes. For example, here is the tree I used for the agents in this project:

Root node

The root node is responsible for the evaluation order of the tree. There's always only one root node, from which the tree is being evaluated.

Composite nodes

Composite nodes are the nodes use to create the logical structure of the tree. There are three different types of composite nodes: Selector, Sequence, and Decorator. A selector node evaluates its subtasks from left to right and returns as soon as one subtask returns a success, not evaluating the following subtasks. Sequence nodes also evaluate from left to right, with the condition being that the previous subtask was successful, meaning that having three subtasks, the third is only evaluated when the first two were successful. Decorator nodes manipulate already existing logic e.g. invert a subtask.

Leaf nodes

Leaf nodes correspond to the actual tasks, meaning that the leaf nodes are responsible for the actual behavior of the AI, like checking health, look for players, etc.

The advantages behavior trees have is that they can be extended easily and the structure and evaluation are easier to understand. Furthermore, once a node was created, it can be reused at any point in the tree, if it was written in a general way that is. To make these trees more efficient, the evaluation of the tree called a tick, can be set to any rate e.g. any 10 frames or each second. Though what emerges more and more are event-driven behavior trees, meaning the trees will re-evaluated depending on the environment.