This tutorial will implement a reusable Finite State Machine using C++. We will then illustrate the concept by applying the implemented Finite State Machine in a few example use cases.
Refactored the code and Updated the tutorial on 31 March 2022.
Read the C# tutorial on Implementing a Finite State Machine Using C# in Unity.
Contact me:
You can find the source code for this project on GitHub https://github.com/shamim-akhtar/fsm-cpp.
This tutorial requires a basic understanding of object-oriented programming and inheritance.
This tutorial aims to make our Finite State Machine reusable by using C++ templates for the state type.
There are several ways you can implement a finite state machine using C++. The easiest and fastest way probably is to use the enumerator type and the switch-case statement. However, in this tutorial, we are not going to do that. Instead, we will use a slightly sophisticated, more robust, generic class-based approach to reuse across multiple projects.
At the same time, we also want to extend the functionality by using functors in the same framework.
But first, let’s recap on what is a Finite State Machine.
Definition
Finite State Machine (or FSM in short) is a computational pattern that defines and models state behaviour.
At any given time, a Finite State Machine can exist in only one state out of a set of a possible number of states. This state can change to another in response to some inputs (sometimes called events).
The process of switching from one state to another is called a transition.
The Classes
For organization purposes, we will put the generic reusable codes in the Patterns namespace. You can put them in any other namespace as well.
The State Class
The State class is the base class for a Finite State Machine state. It is a data structure (type) that encapsulates the state-related functionalities. We will implement this class in the section after FiniteStateMachine class implementation. For now, we define the basic structure.
namespace Patterns
{
template <typename T>
class State
{
public:
}
}Code language: C++ (cpp)We will leave it as above for now and create additional functionalities later.
The Finite State Machine
As defined above, a Finite State Machine.
- consists of a set of states,
- and at any given time, a Finite State Machine can exist in only one state out of these possible states.
Thus, we will need a variable to store the collection of states. This collection will represent a set of states. And then, we will need a variable to keep the current state of the Finite State Machine.
// A Finite State Machine
// - An FSM consists of a set of states,
// - and at any given time, an FSM can exist in only one
// state out of these possible set of states.
// A map to represent the a set of states.
std::map<T, State<T>*> mStates;
// The current state.
State<T>* mCurrentState;Code language: C++ (cpp)To construct the FiniteStateMachine class, we probably won’t need any arguments. At least, not for now. We will proceed with a default constructor.
FiniteStateMachine()
: mCurrentState(0)
{
}Code language: C++ (cpp)Add State to the Finite State Machine
In the previous section, we created the variable that stores the set of states. Now we will create a method that will fill that set by adding state.
template <class S>
State<T>& add(T id)
{
static_assert(not std::is_same<State<T>, S>());
mStates[id] = std::make_unique<S>(*this);
return *mStates[id];
}
Code language: C++ (cpp)Get State from the Finite State Machine
A method that returns a State based on the key.
State<T>& getState(T stateID)
{
return *mStates[stateID];
}
Code language: C++ (cpp)Set the current State to the Finite State Machine
Now perhaps the most critical function of the Finite State Machine, setCurrentState. This method will set the current state of the Finite State Machine.
What happens when we set a state to the current State? There are two possible code paths to it. The first code path is when the previous-current State is valid, and the second code path is when the previous-current state is invalid (or null).
void setCurrentState(T stateID)
{
State<T>* state = &getState(stateID);
setCurrentState(state);
}
Code language: HTML, XML (xml)Then we create a protected method.
void setCurrentState(State<T>* state)
{
if (mCurrentState == state)
{
return;
}
if (mCurrentState != nullptr)
{
***
}
mCurrentState = state;
if (mCurrentState != nullptr)
{
***
}
}
Code language: C++ (cpp)The above code implements the setCurrentState method. If the previous-current State of Finite State Mchine is invalid, the implementation directly sets the State to the mCurrentState. However, if the previous-current State was not null, then what happens?
Can we still overwrite the previous-current state with the new current state?
The answer is probably not. We might want to implement specific functions whenever a state exits and a new state enters. How do we then implement this into our current code?
Enter and Exit
The answer is simple. Create two virtual methods in the State class called enter and exit. The base State class implements nothing for both the enter and exit methods and instead relies on the application to create concrete implementations of the base State class. Then call these two methods whenever there is a change in the State.
void setCurrentState(State<T>* state)
{
if (mCurrentState == state)
{
return;
}
if (mCurrentState != nullptr)
{
mCurrentState->exit();
}
mCurrentState = state;
if (mCurrentState != nullptr)
{
mCurrentState->enter();
}
}
Code language: C++ (cpp)We will finally put an update method to the FSM and the State class.
void update()
{
if (mCurrentState != nullptr)
{
mCurrentState->update();
}
}
Code language: C++ (cpp)Completing the State Class
We have three essential function calls. These are the enter, exit, and update. We will keep these methods virtual.
virtual void enter()
{
}
virtual void exit()
{
}
virtual void update()
{
}
Code language: C++ (cpp)Finally, we will complete the State class by adding a constructor and the essential variables.
State Constructor and Other Essentials
// The ID of the state.
inline T getID()
{
return mID;
}
inline const std::string& getName() const
{
return mName;
}
explicit State(FiniteStateMachine<T>& fsm, T id,
std::string name = "default")
: mName(name)
, mID(id)
, mFsm(fsm)
{
}
virtual ~State() {}
Code language: C++ (cpp)We have implemented a generic reusable Finite State Machine that we can reuse/override and apply based on what is required by our application domain down the stream. We can also use function callbacks to provide the necessary behaviour without deriving a new State class.
You can find the source code for this project on GitHub https://github.com/shamim-akhtar/fsm-cpp.
I have also added several examples for the different use cases of the Finite State Machine. Fork the repository and try out the various examples.
Also read: Unity AI Development: An xNode-based Graphical FSM Tutorial
The Complete Header File
#pragma once
#include <memory>
#include <map>
#include <string>
#include <cassert>
namespace Patterns
{
template <typename T>
class FiniteStateMachine;
template <typename T>
class State
{
public:
// The ID of the state.
inline T getID()
{
return mID;
}
inline const std::string& getName() const
{
return mName;
}
explicit State(FiniteStateMachine<T>& fsm, T id,
std::string name = "default")
: mName(name)
, mID(id)
, mFsm(fsm)
{
}
virtual ~State() {}
virtual void enter()
{
}
virtual void exit()
{
}
virtual void update()
{
}
protected:
std::string mName;
T mID;
FiniteStateMachine<T>& mFsm;
};
template <typename T>
class FiniteStateMachine
{
// A Finite State Machine
// - An FSM consists of a set of states,
// - and at any given time, an FSM can exist in only one
// State out of these possible set of states.
// A map to represent the a set of states.
protected:
std::map<T, std::unique_ptr<State<T>>> mStates;
// The current state.
State<T>* mCurrentState;
public:
FiniteStateMachine()
: mCurrentState(nullptr)
{
}
template <class S>
State<T>& add(T id)
{
static_assert(not std::is_same<State<T>, S>());
mStates[id] = std::make_unique<S>(*this);
return *mStates[id];
}
State<T>& getState(T stateID)
{
return *mStates[stateID];
}
State<T>& getCurrentState()
{
return *mCurrentState;
}
const State<T>& getCurrentState() const
{
return *mCurrentState;
}
void setCurrentState(T stateID)
{
State<T>* state = &getState(stateID);
setCurrentState(state);
}
void update()
{
if (mCurrentState != nullptr)
{
mCurrentState->update();
}
}
protected:
void setCurrentState(State<T>* state)
{
if (mCurrentState == state)
{
return;
}
if (mCurrentState != nullptr)
{
mCurrentState->exit();
}
mCurrentState = state;
if (mCurrentState != nullptr)
{
mCurrentState->enter();
}
}
};
}
Code language: C++ (cpp)Example Use Case
For our use case, we will use the famous turnstile example.
Create a new file called main.cpp and add the following code. Run the program and see how it behaves.
#include "FiniteStateMachine.h"
#include <memory>
#include <iostream>
#include <conio.h>
#include <string>
using namespace Patterns;
bool KeyPresses[255];
enum class TurnstileStateType
{
LOCKED,
UNLOCKED,
};
class TurnstileLockedState : public State<TurnstileStateType>
{
public:
TurnstileLockedState(FiniteStateMachine<TurnstileStateType>& fsm)
: State<TurnstileStateType>(fsm,
TurnstileStateType::LOCKED,
"Locked")
{
}
void enter()
{
State<TurnstileStateType>::enter();
printf("Turnstile state: LOCKED\n");
}
void update()
{
State<TurnstileStateType>::update();
if (KeyPresses['c'])
{
printf(" - coin inserted, unlocking turnstile\n");
mFsm.setCurrentState(TurnstileStateType::UNLOCKED);
}
else
{
printf("Please insert a coin by pressing c to unlock the turnstile.\n");
}
}
};
class TurnstileUnLockedState : public State<TurnstileStateType>
{
public:
TurnstileUnLockedState(FiniteStateMachine<TurnstileStateType>& fsm)
: State<TurnstileStateType>(fsm,TurnstileStateType::UNLOCKED, "Unlocked")
{
}
void enter()
{
State<TurnstileStateType>::enter();
printf("Turnstile state: UNLOCKED\n");
}
void update()
{
State<TurnstileStateType>::update();
if (KeyPresses['p'])
{
printf(" - pushed, locking turnstile\n");
mFsm.setCurrentState(TurnstileStateType::LOCKED);
}
}
};
int main(int argc, char* argv)
{
printf("--------------------------------------------\n");
printf("An example demo for the Finite State Machine\n");
printf("--------------------------------------------\n");
printf(" Press the c key to insert coin.\n");
printf(" Press the p key to open the turnstile\n");
printf(" Press the q key to quit\n");
printf("--------------------------------------------\n");
// create the state machine for the turnstile.
std::unique_ptr<FiniteStateMachine<TurnstileStateType>> fsm = std::make_unique<FiniteStateMachine<TurnstileStateType>>();
State<TurnstileStateType>& state_locked = fsm->add<TurnstileLockedState>(TurnstileStateType::LOCKED);
State<TurnstileStateType>& state_unlocked = fsm->add<TurnstileLockedState>(TurnstileStateType::UNLOCKED);
fsm->setCurrentState(TurnstileStateType::LOCKED);
bool done = false;
while (!done)
{
char input = _getch();
KeyPresses[input] = true;
if (KeyPresses['q'])
{
done = true;
break;
}
fsm->update();
for (int i = 0; i < 255; ++i)
KeyPresses[i] = false;
}
printf("You have exited the program. Good bye!\n");
}Code language: C++ (cpp)Read My Other Tutorials
- Flocking and Boids Simulation in Unity2D
- Runtime Depth Sorting of Sprites in a Layer
- Implement Constant Size Sprite in Unity2D
- Implement Camera Pan and Zoom Controls in Unity2D
- Implement Drag and Drop Item in Unity
- Graph-Based Pathfinding Using C# in Unity
- 2D Grid-Based Pathfinding Using C# and Unity
- 8-Puzzle Problem Using A* in C# and Unity
- Create a Jigsaw Puzzle Game in Unity
- Implement a Generic Pathfinder in Unity using C#
- Create a Jigsaw Puzzle Game in Unity
- Generic Finite State Machine Using C#
- Implement Bezier Curve using C# in Unity
- Create a Jigsaw Tile from an Existing Image
- Create a Jigsaw Board from an Existing Image
- Solving 8 puzzle problem using A* star search
- A Configurable Third-Person Camera in Unity
- Player Controls With Finite State Machine Using C# in Unity
- Finite State Machine Using C# Delegates in Unity
- Enemy Behaviour With Finite State Machine Using C# Delegates in Unity
- Augmented Reality – Fire Effect using Vuforia and Unity
- Implementing a Finite State Machine Using C# in Unity
- Solving 8 puzzle problem using A* star search in C++
- What Are C# Delegates And How To Use Them
- How to Generate Mazes Using Depth-First Algorithm
A committed and optimistic professional who brings passion and enthusiasm to help motivate, guide and mentor young students into their transition to the Industry and reshape their careers for a fulfilling future. The past is something that you cannot undo. The future is something that you can build.
I enjoy coding, developing games and writing tutorials. Visit my GitHub to see the projects I am working on right now.
Educator | Developer | Mentor
Correct the code
State& state_locked = fsm->add(TurnstileStateType::LOCKED);
State& state_unlocked = fsm->add(TurnstileStateType::UNLOCKED);
to
State& state_locked = fsm->add(TurnstileStateType::LOCKED);
State& state_unlocked = fsm->add(TurnstileStateType::UNLOCKED);