Finite State Machines for AI in Actionscript

15th January 2007

A few months ago I said I’d post about the AI in Stick Sports Soccer. Here, at last, is the first such post looking at the code used to implement the Finite State Machines in this and other games I’ve developed.

(For an introduction to Finite State Machines, try Wikipedia and AI-Depot.)

Often finite state machines are implemented (in real projects and tutorials) as a mass of code in a single class, usually a giant switch statement hundreds or (in one instance I’ve seen) thousands of lines long. A simple switch statement is great for a simple agent with two or three states, but the more complex the agent gets, both in the number and complexity of the states, the more complex the code gets. Using a switch statement also offers very little opportunity to reuse code across different agents and different projects (other than by cutting and pasting).

The solution I’ve used in a number of projects is to implement each state as a separate class. The class will contain all the code necessary for entering, updating and exiting that state and nothing else. This way, the code for each state is separate and the agent code isn’t cluttered by it.

In this solution, each state implements the State interface, which looks like this.

interface State
{
    public function Enter():Void; // called on entering the state
    public function Exit():Void; // called on leaving the state
    public function Update( time:Number ):Void;
                   // called every frame while in the state
}

Each state implements Entry and Exit methods for one-off actions that the agent takes when entering and leaving the state, in addition to the Update method which is run repeatedly while in the state. The time paramater in the Update method is the duration of the frame we’re executing.

A couple of states for a patrolling guard in a shoot ‘em up might look like this.

// patrolling the area
class Patrol implements State
{
    private var fsm:StateMachine;
    private var guard:Guard;
    
    public function Patrol( g:Guard )
    {
        guard = g;
        fsm = guard.GetStateMachine();
    }
    
    public function Enter():Void
    {
        // check the gun is loaded
        guard.Reload();
    }
    
    public function Exit():Void
    {
    }
    
    public function Update( time:Number ):Void
    {
        guard.FollowPatrolPath( time );
        var threat:Soldier = guard.Threatened();
                               // returns null if no threat
        if( threat )
        {
            fsm.ChangeState( new Attack( guard, threat ) );
        }
    }
}

// attacking an enemy
class Attack implements State
{
    private var fsm:StateMachine;
    private var guard:Guard;
    private var enemy:Soldier;
    
    public function Attack( g:Guard, e:Soldier )
    {
        guard = g;
        fsm = guard.GetStateMachine();
        enemy = e;
    }
    
    public function Enter():Void
    {
    }
    
    public function Exit():Void
    {
    }
    
    public function Update( time:Number ):Void
    {
        guard.ShootAt( enemy );
        if( enemy.IsDead() )
        {
            fsm.ChangeState( new Patrol( guard ) );
        }
    }
}

I then create the Finite State Machine as a class that is responsible for managing the current state. A simple state machine looks like this.

class StateMachine
{
    private var currentState:State;
    
    public function StateMachine()
    {
        currentState = null;
    }
    
    // Update the FSM. Parameter is the frametime for this frame.
    public function Update( time:Number ):Void
    {
        if( currentState )
        {
            currentState.Update( time );
        }
    }
    
    // Change to another state
    public function ChangeState( s:State ):Void
    {
        currentState.Exit();
        currentState = s;
        currentState.Enter();
    }
}

The agent then uses an instance of the StateMachine class to handle its AI.

class Agent
{
    private var fsm:StateMachine;
    
    public function Agent()
    {
        fsm = new StateMachine();
    }
    
    public function Update( time:Number ):Void
    {
        fsm.Update( time );
    }
    
    public function GetStateMachine():StateMachine
    {
        return fsm;
    }
}

The agent class is a lot more manageable without the state machine implementation and all the states inside it, and I have a single StateMachine class that can be used by all agents. I can even share states across agents too.

Finally, I add a number of features to the StateMachine class to allow chaining of states and returning to previous states.

class StateMachine
{
    private var currentState:State;
    private var previousState:State;
    private var nextState:State;
    
    public function StateMachine()
    {
        currentState = null;
        previousState = null;
        nextState = null;
    }
    
    // prepare a state for use after the current state
    public function SetNextState( s:State ):Void
    {
        nextState = s;
    }
    
    // Update the FSM. Parameter is the frametime for this frame.
    public function Update( time:Number ):Void
    {
        if( currentState )
        {
            currentState.Update( time );
        }
    }
    
    // Change to another state
    public function ChangeState( s:State ):Void
    {
        currentState.Exit();
        previousState = currentState;
        currentState = s;
        currentState.Enter();
    }
    
    // Change back to the previous state
    public function GoToPreviousState():Void
    {
        ChangeState( previousState );
    }
    
    // Go to the next state
    public function GoToNextState():Void
    {
        ChangeState( nextState );
    }
}

Which leads to modified and new classes like the following.

class Soldier extends Agent
{
    ...
}

class Guard extends Soldier
{
    ...
}

// attacking an enemy
class Attack implements State
{
    private var fsm:StateMachine;
    private var self:Soldier;
    private var enemy:Soldier;
    
    public function Attack( s:Soldier, e:Soldier )
    {
        self = s;
        fsm = self.GetStateMachine();
        enemy = e;
    }
    
    public function Enter():Void
    {
    }
    
    public function Exit():Void
    {
    }
    
    public function Update( time:Number ):Void
    {
        self.ShootAt( enemy );
        if( enemy.IsDead() )
        {
            fsm.GoToPreviousState();
        }
    }
}

// wait for a given period of time then go to next state
class Wait implements State
{
    private var fsm:StateMachine;
    private var self:Agent;
    private var waitTime:Number;
    private var timeRemaining:Number;

    public function Wait( s:Agent, t:Number )
    {
        self = s;
        fsm = self.GetStateMachine();
        waitTime = t;
    }
    
    public function Enter():Void
    {
        timeRemaining = waitTime;
    }
    
    public function Exit():Void
    {
    }

    public function Update( time:Number ):Void
    {
        timeRemaining -= time;
        if( timeRemaining < 0 )
        {
            fsm.GoToNextState();
        }
    }
}

Having used this solution for a couple of years I can't imagine returning to the mess of giant switch statements, even for the simplest projects. And I use the same state machine, agent base class and many of the states themselves across multiple projects, which speeds up development time.

Tags: Actionscript, Artificial Intelligence, Finite State Machine, Game development