Finite State Machines for AI in Actionscript

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
    {
        if( currentState )
        {
            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.

Addendum 2011

There's an Actionscript 3 version of this in my Github repository.

14 thoughts on “Finite State Machines for AI in Actionscript

  1. Very cool, thanks for taking the time to post this! I don’t get to do a lot of games, but when I do, this looks extremely useful compared to the switch statement approach I’ve used in the past. Awesome.

  2. Yes, very nice indeed.. I know the state pattern form the adobe tutorial ‘ Creating a video player using the state design pattern and ActionScript 3.0′ .. But I like this implemantation much better, I am going to give it a go later this day .. Thank you for sharing !!

  3. I am more interested on how to manage states where each state is non-deterministic, meaning that one state can lead to more than 1 state.

    Assuming we use a duck. The duck idle state can transition to swimming state OR walking state OR flying state. How would manage this?

    Also I would like to see on the usage of a state transition table to manage these states. Instead of hardcoding on the states to determine which to go next, use a table instead.

    The state themselves will execute the actions. Using the old example of duck, when duck is in Flying State/Behavior, it executes flying mode that can bypass any terrain. If its in walking mode, it have to go around obstacles.

    This will lead to a better reusable class. We could just plug in any state we want and throw them out if not needed without creating a spaghetti code. All the decision making is in 1 area which is the transition table.

  4. @ayu

    For every NFA there is a DFA so you basically have to convert the NFA to DFA.

    Another approach that will help you both with NFA and implementing the transition table would be using graphs.

    @Richard, great and easy to follow resource

  5. Pingback: finite state machine in as3 (for game develop) « CODE@????

  6. Pingback: Daniel Sidhion's Development Blog » A great example of Finite State Machines

  7. I know this is an old article, but you have an error in your code:

    In StateMachine.changeState() you do the following:

    currentState.Exit();

    but currentState might be null if you’re changing to the first state.

    Helpful all the same though!

  8. Hi Richard, just followed a link from Jesse Warden’s page over here.

    If you like FSM’s, you’ll be gaga over Hierarchical State Machines (HSM’s). I have a Google Code project with an AS2 and an AS3 implementation:

    http://code.google.com/p/eqsim-state-machine-and-interface-components/

    along with my equipment interface components (knobs, dials, displays, etc.) from my book http://www.flashsim.com.

    Also check out Troy Gardner’s work (his FSM and HSM is in a framework called COGS), at http://code.google.com/p/troyworks/. He has an elegant implementation of state machines following the pattern originally developed by Miro Samek (http://www.state-machine.com/).

    Just wanted to get the word out to fellow state machine enthusiasts!

  9. You are brilliant, you have just created A CFSM (Concurrent Finite State Machine) by utilizing Object-Oriented and Layering Concept .. By separating Actors from Behaviors, and by separating each behavior in a different object, you break Behavior Linearity into Concurrency …

  10. I read that David Crane, the guy who developed Pitfall for Atari 2600, used bitwise operators to create each of the 255 screens. Any idea how he did this?

  11. Pingback: Finite State Machines with Ash

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>