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:

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:

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):

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:

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:

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:

Let’s run the game:

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.

source code

Leave a Reply

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