Hierachical Finite State Machines

In this post I talk about hierarchical state machines and present a simple implementation, based on the state pattern. It is by no means a comprehensive explanation, and I skim over some important details (in which we all knows the devil cozily dwells). So if you want to know more you can read the book by Miro Samek, “Practical UML Statecharts in C/C++: Event-Driven Programming for Embedded Systems”, to which this post is (heavily) inspired. The book is a must read for everyone who wants to implement an efficient framework for an event driven, reactive system.

A brief review of classic Finite State Machines

Finite State Machines (FSM for short) are a powerful approach to reducing complexity in code: a system is partitioned in (finite) chunks of behaviors, called states, and during its lifetime the system is always in one (and only one) of these states.  The system receives events, and all the events are handled based on the current state. A state captures the history of the system up to that point, and provides a clear execution context for handling the event, instead of relying on a multitude of (often overlapping) variable and flags and conditional statements. A system can move from one state to another depending on which event occurs by means of state transistions. 

Some state machines use additional variable to represent the state, called extended state variables. In these implementations the state variable represents the qualitative state, while the extended state variables represent the quantitative state. These state machines are often called extended state machines (or state machines with memory). The extended state variables are evaluated in guard conditions during transitions.

Traditional finite state machines are a pretty handy tool but suffers from what is called state explosion: many events are often handled in the same way in multiple states as there’s no way to factor out common behavior in a classical FSM and many transitions and actions are repeated in different states. What is needed is a way to reuse the common behavior in order to share it among different states.

HFSM basic concepts:

Hierachical State Machines address the shortcomings of traditional Finite State Machines. They provide an efficient way of capturing the commonality of behavior between states and can represent the complexity of a sistem avoiding the state explosion. This behavioral ineritance is implemented by using composite states, states that contain other states, and leaf states (which do not). A state diagram becomes a tree, with a top state at the root.

A HSM state diagram: boxes are states, arrows are transitions, black circles with arrows are initial transitions. Each transition can have an associated guard condition (in square brackets) and actions (after the slash). Entry and exit conditions are supported.

States and state configurations

In every moment the hierarchical state machine is in one defined state, the current state which is always a leaf state. When the state machine is in a specific state, at the same time it’s considered to be in all the enclosing superstates of that state: the actual state is represented by the specific state the HFSM is in, and all the enclosing (composite) superstates of that state. All these states together represent the current state configuration of the HFSM. For this reason, an HFSM is said to be in a current state configuration rather than in specific state:

A hierarchical state machine is said to be in a state configuration: if it is in state S11, at the same time it is in states s1 and s

When the state machine receives an event, the current state gets a chance to handle it. If it doesn’t handle it, the event is passed to the current state’s superstate, and so on, until a state handles the event or (if the top state is reached) it is silently discarded.

Transitions

As in traditional FSMs, transistions connect two states, a source state and a target state. In a HFSM the state which is the source of the transition isn’t necessarily the current state but may be a superstate of the current state, and it’s called the main source state; the state which is the target of the transition is called the main target state. Transistioning from a main source state to a main target state means exiting the current states and all the parent states of the current state up to the lowest superstate that is common to both the main source state and the main target state; this state is called the Least Common Ancestor (LCA) of the main source and target states. Note that the LCA itself is not exited. The HFSM then enters the states below the LCA up until the main target state. If the target state is a composite state, the HFMS then enters the substates using initial transitions until it reaches a leaf state:

Steps of a transition: a transition involves more steps for a HSM than a traditional state machine

Transitions are indicated with an arrow and the associated event. They can have actions associated with them. In the diagram actions are indicated on the corresponding transition after the /. Transitions can also have guard conditions, indicated in square brackets: guard conditiona often operate on the extended state variables and indicates that the associated transition is taken only if the guard evaluates to true.

HSM Implementation

A HSM can be implemented in several ways. This implementation is focused on simplicity rather than speed performance. It is a variation of the State pattern where the state is an object derived from the state base abstract class: entry and exit actions and initial transitions are implemented as separate methods OnEntry(), OnExit() and OnInitial() respectively, and the generic event handler, OnEvent(), uses a switch statement to discriminate the event to handle:

The OnEntry() method returns a particular value from a Ret enumeration, based on how it handled the event. An Event class is also defined, which contains a value from a Signal enumeration which is only forward declared (it’s definition is provided in the actual state machine implamentation file). A state object mantains a pointer to the parent superstate as well as a pointer to the target state of the target of its initial transition (if the state is a leaf state the pointer is null). A particular state, called the Top state, is defined to act as the root of all other states:

Its only task is to implement the event handling method which ignores all events, and to be at the top of the hierarchy of all other states.

The HSM class implements the state machine

The base event processor class contains the pointer to the current state and has three member functions:

  • a Init() function which dispatches the initial event to the top state, triggering the initial transition from the top state. The passed event can be used to initialize the extended state variables:

  • a Dispatch() function, the core of the event processor, which dispatches events to the state machine, and is in charge of handling transitions between states: a state only set the main target state of a transition, and the Dispatch() method performs all the necessary work to transition from one state configuration to another:

  • a ChangeState() member function that assigns the transition’s target state to the current state

As an example, the following is the code inside the OnEvent() member function of state S:

The event is demultiplexed, based on its signal value, and then handled accordingly. If the event is not handled by a particular states, the event processor goes up the state hierarchy and tries to find a state which handles the event (possibly triggering a transition). If it can’t find a state that handles the event, that event gets discarded.

Code for the example is provided on GitHub

Example application: a player

As an example, I used a slightly different implementation of this hierarchical state machine in my game, as a component of my player object: the state machine takes care of the different states the player can be in (idle, moving, attacking, jumping and so on), and every frame the current state is updated. During the update the state checks the “state” (sorry, but is indeed a matter of state, no pun intended) of the player object, checking its input component, animation component, physics component and the rest. it then performs the relevant actions, or transitions to another state. The only difference with this implementation is that each state takes care of passing the buck to its superstate (using the chain of responsibility design pattern) if the event is not handled in that state, so there’s no need for returning a return code for the dispatcher. This is the result:

Leave a Reply

Your email address will not be published.