AI

Finite State Machine

• A finite-state machine is a model used to represent and control execution flow.
• Only a single state can be active at the same time, so the machine must transition from one state to another in order to perform different actions.
• The "brain" of an enemy, for instance, can be implemented using a FSM
• Every state represents an action, such as attack or evade

An FSM can be represented by a graph, where the nodes are the states and the edges are the transitions. Each edge has a label informing when the transition should happen, like the player is near label in the figure above, which indicates that the machine will transition from wander to attack if the player is near.

Implementing a FSM

An FSM can be implemented and encapsulated in a single class, named FSM for instance. The idea is to implement every state as a function or method, using a property called activeState in the class to determine which state is active:

public class FSM { private var activeState :Function; // points to the currently active state function

public function FSM() {
}

public function setState(state :Function) :void {
    activeState = state;
}

public function update() :void {
    if (activeState != null) {
        activeState();
    }
}

}

Behavior tree

• A behaviour tree is a tree of hierarchical nodes that control the flow of decision making of an AI entity.
• At the extents of the tree, the leaves, are the actual commands that control the AI entity, and forming the branches are various types of utility nodes that control the AI’s walk down the trees to reach the sequences of commands best suited to the situation.

the system will traverse down from the root of the tree every single frame, testing each node down the tree to see which is active, rechecking any nodes along the way, until it reaches the currently active node to tick it again.

Each node can return one of three statuses Success Failure Running

The first two, as their names suggest, inform their parent that their operation was a success or a failure. The third means that success or failure is not yet determined, and the node is still running. The node will be ticked again next time the tree is ticked, at which point it will again have the opportunity to succeed, fail or continue running.

These statuses then propagate and define the flow of the tree, to provide a sequence of events and different execution paths down the tree to make sure the AI behaves as desired.

With this shared functionality in common, there are three main archetypes of behaviour tree node:

Composite Decorator Leaf

Composite

A composite node is a node that can have one or more children. They will process one or more of these children in either a first to last sequence or random order depending on the particular composite node in question, and at some stage will consider their processing complete and pass either success or failure to their parent, often determined by the success or failure of the child nodes. During the time they are processing children, they will continue to return Running to the parent.

The most commonly used composite node is the Sequence, which simply runs each child in sequence, returning failure at the point any of the children fail, and returning success if every child returned a successful status.

Decorator

A decorator node, like a composite node, can have a child node. Unlike a composite node, they can specifically only have a single child. Their function is either to transform the result they receive from their child node's status, to terminate the child, or repeat processing of the child, depending on the type of decorator node.

A commonly used example of a decorator is the Inverter, which will simply invert the result of the child. A child fails and it will return success to its parent, or a child succeeds and it will return failure to the parent.

Leaf

These are the lowest level node type, and are incapable of having any children.

Pros and Cons

Behavior trees have a few advantages over finite state machines: they provide lots of flexibility, are very powerful, and they are really easy to make changes to. But they definitely do not replace the functionality of finite state machines. This is why when you combine a behavior tree with a finite state machine, you can do some really cool things.