I thought it might be nice to share a snippet of code that has worked out really well for me over the past few months. I use it literally everywhere throughout the codebase of my videogame BEEP (AI, UI, Audio etc…). It’s a simple, extensible, portable finite state machine written in C++.

According to Wikipedia, a finite state machine is:

a model of behavior composed of a finite number of states, transitions between those states, and actions.

State machines are literally everywhere in almost every kind of software. Videogames take them to a whole new level with additional models like Heirarchical Finite State Machines and Decision Trees.

But often times, you just want a plain old vanilla state machine with the ability to:

  1. Perform actions within the current state.
  2. Transition to any other state from the current state.
  3. Perform exit and enter actions during a transition.

That’s about as simple as a FSM gets. What follows is my attempt at creating an extensible and simple FSM that can literally be used anywhere you need it and on any platform (Win/MacOS/Linux).

It works like this: there are two objects, finite state machines (FSM) and states (FSMState). A state machine contains a collection of states within it (I’m using std::vector to store the states which are first wrapped in an std::tr1:shared_ptr so you don’t have to worry about garbage collection).

So the first step in setting this up is to sub-class FSMState to create new state type for each state in your machine. An enemy AI, for example, might have IdleState, ChaseState, AttackState and DeadState. Each state has an Update() function that performs actions when the FSM is in that state. It also has a OnENTER() and OnEXIT() functions that can be overidden to perform anything you like when the state is first entered, or when it exits.

When FSM::Update() is called, the current state in the machine has it’s Update() function called which will perform the actions for that state and possibly trigger a transition. If a transition is triggered, the FSM will automatically call the DoEXIT() and DOENTER() functions for the old and new states respectively.

Getting Started:

To setup the FSM:

  1. At the top of your C++ source: #include <FSM.h>
  2. Create a new state machine: FSM *myFSM = new FSM();
  3. Create a bunch of FSMState sub-classes (your states).
  4. Add each states to your FSM like this: myFSM::AddState();

Once the FSM is setup, just call myFSM::Update() to keep the machine running!

NOTE: One trick here, I’m using the Boost shared pointer implimention to store the states. This is NOT a part of the C++ standard, but seems to be ubiquitous in it’s adoption and usage in the industry. In order to use it, you will have to download and include these libraries (not a difficult task). Hopefully this inclusion doesn’t disqualify this code as being ’simple’.

FSM.H

//FSM.h
#ifndef FSM_H
#define FSM_H

#include <iostream>
#include <string>
#include <vector>
#include <memory>

class FSM;

//An individual state (must belong to a FSM)
//This is an abstract class and must be sub-classed
class FSMState
{
public:
  FSMState(){};
  FSMState(FSM *fsm){};
  virtual ~FSMState(){};
  virtual void Update(const float& dt) = 0;
  virtual void DoENTER(){};
  virtual void DoEXIT(){};

  std::string stateName;  //used to switch between states
  FSM *fsm;
};

//A vector of shared pointers housing all the states in the machine
typedef std::vector< std::tr1::shared_ptr<FSMState> > StateBank;

//---------------------------------------
//A Simple Finite State Machine
class FSM
{
public:
  FSM();
  ~FSM();
  void Update(const float& dt);

  void TransitionTo(std::string stateName);
  void DelayTransitionTo(std::string stateName);
  void AddState(FSMState *newState, bool makeCurrent);
  std::string GetState();

public:
  FSMState *currentState;
  std::string delayState;

   //Bank to house list of states
  StateBank stateBank;
  std::vector< std::tr1::shared_ptr<FSMState> >::iterator iter;
};

#endif

FSM.cpp

//FSM.cpp
#include "FSM.h"

//Constructor
FSM::FSM()
{
  currentState = NULL;
  delayState = "NONE";
}

//Destructor
FSM::~FSM()
{
  stateBank.clear();
}

//Update each tick
void FSM::Update(const float& dt)
{
  //Make sure a current state is loaded
  if (currentState == NULL) return;

  //Check if there are any delayed transition requests
  if (delayState != "NONE")
  {
    TransitionTo(delayState);
    delayState = "NONE";
  }

  //Update the current state, may trigger a transition.
  currentState->Update(dt);
}

//Called to transition to another state
//@param stateName the name of the state to transition to
void FSM::TransitionTo(std::string stateName)
{
  //Find the named state
  FSMState *goToState = NULL;
  for(iter= stateBank.begin(); iter!= stateBank.end(); iter++)
    if ( (*iter)->stateName == stateName )
      goToState = iter->get();

  //Error, trying to transition to a non-existant state
  if (goToState == NULL)
  {
    //Print an error here, or assert if you want
    return;
  }

  currentState->DoEXIT();
  goToState->DoENTER();
  currentState = goToState;
}

//Transition to another state (delayed until beginning of next update)
//@param stateName the name of the state to transition to
void FSM::DelayTransitionTo(std::string stateName)
{
  delayState = stateName;
}

//Add a state to the bank, optionally make it the current state
//@param newState the new state to add to the state machine
//@param makeCurrent is this new state the current state?
void FSM::AddState(FSMState *newState, bool makeCurrent)
{
  //Add this state to the FSM
  std::tr1::shared_ptr<FSMState> newStatePtr(newState);
  stateBank.push_back(newStatePtr);
  //Make this the current state?
  if (makeCurrent) currentState = newState;
}

//What is the name of the current state?
std::string FSM::GetState()
{
  return currentState->stateName;
}