One time when I was working on one of my first 2D platformer I had to implement an enemy - shooting alien. At beginning his behaviour was very simple - when player enters in his vision range he starts shooting. So in I use bunch of if statements in Update() method. Later when AI behaviour became more complex I understood that I need to discover better way to solve this problem. And I found a solution - finite-state machines.

What is finite-state machine?

Finite-state machine (FSM) is a mathematical model of computation. Every FSM meets requirements:

  • FSM has a fixed set of states that it can be in, for example: walking, jumping, running, idle,
  • it can only be in one state at time - character can't simultaneously walking and jumping,
  • inputs or events are sent to the machine - when player press keyboard button for example,
  • each state has a set of transitions which describes conditions allow to switch to another state. For example pressing Spacebar switch character from idle state to jump state.

Finite-state machine

Basic finite-state machine

There is no hierarchy in basic finite-state machine. It means that the choice of whether to continue or move into another state is evaluated completely inside the state that AI is currently in.

Finite-state machine in computer games

The behaviour of state machines can be observed in many modern devices that perform a sequence of actions depending on sequence of events with which they are presented. Examples are vending machines, elevators, traffic lights and combinations locks. Game developers noticed that finite-state machines can be used to AI programming. FSM allows to get great results without complex code. They are relatively easy to understand, implement and debug.

To implement FSM for enemy AI we should enter to his brain and recognize all actions that enemy can perform. For example, the ghost in Pac Man can chase the player, evade him or roam freely. Ghosts in each of this states behave diferrently and their transitions are determined by the player's actions - when player eats a pill, state will change from chasing to evading.

Finite-state machine example

Ok, I will show you an example of implementation finite-state machine which control an enemy in shooter game. First let's create IState interface:

public interface IState{

    void UpdateActions();
    void OnTriggerEnter(Collider enemy);

    void ToPatrolState();
    void ToAttackState();
    void ToAlertState();
    void ToChaseState();
}

You can notice that we should create a four states:

  • Patrol state
  • Attack state
  • Alert state
  • and Chase state.

Each of this states will implement IState interface. So let's create 4 new classes, one for each state. Every state should look like this:

public class ChaseState : IState  
{
    EnemyFSM enemy;

    public ChaseState(EnemyFSM enemy)
    {
        this.enemy = enemy;
    }

    public void OnTriggerEnter(Collider enemy)
    {
    }

    public void ToAlertState()
    {
    }

    public void ToAttackState()
    {
    }

    public void ToChaseState()
    {
    }

    public void ToPatrolState()
    {
    }

    public void UpdateActions()
    {
    }
}

You can notice that every state have a transition to all states. But we should simply ignore the impossible transitions for example, from chase state to chase state. Here is the diagram of all possible transitions:
FSM transitions

Next step is implement EnemyFSM to control states flow.

public class EnemyFSM: MonoBehaviour {

    public AlertState alertState;
    public AttackState attackState;
    public ChaseState chaseState;
    public PatrolState patrolState;

    public IState currentState;

    private void Awake()
    {
        alertState = new AlertState(this);
        attackState = new AttackState(this);
        chaseState = new ChaseState(this);
        patrolState = new PatrolState(this);
    }

    private void Start()
    {
        currentState = patrolState;
    }

    private void Update()
    {
        currentState.UpdateActions();
    }

    private void OnTriggerEnter(Collider other)
    {
        currentState.OnTriggerEnter(other);
    }
}

Each state implements own UpdateActions() method, so we always execute update of current state. As your homework please try to finish this finite-state machine ;). You have to implement code which change state according to above diagram's transitions. You should place this code in UpdateActions() function of each state.

Behaviour trees

Behaviour tree is a kind of finite-state machine. The main feature of behaviour tree is a tree hierarchical structure - ordered nodes controls the flow of decision making of AI.
BasicTree

Basic behaviour tree

In above basic example root node trigers the Conditional, which selects between Behaviour A or B. Often BT are more complex but they nicely organised structure allows easier visual debbuging. Large trees can contain smaller sub trees which can continue executing without invoking whole tree, until flow exits from sub to main tree. In Unity we can create a state machines using built-in Animator system. If you need to build more complex AAA dynamic behaviour trees we can recommend one of this handy plugins:

Conclusion

As I wanted to show you, finite-state machines are very useful in games. Especially in implementing AI logic. They can be easily represented using a diagrams, which simplifies processes of implementation, optimizing and debuging.

The implementation of basic FSM using states and methods is quite simple. Despite that, plain FSMs have limitations and for more complex AI you might need more advanced solution like Behaviour trees.

I hope it’s useful for you. If you have any comments or questions, please write them here!

Mateusz Olszewski - Lead Programmer



Show Comments