State Design Pattern
Many systems wait continuously for the occurrence of some event, and they react to the event by performing computations or changing their state. Once the event is handled, they go back to waiting for the next event. Such systems are called reactive systems or event driven systems. Applications written for such systems follow a paradigm called event driven programming. In these programs the application is not in control while it waits for an event: event driven programming follows a principle called the Hollywood principle (“don’t call us, we’ll call you”): the flow of control is inverted from the application’s viewpoint. The application doesn’t call some other code, like when using a library, but defines the code to be called by the event driven framework. So when an event is generated and dispatched, it is the framework which calls the code provided by the application. This code behavior is called inversion of control:
The response to an event does not depend on the event alone, the execution context is at least as important. We can store the execution context into a multitude of variables and flags and test the values of those flags/variables every time the system need o react to an event, and the system can change its current state modifying the value of those state variables. This approach, sometimes referred to as the “event -action paradigm”, is not practical, not readable, difficult to extend and mantain, prone to bugs and inconsistencies: it needs lots of convoluted if tests, evaluation of nested conditional statements and changing state means changing the value of a number of variables, which can lead to inconsistent states. Finite state machines are a formalism that allows us to represent an event driven system by separating the sytem’s behavior into a well defined set of states. State machines:
- use a single state variable to define a chunk of behavior instead of multiple flags and variables
- drastically cut down if tests and conditional statements
- make transistions from a state to another simple (there can be no inconsistent states): changing state amounts to assigning to a single state variable
The state variable represents the qualitative aspect of the current state. Some state machines can have other variables that represent the quantitative aspect of the state (extended state variables): such machines are called extended state machines, or state machines with memory. I’m not diving into a complete explanation of state machines here, if you want to know more about state machines, and their UML statecharts evolution I reccomend you to read this book: Practical UML Statecharts in C/C++: Event-Driven Programming for Embedded Systems.
Finite State Machine implementation using the State desing pattern
The State desing pattern is an OOP implementation of finite state machines. The GoF book says that the State pattern “allows an object to alter its behavior when its internal state changes. The object will appear to change its class”. In the State patttern the different states are encapsulated into objects, while the state machine’s execution context is represented by an object of the Context class:
The Context is the system we’re representing: the Context class declares an interface for handling all the possible events the system can respond to, mantains a reference to an object of abstract type State and delegates to it the handling of the events. The State class mirrrors the event handling interface of the Context class, and each concrete state subclass implements the event handling code for each event. The State class can have a reference to the Context, or the Context can pass an instance of itself to the State class when it calls the event hadlers (this second approach is useful when the concrete state classes can be shared and reused with many contexts so they need to know which context they are working with each time they handle an event). The Context has a setter method to let the state classes change the context’s state. Generally the context class can have a method for each event, but the interface can be simplified by using a single event handling method that accepts a base Event object as argument: in this case the event handler implementation must discriminate the event based on its type, and handle it accordingly:
A finite state machine example: a text adventure
When I was a kid, fancy graphics and surround sound was not what adventure games were all about. I remember spending lots of time playing games like the Zork series. If you don’t know what I’m talking about I suggest you find a way to get your hands on a copy of the game and give it a try. They’re very good old fashioned text adventure games, and a very interesting application of state machines. Here I’m coding a very bare bones text based adventure, where the goal is to open a chest which is in one of the three rooms that make up the game map (not quite the open world game you were expecting , I know). Each room contains an item:
The player can go from one room to the other by writing “go east”, or “go north”; you can look around the room with “look around”, to search for interesting items, and you can pick up stuff writing “pick up” and the item name. Original text adventures like Zork used a complex language parsing system, that allowed you to insert any type of command, and the game would try to exectute them. This example is just trying to explain finite state machines basics, so I’m using string matching to “parse” the commands. Available commands are hard coded into the game, and if a command is unknown the game just rejects it. Let’s see some code:
// State.h
#include <string>
class Game;
class State
{
public:
virtual ~State() {}
virtual void OnCommand(Game *context, std::string const &command) = 0;
virtual void OnEntry(Game *context) = 0;
virtual void OnExit(Game *context) = 0;
protected:
State();
};
The command that we write on the console is the event that the application dispatches to the state machine: the State base abstract class define a OnCommand() method that takes the game context class (which represents the current execution context of the game) and a command string. The string containing the command from the console is our event object, so the event handling code will have to match the string with a known command (get the event “type”) and perform the corresponding action. Generally it’s a good idea to enumerate event types, in this case I match the string with hard coded values using if statements (which is the kind of construct FSM helps you avoid, so bear with me for this example). The State class has an OnEntry() and OnExit() methods that represents entry and exit actions, actions that are performed whenever we enter or leave a specific state (again, if you don’t know about entry/exit actions refer to this excellent book on the topic). Concrete state classes derive from the State class, implement the event handlers and add a bit of state to manage data that is useful in a specific state:
// State.h
class StartRoomState : public State
{
public:
void OnCommand(Game *context, std::string const &command) override;
void OnEntry(Game *context) override;
void OnExit(Game *context) override;
private:
bool m_first_time = true;
bool m_apple_picked = false;
};
class KeyRoomState : public State
{
public:
void OnCommand(Game *context, std::string const &command) override;
void OnEntry(Game *context) override;
void OnExit(Game *context) override;
private:
bool m_key_picked = false;
};
class ChestRoomState : public State
{
public:
void OnCommand(Game *context, std::string const &command) override;
void OnEntry(Game *context) override;
void OnExit(Game *context) override;
};
Finally, the Context class is our game execution context, that stores the current state as well as some other extended state variables (a kind of inventory):
// State.h
class Game
{
public:
Game();
~Game() {}
void OnCommand(std::string const &command);
void SetState(State *new_state); // state setter function
bool HasApple() { return m_has_apple; } // getters/setters for extended state variables
void SetApple(bool b) { m_has_apple = b; }
bool HasKey() { return m_has_key; }
void SetKey() { m_has_key = true; }
void Win() { m_win = true; }
bool HasWon() {return m_win; }
static State *m_start_room_state; // concrete state objects
static State *m_key_room_state;
static State *m_chest_room_state;
private:
State *m_current_state; // current state (state variable)
bool m_has_apple = false; // extended state variables
bool m_has_key = false;
bool m_win = false;
};
The Game class has also three static references to State, that allow the concrete state classes to easily change the context’s current state, as well as getters and setters for the extended state variables:
// State.cpp
Game::Game()
{
m_current_state = m_start_room_state;
m_current_state->OnEntry(this);
}
void Game::OnCommand(std::string const &command)
{
m_current_state->OnCommand(this, command);
}
void Game::SetState(State *new_state)
{
// leave the current state - execute exit action
m_current_state->OnExit(this);
// state transistion
m_current_state = new_state;
// enter the new state - execute enter action
m_current_state->OnEntry(this);
}
The implementation for the concrete state classes is quite long but extremely simple. Their event handling methods just check for a match with the command string and print something to the console to interact with the player. In some cases the command causes the game to transition to another state, which in our case means changing room:
// State.cpp
void StartRoomState::OnEntry(Game *context)
{
if (m_first_time)
{
std::cout << std::endl << "welcome to state machine quest - a simple but functional adventure into the realm of finite state machines." << std::endl;
std::cout << "you are in a small room with two doors, one on the east side, the other on the south side." << std::endl;
m_first_time = false;
}
else
std::cout << "you entered a small room with two doors, one on the east side, the other on the south side." << std::endl;
}
void StartRoomState::OnExit(Game *context)
{
std::cout << "you exited the small room with two doors" << std::endl;
}
void StartRoomState::OnCommand(Game *context, std::string const &command)
{
if (command == "go east")
{
std::cout << "going through the door on the east side..." << std::endl;
context->SetState(Game::m_chest_room_state);
}
else if (command == "go west")
std::cout << "ouch! you bumped into a brick wall." << std::endl;
else if (command == "go north")
std::cout << "ouch! you bumped into a brick wall." << std::endl;
else if (command == "go south")
{
std::cout << "going through the door on the south side..." << std::endl;
context->SetState(Game::m_key_room_state);
}
else if (command == "look around")
{
std::cout << "it's a small room with a door on the east side and another door on the south side" << std::endl;
if (!m_apple_picked)
std::cout << "there's an apple in the room" << std::endl;
}
else if (command == "pick up apple")
{
if (!m_apple_picked)
{
std::cout << "you picked up a juicy red apple" << std::endl;
context->SetApple(true);
m_apple_picked = true;
}
else
std::cout << "you already picked up the apple." << std::endl;
}
else if (command == "eat apple")
{
if (context->HasApple())
{
std::cout << "mmm.. delicious!" << std::endl;
context->SetApple(false);
}
else
std::cout << "I can't eat an apple, too bad I haven't got one!" << std::endl;
}
else if (command == "use key")
{
if (context->HasKey())
std::cout << "ther's nothing to use the key with." << std::endl;
else
std::cout << "Which key? I have got no key!" << std::endl;
}
else
std::cout << "sorry, I didn't understand. say again?" << std::endl;
}
Each concrete state class may have some data to indicate if the item in the current room/state has been picked up or is still present in the room. The game context class keeps track of the inventory into a couple of extended state variables (an apple, or the key for the chest). The event driven framework is our main application, that simply loops until the game ends. Each iteration it dispatches the command from the console to the Game, which handles the command by delegating to its current State:
// main.cpp
#include "State.h"
#include <iostream>
int main(int argc, char **argv)
{
system("cls");
Game game;
std::string command;
while (!game.HasWon())
{
getline(std::cin, command);
std::cout << std::endl;
game.OnCommand(command);
}
return 0;
}
Let’s run the game:
welcome to state machine quest - a simple but functional adventure into the realm of finite state machines. you are in a small room with two doors, one on the east side, the other on the south side. go north ouch! you bumped into a brick wall. go south going through the door on the south side... you exited the small room with two doors you entered a dimly lit room. There's a door on the north side. pick up key you picked up an old, rusted key. go north going through the door on the north side... you exited the dimly lit room. you entered a small room with two doors, one on the east side, the other on the south side. pick up apple you picked up a juicy red apple eat apple mmm.. delicious!
I suggest you download the full source code and see what commands the game implements, and give it a go. I had lots of fun while coding it.