Single Page Version

HSM Book (Single Page)

Introduction
StateValue
State Arguments
Storing Data on Cluster Root State
Restarting States
Selector States
Done States
Sharing Functions Across States
Deferred Transitions
Reusable States
Sharing HSMs
- Sharing states with unrelated owners
- Sharing states with related owners
Sharing State Machines (State Overrides)
Parallel State Machines

Chapter 5. Best Practices

Introduction
Prefer InnerEntry + Sibling to Inner
Nest state-related variables as deeply as possible
Clean up in cluster root state
Avoid state stack queries outside of states
Make each state machine update count

Chapter 1. Getting Started

About HSM

HSM, short for Hierarchical State Machine, is an open-source C++ framework library that can be used to simplify the organization of state-driven code. The implementation is partially inspired by the UML State Machine (aka UML Statechart) standards, as well as by the UnrealScript state system in Unreal Engine 3.

Benefits of using HSM

Most state-driven code can benefit from using any type of state machine library; however, HSM provides the following specific benefits:

Simple to use: making use of HSM is fairly straightforward;
Easy to understand: reading HSM code and understanding how it works is often much simpler than in similar systems mainly due to how transition logic is implemented in-line rather than in a table;
Easy to debug: similarly, since there are no transition table lookups, debugging the state machine is simple. Plus HSM includes a useful tracing feature, as well as a state machine plotting tool;
Scalable: although its main purpose is to provide a method for nesting states, HSM can also be used for single-layer, or flat, state machines with very little overhead;
Performance: HSM has been written with performance in mind.

HSM is particularly well suited to games, or any environment where state changes are made frequently based on complex conditions. However, this does not preclude its use in any other type of software.

License

HSM is an open-source library distributed under the MIT License. In a nutshell, it is a permissive license that allows users to modify the source, and does not force users to distribute the source code with the executable. Of course, although not necessary, if you do decide to use HSM, some form of acknowledgement would certainly be appreciated.

Please see the license file for more details.

Installation

Build Environment

The library is made up of a few header files and a single cpp file: statemachine.cpp. To make use of it, you are expected to build the cpp file as part of your compilation step, and make the headers available for inclusion.

Download a release of the source code (or clone from the master branch).
Assuming the root directory is named "hsm", add "hsm/include" to your compiler's INCLUDE path. This is recommended so that including hsm headers with take the form: #include "hsm/statemachine.h".
Add hsm/src/statemachine.cpp to your compilation step.
Modify hsm/include/hsm/config.h to match your environment and project-specific settings (more on this below) .

Configuration

By default, HSM is configured to be compatible with standard C++ projects, making use of certain STL types, default operator new and operator delete, etc. However, many projects do not make use of the standard types, or provide their own types optimized for their target platform. Thus, the library provides a single header file, hsm/config.h, with macros and typedefs used by the library. This file can be modified to configure HSM to better suit the code environment it's being used in.

Most of the contents of config.h are self-explanatory; but here are a couple of notes for some of the configurable types and definitions:

HSM_STD_VECTOR and HSM_STD_STRING are expected to define types that provide a subset of the std::vector and std::string functionality, respectively. Some code bases avoid using the STL, and define their own types, which are not necessarily compatible with the STL in terms of interface. In this case, one solution would be to provide a wrapper that implements the functionality subset of the STL types to your own types. If this proves too difficult, it may be simpler to replace HSM code that makes use of these types with your own.

RTTI

HSM requires run-time type information (RTTI) for certain features to work. If standard C++ RTTI is enabled in your compiler settings, HSM will use it, and you don't have to worry about it. However, if standard C++ RTTI is explicitly disabled, HSM will enable its custom RTTI, which requires that you add the macro DEFINE_HSM_STATE to each state that you define, for example:

	struct Alive : BaseState
	{
		DEFINE_HSM_STATE(Alive)
	
		virtual Transition GetTransition()
		{
			return InnerEntryTransition<Stand>();
		}
	};

The DEFINE_HSM_STATE macro adds functions used by the custom RTTI system. Note that if you like, you can always add this macro to your states, whether you're using custom RTTI or not, as it is defined to nothing in the latter case.

If standard RTTI is enabled for your project, but you wish to force HSM to use its custom RTTI for whatever reason, you can set the HSM_FORCE_CUSTOM_RTTI to 1 in config.h.

Tools

Useful tools can be found in the hsm/tools directory. This section describes these tools.

plotHsm

Large state machines can be difficult to understand by simply reading code, especially when they have deep hierarchies. The python script hsm/tools/plotHsm.py can be used to parse cpp files containing a state machine implementation, and will render an image and open it.

For instance, if we run the following command:

python plotHsm.py drawing_hsms.cpp

This would produce and open an image like this:

drawing_hsms

The script works by running the hsmToDot.py script to produce a GraphViz "dot" file, then uses GraphViz to render it to an image, and finally opens the image in the default image viewer.

To use this tool, you must install the following:

Python 2.7 (http://www.python.org)
GraphViz 2.18 (Windows: http://www.graphviz.org/pub/graphviz/stable/windows/graphviz-2.18.exe)

Make sure that both python.exe and dot.exe are accessible by adding the relevant paths to the PATH environment variable.

Book Samples

All examples code listings, save a few, that are presented in this book can be found in the hsm/samples/hsm_book_samples/ directory. Each sample is a single cpp file for simplicity, and each code listing in this book provides the sample file name as the first comment of the listing. For instance, the first code listing in Chapter 2 starts like this:

// simplest_state_machine.cpp

So the code for this sample can be found here: hsm/samples/hsm_wiki_samples/source/ch2/simplest_state_machine.cpp.

To build the samples, you will need to install CMake and run cmake . in the hsm_book_samples directory. This will generate the makefile/workspace/solution for the target platform and compilation environment. On Windows, for example, CMake may generate a Visual Studio solution and projects that you can open and build.

Although not required, it can be helpful to build the samples so that you can experiment with them as you read through the book.

Chapter 2. The Basics

Introduction

This chapter will walk you through the basics of using HSM. To keep things simple, we will learn how to author single-hierarchy (aka flat) state machines here, and will cover hierarchical state machines in the next chapter.

The Simplest State Machine

Let's start with the simplest state machine we can write.

// simplest_state_machine.cpp

#include "hsm/statemachine.h"

struct First : hsm::State
{
};

int main()
{
	hsm::StateMachine stateMachine;
	stateMachine.Initialize<First>();
	stateMachine.ProcessStateTransitions();
}

First we include hsm/statemachine.h, which brings in the entire HSM library.

We declare a state named First. States are structs or classes that inherit from hsm::State.

NOTE: We prefer to use structs over classes as they derive publicly by default, so there is no need to specify the 'public' keyword.

In main, we initialize a StateMachine object, telling it that First is its initial state. All StateMachine's must have an initial state to start with.

We then call stateMachine.ProcessStateTransitions, which will evaluate any transitions that must be made, and perform them. In this case, as we have only one state, and it doesn't do anything, this call does nothing.

This is about as simple as it gets. Now let's make this state machine actually do something.

States and Transitions

Let's add some states and transitions.

// states_and_transitions.cpp

#include "hsm/statemachine.h"

using namespace hsm;

struct Third : State
{
	virtual Transition GetTransition()
	{
		return NoTransition();
	}
};

struct Second : State
{
	virtual Transition GetTransition()
	{
		return SiblingTransition<Third>();
	}
};

struct First : State
{
	virtual Transition GetTransition()
	{
		return SiblingTransition<Second>();
	}
};

int main()
{
	StateMachine stateMachine;
	stateMachine.Initialize<First>();
	stateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
	stateMachine.ProcessStateTransitions();
}

Let's look at what's new in this code:

We've brought in the hsm namespace. In general, we recommend doing this in cpp files where state machines are implemented as it drastically reduces the 'hsm::' prefix noise.

We've added 2 more states: Third, and Second. We've also implemented the virtual GetTransition function in all 3 states. This function is where a state returns what transition it wishes to make when StateMachine::ProcessStateTransition gets called. In this case, all 3 states are siblings, meaning they are all at the same hierarchical level (we'll get into the hierarchical part later), and First transitions to Second, which in turn transitions to Third.

In main, we've added a call to stateMachine.SetDebugInfo to give our state machine a name and verbosity level for debugging purposes.

NOTE: The TraceLevel enum supports three values: None, Basic, Diagnostic. We recommend using Basic while authoring your state machines, and Diagnostic when debugging the internals of the library.

Finally, we call stateMachine.ProcessStateTransitions as before. Since we set the debug level to 1, we get the following output:

HSM_1_TestHsm: Init    : struct First
HSM_1_TestHsm: Sibling : struct Second
HSM_1_TestHsm: Sibling : struct Third

The debug output displays the transitions being made. The initial transition to First is followed by two sibling transitions, First to Second, and Second to Third.

Let's also take a look at the plotHsm output for this state machine:

states_and_transitions.cpp.dot.png

The plot of this state machines shows our three states, with dotted arrows signifying sibling transitions that can be made: First can transition to Second, and Second to Third.

NOTE: The plots for the examples in this chapter are too simple to be useful; however, in the next chapter, we make extensive use of plotHsm to better understand the hierarhical state machines presented.

Pretty simple so far, right? Obviously there are many details missing, but we'll get to that soon enough!

Improving Readability

You may have noticed in the previous example that states First, Second, and Third were defined in reverse order; that is: Third, then Second, and finally First. This is typical of C/C++ code as you must always define, or at least declare, a type before it is used; in our case, Second references Third in its GetTransition implementation, and similarly First references Second:

struct Third : State
{
	virtual Transition GetTransition()
	{
		return NoTransition();
	}
};

struct Second : State
{
	virtual Transition GetTransition()
	{
		return SiblingTransition<Third>(); //*** Here
	}
};

struct First : State
{
	virtual Transition GetTransition()
	{
		return SiblingTransition<Second>(); //*** And here
	}
};

It would be nice to order the states any way we'd like; in this case, it would be easier to understand the state machine if First came before Second, and Second before Third. We might be able to do it with some forward declarations, but it's also nice having to declare our states only once. Well, as it turns out, we can have our cake and eat it too, by nesting our states within a struct:

// improving_readability.cpp

#include "hsm/statemachine.h"

using namespace hsm;

struct MyStates
{
	struct First : State
	{
		virtual Transition GetTransition()
		{
			return SiblingTransition<Second>();
		}
	};

	struct Second : State
	{
		virtual Transition GetTransition()
		{
			return SiblingTransition<Third>();
		}
	};

	struct Third : State
	{
		virtual Transition GetTransition()
		{
			return NoTransition();
		}
	};
};

int main()
{
	StateMachine stateMachine;
	stateMachine.Initialize<MyStates::First>();
	stateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
	stateMachine.ProcessStateTransitions();
}

Notice how we've added a struct named MyStates and have nested our three states in a different order within it. We also modified the stateMachine.Initialize call to fully qualify the initial state name (MyStates::First).

The reason this works is because of how template argument dependent name lookup (ADL) works when those names are nested in C++. Without getting into too much detail, when a template function parameter is a nested type, even if it's defined after the template function call, it will be resolved correctly. In our case, SiblingTransition is a template function, and we can pass it the name of a state even though it is defined later because it is nested in the MyStates struct.

NOTE: Later on, we'll show yet another advantage to nesting states in a struct: granting access to a state machine's owner's private members.

State OnEnter and OnExit

The base hsm::State provides two virtual hooks for when a state is entered and exited: OnEnter and OnExit respectively. These can be used to initialize or deinitalize data, systems, etc.

Here's our previous example code with OnEnter/OnExit pairs added to the three states:

// state_onenter_onexit.cpp

#include <cstdio>
#include "hsm/statemachine.h"
using namespace hsm;

struct MyStates
{
	struct First : State
	{
		virtual void OnEnter()
		{
			printf("First::OnEnter\n");
		}

		virtual void OnExit()
		{
			printf("First::OnExit\n");
		}

		virtual Transition GetTransition()
		{
			return SiblingTransition<Second>();
		}
	};

	struct Second : State
	{
		virtual void OnEnter()
		{
			printf("Second::OnEnter\n");
		}

		virtual void OnExit()
		{
			printf("Second::OnExit\n");
		}

		virtual Transition GetTransition()
		{
			return SiblingTransition<Third>();
		}
	};

	struct Third : State
	{
		virtual void OnEnter()
		{
			printf("Third::OnEnter\n");
		}

		virtual void OnExit()
		{
			printf("Third::OnExit\n");
		}

		virtual Transition GetTransition()
		{
			return NoTransition();
		}
	};
};

int main()
{
	StateMachine stateMachine;
	stateMachine.Initialize<MyStates::First>();
	stateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
	stateMachine.ProcessStateTransitions();
}

The output from running the program:

HSM_1_TestHsm: Init    : struct MyStates::First
First::OnEnter
First::OnExit
HSM_1_TestHsm: Sibling : struct MyStates::Second
Second::OnEnter
Second::OnExit
HSM_1_TestHsm: Sibling : struct MyStates::Third
Third::OnEnter

We can see that when a source state makes a sibling transition - or siblings - to a target state, the source state is first exited before the target state is entered.

OnEnter/OnExit vs Constructor/Destructor

Since states are just classes, why not use the constructor/destructor instead of the OnEnter/OnExit functions?

The main reason is that by the time OnEnter is called on a state, all its data has been initialized, including - and most importantly - the owning state machine instance. When using the default constructor, this data is not yet set, and cannot be used. Most functions available to a state depend on the state machine pointer being valid, so these can only be called within OnEnter, not in the constructor.

As for OnExit, there isn't much difference between using it and the destructor; however, we recommend using it for consistency.

NOTE: Another reason for using OnEnter is that it allows for the optional use of StateArgs, a feature we will cover later on.

ProcessStateTransitions

In the examples so far, we've glossed over the details of the stateMachine.ProcessStateTransitions call. In this section, we'll take a look a closer look at this function, starting with some pseudo-code for how it works:

done = false
while (!done)
	transition = currState.GetTransition()
	if (transition != NoTransition)
		currState.OnExit()
		currState = transition.GetTargetState()
		currState.OnEnter()
	else
		done = true

NOTE: This pseudo-code will be expanded in the next chapter to deal with hierarchical state transitions. For now, what we present here is accurate for flat state machines (i.e. that only perform sibling transitions between states).

The important part is to note that the function will keep transitioning between states until there are no more transitions to be made. The following example shows how this works:

// process_state_transitions.cpp

#include <cstdio>
#include "hsm/statemachine.h"
using namespace hsm;

bool gStartOver = false;

struct MyStates
{
	struct First : State
	{
		virtual void OnEnter()
		{
			gStartOver = false;
		}

		virtual Transition GetTransition()
		{
			return SiblingTransition<Second>();
		}
	};

	struct Second : State
	{
		virtual Transition GetTransition()
		{
			return SiblingTransition<Third>();
		}
	};

	struct Third : State
	{
		virtual Transition GetTransition()
		{
			if (gStartOver)
				return SiblingTransition<First>();

			return NoTransition();
		}
	};
};

int main()
{
	StateMachine stateMachine;
	stateMachine.Initialize<MyStates::First>();
	stateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
	
	printf(">>> First ProcessStateTransitions\n");
	stateMachine.ProcessStateTransitions();

	printf(">>> Second ProcessStateTransitions\n");
	stateMachine.ProcessStateTransitions();

	gStartOver = true;
	
	printf(">>> Third ProcessStateTransitions\n");
	stateMachine.ProcessStateTransitions();

	printf(">>> Fourth ProcessStateTransitions\n");
	stateMachine.ProcessStateTransitions();
}

As before, First siblings to Second, and Second siblings to Third; but state Third will only transition back to First if global variable gStartOver is true; otherwise it remains in its state. Here's the output from this program:

>>> First ProcessStateTransitions
HSM_1_TestHsm: Init    : struct MyStates::First
HSM_1_TestHsm: Sibling : struct MyStates::Second
HSM_1_TestHsm: Sibling : struct MyStates::Third
>>> Second ProcessStateTransitions
>>> Third ProcessStateTransitions
HSM_1_TestHsm: Sibling : struct MyStates::First
HSM_1_TestHsm: Sibling : struct MyStates::Second
HSM_1_TestHsm: Sibling : struct MyStates::Third
>>> Fourth ProcessStateTransitions

We can see that the second call to ProcessStateTransitions does nothing. This is because we are in state Third and gStartOver is false, so it returns NoTransition. After that, we set gStartOver = true, and the third call to ProcessStateTransitions has Third sibling to First, First to Second, and Second back to Third where it stops again. Why does it stop in Third again? The reason is that First::OnEnter always resets gStartOver to false, so by the time it reaches Third again, it will not transition back to First. Indeed, if we remove First::OnEnter, ProcessStateTransitions would end up in an infinite loop of sibling transitions: Third -> First -> Second -> Third -> First -> etc.

NOTE: HSM triggers an assertion when infinite transitions are detected.

So now we see how changing some data in between calls to ProcessStateTransitions can result in different transitions being made. In this example, the data is a global variable that is modified outside the state machine; however, often the data changes are made from the states themselves.

At what frequency should ProcessStateTransitions be called? That depends on your application, but here are couple of examples:

In games or real time simulations, you would likely call ProcessStateTransitions every frame, knowing that the state of the world, inputs from the player, or other data may have changed since the last frame.
In event-based systems, such as UI, you'd want to call ProcessStateTransition after an event modifies some data.

A final note on State::GetTransition: this function's role is simply to return what transition to make, not to perform any state-specific logic. Instead, you can use State::Update for this purpose, which is covered in the next section.

UpdateStates

When you need a state to perform some actions while in that state, you can implement the virtual Update function. This function will be called on the current state when StateMachine::UpdateStates is called:

// update_states.cpp

#include <cstdio>
#include "hsm/statemachine.h"
using namespace hsm;

bool gPlaySequence = false;

struct MyStates
{
	struct First : State
	{
		virtual Transition GetTransition()
		{
			if (gPlaySequence)
				return SiblingTransition<Second>();
			
			return NoTransition();
		}

		virtual void Update()
		{
			printf("First::Update\n");
		}
	};

	struct Second : State
	{
		virtual Transition GetTransition()
		{
			if (gPlaySequence)
				return SiblingTransition<Third>();
			
			return NoTransition();
		}

		virtual void Update()
		{
			printf("Second::Update\n");
		}
	};

	struct Third : State
	{
		virtual Transition GetTransition()
		{
			return NoTransition();
		}

		virtual void Update()
		{
			printf("Third::Update\n");
		}
	};
};

int main()
{
	StateMachine stateMachine;
	stateMachine.Initialize<MyStates::First>();
	stateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);

	stateMachine.ProcessStateTransitions();
	stateMachine.UpdateStates();

	stateMachine.ProcessStateTransitions();
	stateMachine.UpdateStates();

	gPlaySequence = true;

	stateMachine.ProcessStateTransitions();
	stateMachine.UpdateStates();

	stateMachine.ProcessStateTransitions();
	stateMachine.UpdateStates();
}

We've added the Update function to states First, Second, and Third. We use global variable gPlaySequence to make First sibling to Second then to Third. In the main function, we now pair up the call to ProcessStateTransition with UpdateStates. Typically, we'd want to call these two functions in succession once per frame (or whenever the state machine needs to be updated). In this contrived example, we call this pair twice before modifying the global variable to show what happens when you remain in a state for multiple frames.

Here's the output from running the program:

HSM_1_TestHsm: Init    : struct MyStates::First
First::Update
First::Update
HSM_1_TestHsm: Sibling : struct MyStates::Second
HSM_1_TestHsm: Sibling : struct MyStates::Third
Third::Update
Third::Update

While we're in state First, First::Update gets called each time we invoke stateMachine.UpdateStates. After modifying our global variable, the next call to stateMachine.ProcessStateTransitions causes First to sibling to Second, and Second to Third. As we're in state Third, Third::Update gets called twice for each call to stateMachine.UpdateStates. The important thing to note here is that Second::Update is never called because we never ended up in that state at the end of ProcessStateTransitions. If we really wanted Second to do something when we pass through it, we could use OnEnter.

Some more things to note about UpdateStates:

This feature is, in fact, not actually necessary. However, in games and real-time simulations, it turns out we often want some type of Update function on our current state, so it was added to HSM as a convenience.
It is often useful to pass certain arguments to Update functions, such as the frame delta time. The HSM provides macros that can be modified to define the parameters to StateMachine::UpdateStates and State::Update:
```
#define HSM_STATE_UPDATE_ARGS void
#define HSM_STATE_UPDATE_ARGS_FORWARD
```
By default, these functions take no arguments (void), but say you wanted to pass a float deltaTime parameter, you could modify the macros as follows:
```
#define HSM_STATE_UPDATE_ARGS float deltaTime
#define HSM_STATE_UPDATE_ARGS_FORWARD deltaTime
```
Now when invoking stateMachine.UpdateStates you would pass it a float parameter, and make sure to add 'float deltaTime' to the overrides of State::Update in your own states.

Ownership

Basic Usage

So far in our examples, we've created a single StateMachine instance directly in main, and have communicated with the states using global variables. In practice, a StateMachine would be a data member of a class - it's owner - and we'd want the states of that StateMachine to access members on this owner (its functions and data members).

Let's take a look at an example that is functionally equivalent to the one in the last section, except this time we've added an owner:

// ownership_basic_usage.cpp

#include <cstdio>
#include "hsm/statemachine.h"
using namespace hsm;

class MyOwner
{
public:
	MyOwner();
	void UpdateStateMachine();
	void PlaySequence();
	bool GetPlaySequence() const;

private:
	StateMachine mStateMachine;
	bool mPlaySequence;
};

struct MyStates
{
	struct First : State
	{
		virtual Transition GetTransition()
		{
			MyOwner* owner = reinterpret_cast<MyOwner*>(GetStateMachine().GetOwner());

			if (owner->GetPlaySequence())
				return SiblingTransition<Second>();

			return NoTransition();
		}

		virtual void Update()
		{
			printf("First::Update\n");
		}
	};

	struct Second : State
	{
		virtual Transition GetTransition()
		{
			MyOwner* owner = reinterpret_cast<MyOwner*>(GetStateMachine().GetOwner());

			if (owner->GetPlaySequence())
				return SiblingTransition<Third>();

			return NoTransition();
		}

		virtual void Update()
		{
			printf("Second::Update\n");
		}
	};

	struct Third : State
	{
		virtual Transition GetTransition()
		{
			return NoTransition();
		}

		virtual void Update()
		{
			printf("Third::Update\n");
		}
	};
};

MyOwner::MyOwner()
{
	mPlaySequence = false;
	mStateMachine.Initialize<MyStates::First>(this);
	mStateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
}

void MyOwner::UpdateStateMachine()
{
	mStateMachine.ProcessStateTransitions();
	mStateMachine.UpdateStates();
}

void MyOwner::PlaySequence()
{
	mPlaySequence = true;
}

bool MyOwner::GetPlaySequence() const
{
	return mPlaySequence;
}

int main()
{
	MyOwner myOwner;

	myOwner.UpdateStateMachine();
	myOwner.UpdateStateMachine();

	myOwner.PlaySequence();

	myOwner.UpdateStateMachine();
	myOwner.UpdateStateMachine();
}

The output is exactly the same as before:

HSM_1_TestHsm: Init    : struct MyStates::First
First::Update
First::Update
HSM_1_TestHsm: Sibling : struct MyStates::Second
HSM_1_TestHsm: Sibling : struct MyStates::Third
Third::Update
Third::Update

Alright, let's break down this example to better understand the changes. First, we've introduced a new class MyOwner:

class MyOwner
{
public:
	MyOwner();
	void UpdateStateMachine();
	void PlaySequence();
	bool GetPlaySequence() const;

private:
	StateMachine mStateMachine;
	bool mPlaySequence;
};

This class contains the StateMachine instance as a member named mStateMachine. We've also moved the gPlaySequence global to this class as data member mPlaySequence, which is set and read by member functions PlaySequence and GetPlaySequence:

void MyOwner::PlaySequence()
{
	mPlaySequence = true;
}

bool MyOwner::GetPlaySequence() const
{
	return mPlaySequence;
}

The constructor is where we initialize mPlaySequence as well as mStateMachine. The important difference here is that we now pass an argument to mStateMachine.Initialize: 'this':

MyOwner::MyOwner()
{
	mPlaySequence = false;
	mStateMachine.Initialize<MyStates::First>(this); //*** Note that we pass 'this' as our owner
	mStateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
}

The StateMachine::Initialize function accepts an optional pointer to the owner instance as it's first parameter. The pointer type is void*, so any type can be passed in here. Before we see how this owner pointer is used, let's take a look at UpdateStateMachine, which we'd call whenever the state machine needs to be updated (e.g. once per frame in a game):

void MyOwner::UpdateStateMachine()
{
	mStateMachine.ProcessStateTransitions();
	mStateMachine.UpdateStates();
}

In main, we create the MyOwner instance, and simulate four frame updates, making sure to set PlaySequence after two of them:

int main()
{
	MyOwner myOwner;

	myOwner.UpdateStateMachine();
	myOwner.UpdateStateMachine();

	myOwner.PlaySequence();

	myOwner.UpdateStateMachine();
	myOwner.UpdateStateMachine();
}

Now let's take a look at our states. Previously, states First and Second would read the value of global variable gPlaySequence in their GetTransition functions to determine whether to sibling to the next state. Now, these states access their owner via GetStateMachine().GetOwner():

	struct First : State
	{
		virtual Transition GetTransition()
		{
			MyOwner* owner = reinterpret_cast<MyOwner*>(GetStateMachine().GetOwner());

			if (owner->GetPlaySequence())
				return SiblingTransition<Second>();

			return NoTransition();
		}		
		<snip>
	}

Since GetStateMachine().GetOwner() returns the void* pointer we set earlier via StateMachine::Initialize, we need to cast it to MyOwner* so that we can call owner->GetPlaySequence(). In the next section, we'll see how to get rid of this casting.

Easier Owner Access

As we saw in the last example, we need to reinterpret_cast the void* owner pointer in state code like so:

	struct First : State
	{
		virtual Transition GetTransition()
		{
			MyOwner* owner = reinterpret_cast<MyOwner*>(GetStateMachine().GetOwner());

			if (owner->GetPlaySequence())
				return SiblingTransition<Second>();

			return NoTransition();
		}
	};

Accessing owners happens a lot in state code, so having to do this gets tedious fast. Thankfully, HSM offers a nice solution: derive your states from hsm::StateWithOwner<OwnerType> instead of from hsm::State. For example, state First would become:

	struct First : StateWithOwner<MyOwner>
	{
		virtual Transition GetTransition()
		{
			if (Owner().GetPlaySequence())
				return SiblingTransition<Second>();

			return NoTransition();
		}

		virtual void Update()
		{
			printf("First::Update\n");
		}
	};

Notice that First now derives from StateWithOwner<MyOwner>. This template class simply introduces a new function, Owner, that returns the specified owner type by reference: MyOwner& in this case. This simplifies the GetTransition code as it can now just call Owner() and access it's public members directly. We'll see in the next section how to access the Owner's private members as well.

Although deriving each state class from StateWithOwner<> works, we recommend creating a new base class that derives from StateWithOwner<>, and having each state derive from that class. This not only makes the code a little less verbose, but having a base class for your states is useful for adding shared functionality. Here's the full example using a base state class:

// ownership_easier_owner_access.cpp

#include <cstdio>
#include "hsm/statemachine.h"
using namespace hsm;

class MyOwner
{
public:
	MyOwner();
	void UpdateStateMachine();
	void PlaySequence();
	bool GetPlaySequence() const;

private:
	StateMachine mStateMachine;
	bool mPlaySequence;
};

struct MyStates
{
	struct BaseState : StateWithOwner<MyOwner>
	{
	};

	struct First : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().GetPlaySequence())
				return SiblingTransition<Second>();

			return NoTransition();
		}

		virtual void Update()
		{
			printf("First::Update\n");
		}
	};

	struct Second : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().GetPlaySequence())
				return SiblingTransition<Third>();

			return NoTransition();
		}

		virtual void Update()
		{
			printf("Second::Update\n");
		}
	};

	struct Third : BaseState
	{
		virtual Transition GetTransition()
		{
			return NoTransition();
		}

		virtual void Update()
		{
			printf("Third::Update\n");
		}
	};
};

MyOwner::MyOwner()
{
	mPlaySequence = false;
	mStateMachine.Initialize<MyStates::First>(this);
	mStateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
}

void MyOwner::UpdateStateMachine()
{
	mStateMachine.ProcessStateTransitions();
	mStateMachine.UpdateStates();
}

void MyOwner::PlaySequence()
{
	mPlaySequence = true;
}

bool MyOwner::GetPlaySequence() const
{
	return mPlaySequence;
}

int main()
{
	MyOwner myOwner;

	myOwner.UpdateStateMachine();
	myOwner.UpdateStateMachine();

	myOwner.PlaySequence();

	myOwner.UpdateStateMachine();
	myOwner.UpdateStateMachine();
}

Accessing Owner's Private Members

So far, we've seen how states can access their owner quite easily; however, because the owner is an unrelated class, states can only access its public members. This type of encapsulation is usually a good thing; however, in the case of state machines, the logic in states are often highly coupled with the data and functions in the owner class. Indeed, without using HSM, the state machine logic would usually be written directly in the owner class's member functions, thus having full access to its private members.

How can we make our states gain private access to the owner's private members? There are a few different ways:

Make each state a friend of the owner class. The problem with this approach is that every time a state is added/renamed/deleted, you need to modify the owner's class declaration.
Make the base state class - StateBase in the previous example - a friend of the owner class, and write forwarding functions in the base state class that accesses the private members of the owner. The derived states then use these forwarding functions. The advantage of this approach is that you don't need to modify the owner's class declaration when states are added/renamed/deleted. On the other hand, you may often need to add new forwarding functions to the base state class, introducing a lot of redundancy.

It would be great if states could just access their owner's privates directly without any fuss. Well, it turns out we can do this. As you may recall, we decided to nest all our states within a struct - MyStates in our examples so far - to avoid worrying about the order in which states are declared. Well, if we declare this struct a friend of the owner, then all states within the struct will be able to access the private members of the owner! This works because in C++, member access is inherited by nested types.

Here's our previous example modified to use this technique:

// ownership_access_owner_privates.cpp

#include <cstdio>
#include "hsm/statemachine.h"
using namespace hsm;

class MyOwner
{
public:
	MyOwner();
	void UpdateStateMachine();

	void PlaySequence();

private:
	friend struct MyStates; //*** All states can access MyOwner's private members

	StateMachine mStateMachine;
	bool mPlaySequence;
};

struct MyStates
{
	struct BaseState : StateWithOwner<MyOwner>
	{
	};

	struct First : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().mPlaySequence) //*** Access one of owner's private members
				return SiblingTransition<Second>();

			return NoTransition();
		}

		virtual void Update()
		{
			printf("First::Update\n");
		}
	};

	struct Second : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().mPlaySequence) //*** Access one of owner's private members
				return SiblingTransition<Third>();

			return NoTransition();
		}

		virtual void Update()
		{
			printf("Second::Update\n");
		}
	};

	struct Third : BaseState
	{
		virtual Transition GetTransition()
		{
			return NoTransition();
		}

		virtual void Update()
		{
			printf("Third::Update\n");
		}
	};
};

MyOwner::MyOwner()
{
	mPlaySequence = false;
	mStateMachine.Initialize<MyStates::First>(this);
	mStateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
}

void MyOwner::UpdateStateMachine()
{
	mStateMachine.ProcessStateTransitions();
	mStateMachine.UpdateStates();
}

void MyOwner::PlaySequence()
{
	mPlaySequence = true;
}

int main()
{
	MyOwner myOwner;

	myOwner.UpdateStateMachine();
	myOwner.UpdateStateMachine();

	myOwner.PlaySequence();

	myOwner.UpdateStateMachine();
	myOwner.UpdateStateMachine();
}

The main differences are:

We've added the friend declaration to MyOwner:

friend struct MyStates; //*** All states can access MyOwner's private members

The public Owner::GetPlaySequence function has been removed since our states can now read the private mPlaySequence member directly, so the code in states First and Second looks like:

			if (Owner().mPlaySequence) //*** Access one of owner's private members
				return SiblingTransition<Third>();

Storing Data

So far, we've seen how states can access data stored on their owner instance. This is perfect for any data that must persist across state changes. You can also store data on a state directly - after all, it's just a class. Naturally, data members of a state will be created when the state is entered, and destroyed when the state is exited.

This example shows how we can store data on a state, and how its lifetime is managed:

// storing_data.cpp

#include <cstdio>
#include <string>
#include "hsm/statemachine.h"
using namespace hsm;

class MyOwner
{
public:
	MyOwner();
	void UpdateStateMachine();

private:
	friend struct MyStates; //*** All states can access MyOwner's private members
	StateMachine mStateMachine;
};

struct Foo
{
	Foo() { printf(">>> Foo created\n"); }
	~Foo() { printf(">>>Foo destroyed\n"); }
};

struct MyStates
{
	struct BaseState : StateWithOwner<MyOwner>
	{
	};

	struct First : BaseState
	{
		virtual Transition GetTransition()
		{
			return SiblingTransition<Second>();
		}

		Foo mFoo; //*** State data member
	};

	struct Second : BaseState
	{
		virtual Transition GetTransition()
		{
			return NoTransition();
		}
	};
};

MyOwner::MyOwner()
{
	mStateMachine.Initialize<MyStates::First>(this);
	mStateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
}

void MyOwner::UpdateStateMachine()
{
	mStateMachine.ProcessStateTransitions();
	mStateMachine.UpdateStates();
}

int main()
{
	MyOwner myOwner;
	myOwner.UpdateStateMachine();
}

We've added a simple class Foo that prints when it's created and destroyed, and have added an instance of Foo to state First. Here's the output from the program:

>>> Foo created
HSM_1_TestHsm: Init    : struct MyStates::First
>>>Foo destroyed
HSM_1_TestHsm: Sibling : struct MyStates::Second

We can see that the Foo instance in First gets created when entering First, and destroyed when sibling from First to Second.

When it comes to storing data for your state machine, you should try to reduce its scope to where its needed. If you only need data on one state, make it data members of that state. If it needs to be accessed by all (or most) states, it makes sense to store it on the owner. What about scoping data to a subset of states? This will be covered in the next chapter when we introduce the concept of hierarchical state machines.

Chapter 3. The H in HSM

Introduction

In the last chapter, we learned how to use HSM to author flat state machines. Although HSM is perfectly suited to creating flat state machines, it's main feature is its built-in support for hierarchical state machines. In this chapter, we'll learn what is a hierarchical state machine, and how to author them with HSM.

Why Use Hierarchical State Machines?

The best way to understand why a hierarchical state machine is useful is with an example. Our example will be that of a typical state machine we'd build for a character controller in a video game. We first start out with a simple, flat state machine, much like the ones we saw in Chapter 2:

fsm-1

We have 3 states with certain transitions between them. Both Stand and Move can transition between each other, based on speed, and if the character's health drops to 0, in either state we make sure to go to Dead. Now let's add a few more states and transitions:

fsm-2

We've added 3 new states: Jump, Crouch, and Shoot. Although it looks like a big mess of arrows, if you look carefully, you will see that the transitions make sense: you can Jump, Crouch, or Shoot from both Stand and Move, and from all states, you must be able to go to Dead.

Now the fact that this looks like a big mess on a picture is not just because it's on a picture - this type of mess translates into code as well. If you've ever had to write a flat state machine in code that had more than just a few states, and many possible transitions, you've quickly learned how difficult it can be to manage. Indeed, it is very common for bugs to creep up at the 11th hour because you forgot a transition to a state from one that you never thought would require it.

The truth is, the complexity of a flat state machine is often exponentially proportional to the number of states it contains. When you add a new state, the number of transitions that need to be added increase as the state machine itself grows. For example, if we were to add a Hurt state to the above state machine, we'd need to add a transition to Hurt from all states except Dead.

The problem with flat state machines is that all states are treated as independent units: you can only be in one state at time. However, often it would make sense to be in more than one state at the same time. For example, let's say we introduce the state Alive to represent the opposite of Dead. Alive would transition to dead as long as health <= 0. Now logically, it makes sense to say that as long as you're in any of the states except for Dead in our example above, you should also be in Alive. Indeed, when you're standing, moving, crouching, and shooting, you're still alive, right?

Here's an example of what such a state machine could look like:

hsm-1

As you can see, most states have been grouped into the new Alive state, which is now the only one that transitions to the Dead state. This is exactly what a hierarchical state machine is: it provides a way of nesting states within other states.

Here's another version of this HSM with some more state nesting:

hsm-2

In this version, we've grouped Stand, Move, and Crouch into a Locomotion state, which is itself an inner state of Alive. Not only has the number of transitions greatly reduced, it's much easier to understand the state machine. For instance, we can see that whether you're standing, crouching, or moving, you can start shooting, but you can't shoot while jumping. Thus, by making our flat state machine a hierarchical one, we can more easily infer the rules of our character controller.

Hopefully by now you can see how useful hierarchical state machines can be. The rest of this chapter will delve into how to use HSM to implement these types of state machines.

Drawing HSMs

The images in the previous section displayed state nesting as concentric circles. Although this is useful for understanding the concept of hierarchical state machines, it's not practical to draw them this way for larger state machines with many levels of nesting. The rest of this book uses the output from plotHsm, which takes a different approach to representing state hierarchies. For instance, this state machine:

hsm-2

... looks like this using plotHsm:

drawing_hsms

Here are some tips for understanding this output:

The number in parentheses is the depth level of the state
State colors are brighter for more deeply nested states
Solid lines represent inner transitions (from an outer state to an inner state)
Dotted lines represent sibling transitions

Finally, plotHsm will group states together into clusters based on the state name: if a set of states share the same prefix followed by an underscore in their name, they will be grouped together. For instance:

drawing_hsms_clusters

Because we've prefixed the state names for Crouch, Move, and Stand with "Locomotion_", plotHsm clusters the states into a box labelled "Locomotion". This can be especially useful in understanding larger state machines where you'll typically have many state clusters at the same depth level. Of course, it can be cumbersome to prefix all your state names this way, so we recommend doing it to group the deepest, or innermost, set of states.

Inner and Outer States

When talking (or writing) about hierarchical state machines, the terms parent and child will often be used when describing the relationship between a state and its nested state. In HSM, we use the terms outer and inner instead. We do this to avoid confusion with the fact that states are actually C++ polymorphic classes, so a parent/child relationship already exists at the class hierarchy level (e.g. every state is a child class of hsm::State).

There are a few other terms we use to describe the relationships between states along with outer and inner: sibling, immediate, and root. The best way to define these is with an example:

drawing_hsms

We can describe the state relationships in the state machine above as follows:

Shoot, Locomotion, Jump, Crouch, Move, and Stand are inner states of Alive
Shoot, Locomotion, and Jump are inner states of Alive
Shoot, Locomotion, and Jump are also immediate inner states of Alive
Crouch, Move, and Stand are immediate inner states of Locomotion
Alive is the outer state of Shoot, Locomotion, Jump, Crouch, Move, and Stand
Alive is the immediate outer state of Shoot, Locomotion, and Jump
Dead is not an outer state
Alive and Dead are root states of the state machine
Alive and Dead are sibling states
Shoot, Locomotion, Jump are sibling states
Crouch, Move, and Stand are sibling states
If you're in the Move state, you're also in the Locomotion state and the Alive state
If you're in the Shoot state, you're also in the Alive state

This is the terminology that is used throughout this book as well as in the HSM code.

The State Stack

Before we look at how to author hierarchical state machines, we must first discuss one of the key features of how HSM manages states: the state stack.

Each StateMachine instance manages a stack of States instances. The first state pushed onto the stack is the outermost state, the next state pushed is its inner, and the last state pushed is the innermost state. A sibling transition will first pop the current state from the stack, and then push the target state back onto the stack, thus keeping it at the same depth. Inner and inner entry transitions, which we'll cover in the next few sections, are used to push inner states onto the stack. Every time a state is pushed onto the stack, it's OnEnter gets called.

When a source state makes a sibling transition to a target state, the source state and its inners are all popped off the stack before the target state is pushed. This happens from innermost up to the source state, with OnExit being called on each state, giving each state a chance to clean itself up.

Let's take the example from the previous section. After running ProcessStateTransitions, the state stack might look like this:

State Stack
Alive
Locomotion
Stand

If the player presses the movement input, the next call to ProcessStateTransitions would result in this state stack:

State Stack
Alive
Locomotion
Move

In this case, Stand made a sibling transition to Move, resulting in Stand::OnExit (pop) followed by Move::OnEnter (push). Now, if the character is killed, the next call to ProcessStateTransitions would result in this state stack:

State Stack
Dead

This time, Alive made a sibling transition to Dead, resulting in Move::OnExit (pop), Locomotion::OnExit (pop), Alive::OnExit (pop), and finally Dead::OnEnter (push).

In the next couple of sections, we'll learn about the two types of transitions used to push inner states.

InnerEntry Transitions

So far, the only type of transition we have seen is the sibling transition, which is used to exit a state and enter another state. In this section, we introduce the inner entry transition, which is used to enter a new inner state. Let's start with some code:

// inner_entry_transition.cpp

#include "hsm/statemachine.h"

using namespace hsm;

class MyOwner
{
public:
	MyOwner();
	void UpdateStateMachine();

	void Die() { mDead = true; }

private:
	bool IsDead() const { return mDead; }
	bool PressedMove() const { return false; } // Stub

	bool mDead;

	friend struct MyStates;
	StateMachine mStateMachine;
};

struct MyStates
{
	struct BaseState : StateWithOwner<MyOwner>
	{
	};

	struct Alive : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().IsDead())
				return SiblingTransition<Dead>();

			return InnerEntryTransition<Locomotion>();
		}
	};

	struct Dead : BaseState
	{
		virtual Transition GetTransition()
		{
			return NoTransition();
		}
	};

	struct Locomotion : BaseState
	{
		virtual Transition GetTransition()
		{
			return InnerEntryTransition<Stand>();
		}
	};

	struct Stand : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().PressedMove())
				return SiblingTransition<Move>();

			return NoTransition();
		}
	};

	struct Move : BaseState
	{
		virtual Transition GetTransition()
		{
			if (!Owner().PressedMove())
				return SiblingTransition<Stand>();

			return NoTransition();
		}
	};
};

MyOwner::MyOwner()
	: mDead(false)
{
	mStateMachine.Initialize<MyStates::Alive>(this);
	mStateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
}

void MyOwner::UpdateStateMachine()
{
	mStateMachine.ProcessStateTransitions();
	mStateMachine.UpdateStates();
}

int main()
{
	MyOwner myOwner;
	myOwner.UpdateStateMachine();
	myOwner.Die();
	myOwner.UpdateStateMachine();
}

Before we talk about the code, let's take a look at the plotHsm output for this state machine:

inner_entry_transition

Looking at this image, we can see that Alive and Dead are siblings, and that Move and Stand are also siblings. Locomotion, however, is an inner state of Alive, and both Move and Stand are inner states of Locomotion.

Now notice that although both Stand and Move are inner states of Locomotion, there is only one arrow going from Locomotion to Stand, but none from Locomotion to Move. The reason for this is that Locomotion makes an inner entry transition to Stand. We can see this when looking at the code for state Locomotion:

	struct Locomotion : BaseState
	{
		virtual Transition GetTransition()
		{
			return InnerEntryTransition<Stand>();
		}
	};

When a state returns an InnerEntryTransition<TargetState>, the state machine will enter TargetState if no other inner state has been entered yet.

In other words, if a state at depth D on the state stack returns InnerEntryTransition<TargetState>, as long as there is no state yet at depth D+1, TargetState will be created and pushed onto the stack. The next time the same state returns InnerEntryTransition<TargetState>, because an inner state has already been pushed, this transition will be ignored.

Back to our example, Locomotion will always return InnerEntryTransition<Stand>() from its GetTransition function; but the inner transition will only happen the first time it's returned, at which point Stand will be created as an inner state. Now Stand is free to make sibling transitions:

	struct Stand : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().PressedMove())
				return SiblingTransition<Move>();

			return NoTransition();
		}
	};

We can see that if the user presses the move input, Stand will sibling to Move. When this occurs, Move will be the current inner state of Locomotion. Note that even though Locomotion::GetTransition will continue to return InnerEntryTransition<Stand>(), this will have no effect; Move will remain its current inner state.

Inners and Trace Output

As usual, we've set up the state machine to output basic level tracing:

	mStateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);

Which produces this output:

HSM_1_TestHsm: Init    : struct MyStates::Alive
HSM_1_TestHsm:  Entry   : struct MyStates::Locomotion
HSM_1_TestHsm:   Entry   : struct MyStates::Stand
HSM_1_TestHsm: Sibling : struct MyStates::Dead

The first thing to note is that the output is indented with respect to the state depth on the stack. We can clearly see that Alive made an inner entry transition to Locomotion, and Locomotion also made an inner entry to Stand. Finally, we see that there was a sibling transition to Dead, and since it's indentation level matches that of Alive, we know that Alive must have made that transition.

The Alive to Dead sibling transition implies that Stand, Locomotion, and Alive were all popped from the stack (and OnExit called on each). If you wish to see this explicitly, you can change the trace level from Basic to Diagnostic as follows:

	mStateMachine.SetDebugInfo("TestHsm", TraceLevel::Diagnostic);

Now the output becomes:

HSM_1_TestHsm: Init    : struct MyStates::Alive
HSM_1_TestHsm:  Entry   : struct MyStates::Locomotion
HSM_1_TestHsm:   Entry   : struct MyStates::Stand
HSM_2_TestHsm:   Pop     : struct MyStates::Stand
HSM_2_TestHsm:  Pop     : struct MyStates::Locomotion
HSM_2_TestHsm: Pop     : struct MyStates::Alive
HSM_1_TestHsm: Sibling : struct MyStates::Dead

We now see three new "Pop" lines for Stand, Locomotion, and Alive. Although this is useful for understanding how the HSM works, once you're used to it, you can easily infer when states are popped, which is why these lines are not part of the Basic trace output.

Inner Transitions

In the previous section, we covered the InnerEntryTransition, which is used to push an inner state only if there is no inner state yet on the stack. The more generalized InnerTransition, on the other hand, is used to force an inner state onto the state stack, regardless of what's on it.

More specifically: when InnerTransition<TargetState> is returned from GetTransition, the state machine makes sure that TargetState becomes (or remains) the inner state. If there is no inner state yet, TargetState gets pushed. If the inner state is already TargetState, nothing happens. If the inner state is not TargetState, the current inner state - along with all its inners - are popped off the stack (from innermost out), and TargetState is then pushed.

Let's take a look at an example:

// inner_transition.cpp

#include "hsm/statemachine.h"

using namespace hsm;

class MyOwner
{
public:
	MyOwner();
	void UpdateStateMachine();

	void Die() { mDead = true; }
	void SetMove(bool enable) { mMove = enable; }

private:
	bool IsDead() const { return mDead; }
	bool PressedMove() const { return mMove; }

	bool mDead;
	bool mMove;

	friend struct MyStates;
	StateMachine mStateMachine;
};

struct MyStates
{
	struct BaseState : StateWithOwner<MyOwner>
	{
	};

	struct Alive : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().IsDead())
				return SiblingTransition<Dead>();

			return InnerEntryTransition<Locomotion>();
		}
	};

	struct Dead : BaseState
	{
		virtual Transition GetTransition()
		{
			return NoTransition();
		}
	};

	struct Locomotion : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().PressedMove())
				return InnerTransition<Move>();
			else
				return InnerTransition<Stand>();
		}
	};

	struct Stand : BaseState
	{
	};

	struct Move : BaseState
	{
	};
};

MyOwner::MyOwner()
	: mDead(false)
	, mMove(false)
{
	mStateMachine.Initialize<MyStates::Alive>(this);
	mStateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
}

void MyOwner::UpdateStateMachine()
{
	mStateMachine.ProcessStateTransitions();
	mStateMachine.UpdateStates();
}

int main()
{
	MyOwner myOwner;
	myOwner.UpdateStateMachine();
	
	printf("Set Move = true\n");
	myOwner.SetMove(true);
	myOwner.UpdateStateMachine();
	
	printf("Set Move = false\n");
	myOwner.SetMove(false);
	myOwner.UpdateStateMachine();
}

This example is the same as the one from the InnerEntryTransition section, except we've modified how the Stand and Move states are transitioned to. In the previous section, Locomotion made an InnerEntryTransition to Stand, and then Stand and Move would sibling to each other based on the result of Owner().PressedMove():

	struct Locomotion : BaseState
	{
		virtual Transition GetTransition()
		{
			return InnerEntryTransition<Stand>();
		}
	};

	struct Stand : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().PressedMove())
				return SiblingTransition<Move>();

			return NoTransition();
		}
	};

	struct Move : BaseState
	{
		virtual Transition GetTransition()
		{
			if (!Owner().PressedMove())
				return SiblingTransition<Stand>();

			return NoTransition();
		}
	};

In the current example, Locomotion uses InnerTransition to select which inner state will be pushed on the stack:

	struct Locomotion : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().PressedMove())
				return InnerTransition<Move>();
			else
				return InnerTransition<Stand>();
		}
	};

	struct Stand : BaseState
	{
	};

	struct Move : BaseState
	{
	};

The main difference is that Locomotion decides whether Stand or Move should be the current inner state by using InnerTransition. Formerly, Locomotion only decided which of these states to start in - Stand in our case - by returning an InnerEntryTransition to that state; afterwards, Stand and Move used SiblingTransitions to decide which state should be the current inner of Locomotion.

In main, we toggle the 'move' variable to see these inner transitions in action:

int main()
{
	MyOwner myOwner;
	myOwner.UpdateStateMachine();
	
	printf("Set Move = true\n");
	myOwner.SetMove(true);
	myOwner.UpdateStateMachine();
	
	printf("Set Move = false\n");
	myOwner.SetMove(false);
	myOwner.UpdateStateMachine();
}

This produces the following output:

HSM_1_TestHsm: Init    : struct MyStates::Alive
HSM_1_TestHsm:  Entry   : struct MyStates::Locomotion
HSM_1_TestHsm:   Inner   : struct MyStates::Stand
Set Move = true
HSM_1_TestHsm:   Inner   : struct MyStates::Move
Set Move = false
HSM_1_TestHsm:   Inner   : struct MyStates::Stand

We can see from this output that Locomotion first makes an InnerTransition to Stand, then after we set the move field to true, Locomotion "inners" to Move, and finally after resetting the move field, Locomotion inners back to Stand.

The plotHsm output for this example is a little different from the last one:

inner_transition.cpp.dot.png

There are now two arrows indicating InnerTransitions from Locomotion to Move and Stand. Note that the InnerEntryTransition arrow from Alive to Locomotion is thicker than the InnerTransition arrows from Locomotion to Move and Stand.

State Stack Queries

When implementing state machines, there are many instances in which you need to query the current state stack. In this section, we'll take a look at the functions HSM provides for this purpose.

The most basic query is "are we in a given state?". For this, use StateMachine::IsInState<StateType>, which returns true if StateType is anywhere on the state stack. For instance, given the following state stack:

State Stack
Alive
Locomotion
Stand

Then mStateMachine.IsInState<Alive>();, mStateMachine.IsInState<Locomotion>(), and mStateMachine.IsInState<Stand>() would all return true, but mStateMachine.IsInState<Move>() would return false.

Another useful query function is StateMachine::GetState<StateType>, which returns a pointer to StateType if StateType is found on the stack, otherwise it returns NULL. This allows you to both check if you are in a given state and access members on that state, which means you can keep state-specific functions and data scoped to the state itself.

That covers the query functions available on the StateMachine class, but there are more available from the State class that can be used from within states (typically from GetTransition):

State::GetState<StateType> simply forwards to the same functions on the StateMachine class. This function can be useful when a state is interested in knowing whether a specific state is anywhere on the stack. However, the functions described below narrow the search direction, and are typically more useful and optimal.
State::GetOuterState<StateType> is similar to GetState except it searches the state stack starting from the current state's immediate outer to the outermost. This function is typically used when inner states need to access members from a common outer state.
State::GetInnerState<StateType> is similar to GetState except it searches the state stack from the current state's immediate inner to the innermost. This function is typically used when a state needs to make a sibling transition based on the existence of an inner state on the stack.
State::GetImmediateInnerState<StateType> is similar to GetInnerState, except it only checks for the existence of StateType at the current state's depth + 1 on the stack. This is useful when you know the target state is an immediate inner, and is mostly an optimization over GetInnerState as it doesn't search all inners.

Finally, State provides analogues to the above functions that check for the existence of a state: IsInState, IsInOuterState, IsInInnerState, and IsInImmediateInnerState.

We will see these state stack query functions in action in future examples.

ProcessStateTransitions Revisited

In Chapter 2, we covered the basics of the StateMachine::ProcessStateTransitions function, but only to the extent of how it behaves with non-hierarchical (flat) state machines. In this section, we present the complete algorithm that takes into account the state stack, as well as InnerEntry and Inner transitions.

Note that this is perhaps the most important section in this book as it details the execution model of HSM. To build effective state machines, it is important to understand how states are created/destroyed, and how transitions are processed.

Algorithm

In Chapter 2, we presented the following pseudo-code to explain how StateMachine::ProcessStateTransitions works:

done = false
while (!done)
	transition = currState.GetTransition()
	if (transition != NoTransition)
		currState.OnExit()
		currState = transition.GetTargetState()
		currState.OnEnter()
	else
		done = true

This pseudo-code was enough to understand how HSM processes non-hierarchical (flat) state machines. We now expand this code to see how it handles hierarchical state machines:

function ProcessStateTransitions
{
	if stateStack.IsEmpty()
		CreateAndPushInitialState()
		
	bool stackModified = true
	
	while (stackModified)
	{
		stackModified = ProcessStateTransitionsOnce()
	} 
}

function ProcessStateTransitionsOnce
{
	for (depth = 0; depth < stateStack.size(); ++depth)
	{
		State* currState = GetStateAtDepth(depth)
		Transition transition = currState->GetTransition()

		if transition.Type() == NoTransition
		{
			continue // Move to next inner
		}
		
		else if transition.Type() == Inner
		{
			if transition.TargetState() == GetStateAtDepth(depth + 1)
			{
				continue // Inner is already target state, move to next inner
			}
			else
			{
				// Pop all states under us and push target
				PopStatesToDepth(depth + 1) // Invokes OnExit on each state, then pops
				PushState(CreateState(transition.TargetState())) // Pushes to stack, then calls OnEnter
				
				return true // State stack was modified
			}
		}
		
		else if transition.Type() == InnerEntry
		{
			// If current state has no inner (is currently the innermost), then push the entry state
			if GetStateAtDepth(depth + 1) == NULL
			{
				State* targetState = CreateState(transition.TargetState())
				PushState(targetState) // Pushes to stack, then calls OnEnter
				
				return true // State stack was modified
			}
		}
		
		else if transition.Type() == Sibling
		{
			// Pop all states under and including current, then push target state		
			PopStatesToDepth(depth)
			State* targetState = CreateState(transition)
			PushState(targetState) // Pushes to stack, then calls OnEnter
			
			return true // State stack was modified
		}
	}
	
	return false // State stack was not modified
}

This version of ProcessStateTransitions is certainly longer than the one we presented in Chapter 2. However, it should be fairly straightforward, and it's the same code you'll find in the StateMachine implementation, only simplified to help focus on the important parts.

The first thing you'll probably notice is that the process is broken down into two functions. We'll begin by focusing on ProcessStateTransitionsOnce. This function's role is to process each state on the stack from outermost (at depth 0) to innermost, invoking GetTransition on each state, and as soon as a state returns a transition that would modify the state stack, it performs the transition and returns true to signal that a modification was made. If no state returns a transition that would modify the current state stack, the function returns false to signal that no modification was made.

For each transition type, we can see how the state stack is manipulated. There should be no surprises here; how the stack is manipulated corresponds to how each transition was defined earlier in this chapter. Note that Sibling transitions always modify the state stack, while InnerEntry transitions only modify the stack if there's no inner state yet, and Inner transitions only modify the stack when the current inner state is not already the target state.

Now keeping in mind that ProcessStateTransitionsOnce returns whether or not the state stack was modified, ProcessStateTransition simply calls ProcessStateTransitionsOnce in a loop until the latter returns false. Effectively, ProcessStateTransition's role is to keep processing state transitions on the stack from outermost to innermost (via ProcessStateTransitionsOnce) until there are no more transitions that modify the stack. When this happens, we say that the state stack has settled.

Rationale

Let's talk about the rationale behind some of the decisions in the ProcessStateTransition algorithm.

First, why does ProcessStateTransition need to keep iterating over the state stack until the stack has settled? Why not simply run through the stack once by just calling ProcessStateTransitionOnce one time? The main reason is idempotence: all things being equal, if you call StateMachine::ProcessStateTransitions twice, the second call should effectively be a "no-op" (i.e. should not modify the state stack).

To understand why this is important, let's say in a game, an enemy deals damage to the player, dropping his health value to 0. Depending on how the state machine was designed, it is possible that it would need to process its transitions from outer to inner more than once to get itself into the Dead state. If we did not make sure to keep processing transitions until the state stack is settled, then for one or more frames, the player would have a health value of 0, but would not be in the Dead state. This type of inconsistency usually results in bugs that are difficult to understand. In effect, what we want is a 1:1 mapping between external data and the state stack: if health is 0, we should be in the Dead state after calling ProcessStateTransitions.

NOTE: The fact that ProcessStateTransitions works this way is also useful in that it allows for transitions to so-called "transient" states: a state that will never exist on the stack once it has settled. A typical example is a "done" state, which is covered in Chapter 4

Another question that is often asked about the ProcessStateTransition algorithm is: why are transitions processed from outer to inner, rather than from inner to outer? The reason has to do with how a hierarchical state machine is typically organized: an outer state represents a more global state, while an inner states represent a more local state. Outer states make "bigger" - or more important - decisions than inner states, so they are processed first - they have priority. For instance, in most of our examples in this chapter, Alive is an outermost state, and no matter what inner states are currently on the stack, Alive will always sibling to Dead if health drops to 0. This transition is a high-priority transition, and thus is processed before inner transitions.

Implications

Let's discuss some of the important implications of how the ProcessStateTransitions algorithm keeps processing transitions until the state stack has settled.

First of all, keep in mind that State::GetTransition can be called more than once on any given state during a single call to StateMachine::ProcessStateTransitions. As a result, GetTransition is not a good place to execute "update" logic - for that, use the State::Update function instead, which is guaranteed to only get called once on each state. GetTransition should really only return what transition to make by reading/polling state data. In other words, GetTransition should generally have no side-effects apart from returning a transition that modifies the state stack.

Secondly, it's possible for ProcessStateTransitions to end up in an infinite transition loop - one where the state stack never settles. A simple example is one where state A siblings to B if boolean variable foo is true, and B siblings to A is foo is false. Fortunately, infinite transition loops like these are detected and reported by HSM via an assertion, and with the help of the trace output, are usually easy enough to understand and correct. (See the section on Deferred Transitions for one way to break such infinite transition loops).

UpdateStates Revisited

In Chapter 2, we learned that StateMachine::UpdateStates can be used to invoke State::Update on the current state in a flat state machine. More generally, what StateMachine::UpdateStates actually does is invoke State::Update on each state on the state stack from outermost to innermost.

Let's take a look at an example of how UpdateStates works:

// revisit_update_states.cpp

#include "hsm/statemachine.h"

using namespace hsm;

class MyOwner
{
public:
	MyOwner();
	void UpdateStateMachine();

private:
	friend struct MyStates;
	StateMachine mStateMachine;
};

struct MyStates
{
	struct BaseState : StateWithOwner<MyOwner>
	{
	};
	
	struct A : BaseState
	{
		virtual Transition GetTransition()
		{
			return InnerEntryTransition<B>();
		}

		virtual void Update()
		{
			printf("A::Update\n");
		}
	};

	struct B : BaseState
	{
		virtual Transition GetTransition()
		{
			return InnerEntryTransition<C>();
		}

		virtual void Update()
		{
			printf("B::Update\n");
		}
	};

	struct C : BaseState
	{
		virtual Transition GetTransition()
		{
			return InnerEntryTransition<D>();
		}

		virtual void Update()
		{
			printf("C::Update\n");
		}
	};

	struct D : BaseState
	{
		virtual void Update()
		{
			printf("D::Update\n");
		}
	};
};

MyOwner::MyOwner()
{
	mStateMachine.Initialize<MyStates::A>(this);
	mStateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
}

void MyOwner::UpdateStateMachine()
{
	mStateMachine.ProcessStateTransitions();
	mStateMachine.UpdateStates();
}

int main()
{
	MyOwner myOwner;
	myOwner.UpdateStateMachine();
}

Here's the output from this example:

HSM_1_TestHsm: Init    : struct MyStates::A
HSM_1_TestHsm:  Entry   : struct MyStates::B
HSM_1_TestHsm:   Entry   : struct MyStates::C
HSM_1_TestHsm:    Entry   : struct MyStates::D
A::Update
B::Update
C::Update
D::Update

From this output, we can clearly see that Update gets called from outermost to innermost.

The State::Update function is where a state should perform whatever actions are relevant to that state. In the context of a hierarchical state machine, this allows you to encapsulate a state's behaviour where it belongs - in the state itself.

Also keep in mind that StateMachine::UpdateStates is invoked after StateMachine::ProcessStateTransitions, which means that State::Update is only called on states once the stack has settled. This means it's possible for certain states to never have State::Update called on them, even if transitioned to. For example, if A transitions to state B, and B immediately returns a sibling transition to state C, B::Update won't get called.

It's also worth noting that unlike State::Update, State::OnEnter and State::OnExit are always called on states that are transitioned to, so these are good functions to use if a state must always perform an action, regardless of whether they remain on the state stack at the end of StateMachine::ProcessTransitions.

Chapter 4. Advanced Techniques

Introduction

In the last chapter, we covered the basics of how to author a hierarchical state machine using HSM. In this chapter, we will take a look at some advanced techniques that will aid in making your state machines easier to manage, and more expressive.

StateValue

When working with hierarchical state machines, one common pattern that arises is setting a shared value in OnEnter, and restoring that same value in OnExit. In this section, we'll learn how to make use of a feature of HSM called StateValue to facilitate this common pattern.

Without StateValue

Before we look at how to use the StateValue feature, we'll start with an example that sets/unsets values in states directly. Once again, this code demonstrates a possible state machine for a character controller:

// state_value_without.cpp

#include "hsm/statemachine.h"

using namespace hsm;

class PhysicsComponent
{
public:
	void SetSpeed(float speed) {} // Stub
	void Move() {} // Stub
};

class Character
{
public:
	Character();
	void Update();

	// Public to simplify sample
	bool mInWater;
	bool mMove;
	bool mCrawl;

private:
	friend struct CharacterStates;
	StateMachine mStateMachine;

	PhysicsComponent mPhysicsComponent;
	float mSpeedScale; // [0,1]
};

struct CharacterStates
{
	struct BaseState : StateWithOwner<Character>
	{
	};

	struct Alive : BaseState
	{
		virtual Transition GetTransition()
		{
			return InnerEntryTransition<OnGround>();
		}
	};

	struct OnGround : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().mInWater)
				return SiblingTransition<Swim>();

			return InnerEntryTransition<Stand>();
		}
	};

	struct Stand : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().mMove)
				return SiblingTransition<Move>();

			return NoTransition();
		}
	};

	struct Move : BaseState
	{
		virtual Transition GetTransition()
		{
			if (!Owner().mMove)
				return SiblingTransition<Stand>();

			return InnerEntryTransition<Move_Walk>();
		}
	};

	struct Move_Walk : BaseState
	{
		float mLastSpeedScale;

		virtual void OnEnter()
		{
			mLastSpeedScale = Owner().mSpeedScale;
			Owner().mSpeedScale = 1.0f; // Full speed when moving normally
		}

		virtual void OnExit()
		{
			Owner().mSpeedScale = mLastSpeedScale;
		}

		virtual Transition GetTransition()
		{
			if (Owner().mCrawl)
				return SiblingTransition<Move_Crawl>();
			
			return NoTransition();
		}
	};

	struct Move_Crawl : BaseState
	{
		float mLastSpeedScale;

		virtual void OnEnter()
		{
			mLastSpeedScale = Owner().mSpeedScale;
			Owner().mSpeedScale = 0.5f; // Half speed when crawling
		}

		virtual void OnExit()
		{
			Owner().mSpeedScale = mLastSpeedScale;
		}

		virtual Transition GetTransition()
		{
			if (!Owner().mCrawl)
				return SiblingTransition<Move_Walk>();

			return NoTransition();
		}
	};

	struct Swim : BaseState
	{
		float mLastSpeedScale;

		virtual void OnEnter()
		{
			mLastSpeedScale = Owner().mSpeedScale;
			Owner().mSpeedScale = 0.3f; // ~1/3 speed when swimming
		}

		virtual void OnExit()
		{
			Owner().mSpeedScale = mLastSpeedScale;
		}

		virtual Transition GetTransition()
		{
			if (!Owner().mInWater)
				return SiblingTransition<OnGround>();

			return NoTransition();
		}
	};
};

Character::Character()
	: mInWater(false)
	, mMove(false)
	, mCrawl(false)
	, mSpeedScale(0.0f) // By default we don't move
{
	mStateMachine.Initialize<CharacterStates::Alive>(this);
	mStateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
}

void Character::Update()
{
	// Update state machine
	mStateMachine.ProcessStateTransitions();
	mStateMachine.UpdateStates();

	// Move character
	const float MAX_SPEED = 100.0f;
	float currSpeed = mSpeedScale * MAX_SPEED;
	mPhysicsComponent.SetSpeed(currSpeed);
	mPhysicsComponent.Move();

	printf("Current speed: %f\n", currSpeed);
}

int main()
{
	Character character;
	character.Update();

	character.mMove = true;
	character.Update();

	character.mCrawl = true;
	character.Update();

	character.mInWater = true;
	character.Update();

	character.mInWater = false;
	character.mMove = false;
	character.mCrawl = false;
	character.Update();
}

Before we talk about the code, let's take a look at the plotHsm output for this state machine:

state_value_without

Just from this plot, we can infer a few things about this character controller. We see the character can be either on the ground or swimming. While on ground, the character can stand or move, and while moving can be either walking or crawling.

In the example code, there is a class named PhysicsComponent that would be responsible for moving a physical representation of the character, handling collisions, etc. This class is stubbed out for simplicity. In Character::Update, we can see how the speed is computed and set on this PhysicsComponent before calling Move() on it:

void Character::Update()
{
	// Update state machine
	mStateMachine.ProcessStateTransitions();
	mStateMachine.UpdateStates();

	// Move character
	const float MAX_SPEED = 100.0f;
	float currSpeed = mSpeedScale * MAX_SPEED;
	mPhysicsComponent.SetSpeed(currSpeed);
	mPhysicsComponent.Move();

	printf("Current speed: %f\n", currSpeed);
}

The idea is that the character can move at a max speed of 100 units per second, and the data member mSpeedScale is used to scale the max speed based on the character's current state. By default, mSpeedScale is initialized to 0 in the constructor, so by default, the character does not move. In the three states where the character can move, we find similar code to save/set/restore mSpeedScale:

	struct Move_Walk : BaseState
	{
		float mLastSpeedScale;

		virtual void OnEnter()
		{
			mLastSpeedScale = Owner().mSpeedScale;
			Owner().mSpeedScale = 1.0f; // Full speed when moving normally
		}

		virtual void OnExit()
		{
			Owner().mSpeedScale = mLastSpeedScale;
		}
		<snip>
	};
		
	struct Move_Crawl : BaseState
	{
		float mLastSpeedScale;

		virtual void OnEnter()
		{
			mLastSpeedScale = Owner().mSpeedScale;
			Owner().mSpeedScale = 0.5f; // Half speed when crawling
		}

		virtual void OnExit()
		{
			Owner().mSpeedScale = mLastSpeedScale;
		}
		<snip>
	};
	
	struct Swim : BaseState
	{
		float mLastSpeedScale;

		virtual void OnEnter()
		{
			mLastSpeedScale = Owner().mSpeedScale;
			Owner().mSpeedScale = 0.3f; // ~1/3 speed when swimming
		}

		virtual void OnExit()
		{
			Owner().mSpeedScale = mLastSpeedScale;
		}
		
		<snip>
	};

In all three states, Move_Walk, Move_Crawl, and Swim, the following steps occur:

In OnEnter: save value of Owner().mSpeedScale into state data member mLastSpeedScale.
In OnEnter: set the value of Owner().mSpeedScale to a value that makes sense for that specific state.
In OnExit: as we exit the state, restore the value of Owner().mSpeedScale to what it was before the state was entered.

Now let's look at the output from this program:

HSM_1_TestHsm: Init    : struct CharacterStates::Alive
HSM_1_TestHsm:  Entry   : struct CharacterStates::OnGround
HSM_1_TestHsm:   Entry   : struct CharacterStates::Stand
Current speed: 0.000000
HSM_1_TestHsm:   Sibling : struct CharacterStates::Move
HSM_1_TestHsm:    Entry   : struct CharacterStates::Move_Walk
Current speed: 100.000000
HSM_1_TestHsm:    Sibling : struct CharacterStates::Move_Crawl
Current speed: 50.000000
HSM_1_TestHsm:  Sibling : struct CharacterStates::Swim
Current speed: 30.000002
HSM_1_TestHsm:  Sibling : struct CharacterStates::OnGround
HSM_1_TestHsm:   Entry   : struct CharacterStates::Stand
Current speed: 0.000000

From the output, we can see that the final speed is scaled appropriately depending on what state is on the state stack.

With StateValue

This method of saving/setting/restoring a shared variable in a state works; however, it is such a common paradigm that HSM offers a feature named StateValue to make easier. Let's take a look at the same example, but this time using StateValue:

// state_value_with.cpp

#include "hsm/statemachine.h"

using namespace hsm;

class PhysicsComponent
{
public:
	void SetSpeed(float speed) {} // Stub
	void Move() {} // Stub
};

class Character
{
public:
	Character();
	void Update();

	// Public to simplify sample
	bool mInWater;
	bool mMove;
	bool mCrawl;

private:
	friend struct CharacterStates;
	StateMachine mStateMachine;

	PhysicsComponent mPhysicsComponent;
	hsm::StateValue<float> mSpeedScale; // [0,1]
};

struct CharacterStates
{
	struct BaseState : StateWithOwner<Character>
	{
	};

	struct Alive : BaseState
	{
		virtual Transition GetTransition()
		{
			return InnerEntryTransition<OnGround>();
		}
	};

	struct OnGround : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().mInWater)
				return SiblingTransition<Swim>();

			return InnerEntryTransition<Stand>();
		}
	};

	struct Stand : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().mMove)
				return SiblingTransition<Move>();

			return NoTransition();
		}
	};

	struct Move : BaseState
	{
		virtual Transition GetTransition()
		{
			if (!Owner().mMove)
				return SiblingTransition<Stand>();

			return InnerEntryTransition<Move_Walk>();
		}
	};

	struct Move_Walk : BaseState
	{
		virtual void OnEnter()
		{
			SetStateValue(Owner().mSpeedScale) = 1.0f; // Full speed when moving normally
		}

		virtual Transition GetTransition()
		{
			if (Owner().mCrawl)
				return SiblingTransition<Move_Crawl>();
			
			return NoTransition();
		}
	};

	struct Move_Crawl : BaseState
	{
		virtual void OnEnter()
		{
			SetStateValue(Owner().mSpeedScale) = 0.5f; // Half speed when crawling
		}

		virtual Transition GetTransition()
		{
			if (!Owner().mCrawl)
				return SiblingTransition<Move_Walk>();

			return NoTransition();
		}
	};

	struct Swim : BaseState
	{
		virtual void OnEnter()
		{
			SetStateValue(Owner().mSpeedScale) = 0.3f; // ~1/3 speed when swimming
		}

		virtual Transition GetTransition()
		{
			if (!Owner().mInWater)
				return SiblingTransition<OnGround>();

			return NoTransition();
		}
	};
};

Character::Character()
	: mInWater(false)
	, mMove(false)
	, mCrawl(false)
	, mSpeedScale(0.0f) // By default we don't move
{
	mStateMachine.Initialize<CharacterStates::Alive>(this);
	mStateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
}

void Character::Update()
{
	// Update state machine
	mStateMachine.ProcessStateTransitions();
	mStateMachine.UpdateStates();

	// Move character
	const float MAX_SPEED = 100.0f;
	float currSpeed = mSpeedScale * MAX_SPEED;
	mPhysicsComponent.SetSpeed(currSpeed);
	mPhysicsComponent.Move();

	printf("Current speed: %f\n", currSpeed);
}

int main()
{
	Character character;
	character.Update();

	character.mMove = true;
	character.Update();

	character.mCrawl = true;
	character.Update();

	character.mInWater = true;
	character.Update();

	character.mInWater = false;
	character.mMove = false;
	character.mCrawl = false;
	character.Update();
}

The first difference to notice is that the former declaration 'float mSpeedScale;' has now become:

	hsm::StateValue<float> mSpeedScale; // [0,1]

Consequently, the three states that set mSpeedScale have also changed and have become much simpler:

	struct Move_Walk : BaseState
	{
		virtual void OnEnter()
		{
			SetStateValue(Owner().mSpeedScale) = 1.0f; // Full speed when moving normally
		}
		<snip>
	};

	struct Move_Crawl : BaseState
	{
		virtual void OnEnter()
		{
			SetStateValue(Owner().mSpeedScale) = 0.5f; // Half speed when crawling
		}
		<snip>
	};

	struct Swim : BaseState
	{
		virtual void OnEnter()
		{
			SetStateValue(Owner().mSpeedScale) = 0.3f; // ~1/3 speed when swimming
		}
		<snip>
	};

Notice how we no longer have a local data member in each state to save the original value, nor an OnExit to restore it. All we need to do is call SetStateValue(myStateValue) = newValue, and we're done.

The output from the program is the same as before:

HSM_1_TestHsm: Init    : struct CharacterStates::Alive
HSM_1_TestHsm:  Entry   : struct CharacterStates::OnGround
HSM_1_TestHsm:   Entry   : struct CharacterStates::Stand
Current speed: 0.000000
HSM_1_TestHsm:   Sibling : struct CharacterStates::Move
HSM_1_TestHsm:    Entry   : struct CharacterStates::Move_Walk
Current speed: 100.000000
HSM_1_TestHsm:    Sibling : struct CharacterStates::Move_Crawl
Current speed: 50.000000
HSM_1_TestHsm:  Sibling : struct CharacterStates::Swim
Current speed: 30.000002
HSM_1_TestHsm:  Sibling : struct CharacterStates::OnGround
HSM_1_TestHsm:   Entry   : struct CharacterStates::Stand
Current speed: 0.000000

How does it work?

The StateValue<T> template class is a light wrapper around any type T (float in our example) that provides read-only access to the value that's wrapped. The only way to modify the wrapped value is by invoking State::SetStateValue from within a state, which returns a modifiable reference to the wrapped value.

When you call SetStateValue in a state member function, the state saves a pointer to the wrapped variable as well as its original value when SetStateValue was called. When the state is destroyed, and after OnExit is called, the wrapped variable's value is restored to the value that was saved on the state.

Initializing StateValues

One important thing to note about StateValue is that you should initialize it with a default value via the StateValue constructor. In our example, as hsm::StateValue<float> mSpeedScale is a data member of the owner Character class, we initialize it in the constructor's initialization list:

Character::Character()
	: mInWater(false)
	, mMove(false)
	, mCrawl(false)
	, mSpeedScale(0.0f) // By default we don't move

Sometimes you will want to initialize a StateValue after the constructor is called; for instance, in a Reset function on the owner class. For this, you can use StateValue::SetInitialValue. Of course, this function essentially allows you to bypass the read-only access to the wrapped value, but you should never use it once the state machine has been updated, as this could invalidate values set by states.

Reading StateValues

Another thing to note about StateValue is that it provides an implicit cast to const T&, which means you can treat the variable as its wrapped type when reading it, as is done in the example:

	const float MAX_SPEED = 100.0f;
	float currSpeed = mSpeedScale * MAX_SPEED;

Here, the compiler implicitly casts mSpeedScale to const float& to multiply it with MAX_SPEED.

In certain cases, the compiler will not be able to implicitly cast to const T&, in which case you can either explicitly cast yourself (e.g. static_cast<float>(mSpeedScale)), or you can simply invoke the StateValue::Value function instead (e.g. mSpeedScale.Value()).

Modifying StateValues

It may seem odd that State::SetStateValue returns a modifiable reference to the variable it wraps. Why not pass in the new value as a second parameter? The reason is that a StateValue can be used to wrap not only fundamental types like bool, float, and int, but also aggregate types like structs or classes. In the case of aggregate types, it is useful to be able to retrieve a reference to the type in order to modify a single field, or invoke a single function.

For example, we could define a StateValue that wraps a struct as follows:

struct MoveParams
{
	MoveParams() : mSpeed(0.0f), mGravity(-9.8f) {}
	float mSpeed;
	float mGravity;
};

StateValue<MoveParams> mMoveParams;

In our states, we'd be able to modify any field of our struct easily:

SetStateValue(Owner().mMoveParams).mGravity = 0.0f; // In this state, we're in space!

When the state exits, the fields that were modified on the struct would be restored. There is no specical handling here - the entire struct is saved on the state when SetStateValue is first called, and restored entirely when the state exits.

When to modify StateValues

In the example above, we modify the StateValue mSpeedScale in the OnEnter function of our three states; however, nothing stops you from modifying StateValues from other functions in a state. For instance, it can be useful to change a value dynamically in a state's Update function. When a state modifies a StateValue, it will save the original value only the first time it modifies it. Subsequent writes to the StateValue will simply modify its value, and when the state exits, it will restore the original value, as expected.

For example, in the Swim state's OnEnter, we set mSpeedScale to 0.3; however, we could instead set mSpeedScale to a range of values from 0 to 0.3 based on how long the user presses movement input in Swim's Update function. When transitioning away from the Swim state, mSpeedScale would return to whatever value it had before Swim was entered.

State Arguments

Another useful feature of HSM is the ability to pass arguments to states when transitioning to them. As with functions, the ability to pass arguments to a state goes a long way to making that state reusable.

Let's take a look at an example of a character controller that makes use of state arguments:

// state_args.cpp

#include "hsm/statemachine.h"

using namespace hsm;

class AnimComponent
{
public:
	AnimComponent() : mLoop(false) {}
	void PlayAnim(const char* name, bool loop, float blendTime, float rate)
	{
		printf(">>> PlayAnim: %s, looping: %s\n", name, loop ? "true" : "false");
		mLoop = loop;
	}

	bool IsFinished() const { return !mLoop; }

private:
	bool mLoop;
};

class Character
{
public:
	Character();
	void Update();

	// Public to simplify sample
	bool mMove;
	bool mJump;

private:
	friend struct CharacterStates;
	StateMachine mStateMachine;

	AnimComponent mAnimComponent;
};

struct CharacterStates
{
	struct BaseState : StateWithOwner<Character>
	{
	};

	struct PlayAnim : BaseState
	{
		struct Args : StateArgs
		{
			Args(const char* animName, bool loop = true, float blendTime = 0.2f, float rate = 1.0f)
				: animName(animName), loop(loop), blendTime(blendTime), rate(rate) {}

			const char* animName;
			bool loop;
			float blendTime;
			float rate;
		};

		virtual void OnEnter(const Args& args)
		{
			Owner().mAnimComponent.PlayAnim(args.animName, args.loop, args.blendTime, args.rate);
		}

		virtual Transition GetTransition()
		{
			if (Owner().mAnimComponent.IsFinished())
				return SiblingTransition<PlayAnim_Done>();
			
			return NoTransition();
		}
	};

	struct PlayAnim_Done : BaseState
	{
	};


	struct Alive : BaseState
	{
		virtual Transition GetTransition()
		{
			return InnerEntryTransition<Stand>();
		}
	};

	struct Stand : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().mMove)
				return SiblingTransition<Move>();

			return InnerEntryTransition<PlayAnim>(PlayAnim::Args("Anim_Stand"));
		}
	};

	struct Move : BaseState
	{
		virtual Transition GetTransition()
		{
			if (!Owner().mMove)
				return SiblingTransition<Stand>();

			if (Owner().mJump)
			{
				Owner().mJump = false; // We've processed jump input, clear to avoid infinite transitions
				return SiblingTransition<Jump>();
			}

			return InnerEntryTransition<PlayAnim>(PlayAnim::Args("Anim_Move"));
		}
	};

	struct Jump : BaseState
	{
		virtual Transition GetTransition()
		{
			if (IsInInnerState<PlayAnim_Done>())
				return SiblingTransition<Move>();

			return InnerEntryTransition<PlayAnim>(PlayAnim::Args("Anim_Jump", false));
		}
	};
};

Character::Character()
	: mMove(false)
	, mJump(false)
{
	mStateMachine.Initialize<CharacterStates::Alive>(this);
	mStateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
}

void Character::Update()
{
	// Update state machine
	mStateMachine.ProcessStateTransitions();
	mStateMachine.UpdateStates();
}

int main()
{
	Character character;

	character.Update();

	character.mMove = true;
	character.Update();

	character.mJump = true;
	character.Update();
}

Before we look at the code, let's take a look at the plotHsm output:

state_args

From the plot, we can infer a few things:

The character can Stand, Move, or Jump
The only way to jump is while moving
The three states, Stand, Move, and Jump, all push the state PlayAnim

That last point is of particular interest: PlayAnim is a state that is pushed from multiple states. This is an example of a reusable state. Although not required, typically a state is made reusable by being able to pass arguments to it. Let's take a look at PlayAnim and it's sibling PlayAnim_Done:

	struct PlayAnim : BaseState
	{
		struct Args : StateArgs
		{
			Args(const char* animName, bool loop = true, float blendTime = 0.2f, float rate = 1.0f)
				: animName(animName), loop(loop), blendTime(blendTime), rate(rate) {}

			const char* animName;
			bool loop;
			float blendTime;
			float rate;
		};

		virtual void OnEnter(const Args& args)
		{
			Owner().mAnimComponent.PlayAnim(args.animName, args.loop, args.blendTime, args.rate);
		}

		virtual Transition GetTransition()
		{
			if (Owner().mAnimComponent.IsFinished())
				return SiblingTransition<PlayAnim_Done>();
			
			return NoTransition();
		}
	};

	struct PlayAnim_Done : BaseState
	{
	};

The first thing to notice is the nested struct named Args that derives from StateArgs. This is the mechanism by which you add arguments to a state: you must declare a struct named Args, and it must derive from StateArgs (note: StateArgs is a type defined in the hsm namespace). In this struct, we can declare whatever arguments we want as variables. In this case, we add 4 typical animation-related parameters, and make the first one, animName, a required parameter of the constructor.

The next thing to notice is how the OnEnter function now accepts the Args struct as a const reference parameter. When transitioning to state PlayAnim, it is this OnEnter that will be invoked. In this function, the parameter can be read, processed, or even copied into a data member of the state of type Args. In this case, state PlayAnim simply forwards the args, one by one, to Owner().mAnimComponent.PlayAnim.

Before we look at how to pass arguments to states, note that PlayAnim will sibling to the PlayAnim_Done state when the AnimComponent returns that the animation has finished playing. This is part of the PlayAnim state's "API", and we will see how it's used in the state machine below.

Now for how to pass arguments to the PlayAnim state. In the code, PlayAnim is a state that is pushed onto the stack as an InnerEntryTransition from three states: Stand, Move, and Jump. Let's look at how Stand does it:

	struct Stand : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().mMove)
				return SiblingTransition<Move>();

			return InnerEntryTransition<PlayAnim>(PlayAnim::Args("Anim_Stand"));
		}
	};

As we can see, to pass the expected arguments to the PlayAnim state, you must simply pass an instance of the nested Args struct as a parameter to the transition function. Notice that we make use of the constructor to make it easier to construct a temporary instance inline, so this looks very much like a regular function call.

NOTE: State arguments can be passed via any of the three transition functions: SiblingTransition, InnerTransition, and InnerEntryTransition. The only requirement is that the Args struct be copy-constructible, as a copy is made and kept until OnEnter is invoked.

The Move state, just like Stand, also pushes PlayAnim to play a looping animation. The Jump state is a little different:

	struct Jump : BaseState
	{
		virtual Transition GetTransition()
		{
			if (IsInInnerState<PlayAnim_Done>())
				return SiblingTransition<Move>();

			return InnerEntryTransition<PlayAnim>(PlayAnim::Args("Anim_Jump", false));
		}
	};

In this case, Jump pushes PlayAnim to play the jump anim in a non-looping fashion. The API we've defined for PlayAnim is that it will sibling to PlayAnim_Done when the animation that it plays is finished, which would normally only happen for non-looping animations. As such, the Jump state uses the state stack query function IsInInnerState<PlayAnim_Done>() to know when the jump animation has finished playing so that it can sibling back to the Move state. This is a common pattern when designing state machines in HSM, and is considered good practice.

Finally, let's look at our main function and the output of our program:

int main()
{
	Character character;

	character.Update();

	character.mMove = true;
	character.Update();

	character.mJump = true;
	character.Update();
}

Output:

HSM_1_TestHsm: Init    : struct CharacterStates::Alive
HSM_1_TestHsm:  Entry   : struct CharacterStates::Stand
HSM_1_TestHsm:   Entry   : struct CharacterStates::PlayAnim
>>> PlayAnim: Anim_Stand, looping: true
HSM_1_TestHsm:  Sibling : struct CharacterStates::Move
HSM_1_TestHsm:   Entry   : struct CharacterStates::PlayAnim
>>> PlayAnim: Anim_Move, looping: true
HSM_1_TestHsm:  Sibling : struct CharacterStates::Jump
HSM_1_TestHsm:   Entry   : struct CharacterStates::PlayAnim
>>> PlayAnim: Anim_Jump, looping: false
HSM_1_TestHsm:   Sibling : struct CharacterStates::PlayAnim_Done
HSM_1_TestHsm:  Sibling : struct CharacterStates::Move
HSM_1_TestHsm:   Entry   : struct CharacterStates::PlayAnim
>>> PlayAnim: Anim_Move, looping: true

We can see that PlayAnim is pushed from Stand, Move, and Jump; and in Jump's case, we see that PlayAnim siblings to PlayAnim_Done, which results in Jump sibling back to Move.

Storing Data on Cluster Root State

We've already seen many examples of a state storing state-specific data as data members of its class. Scoping data as narrowly as possible like this makes sense; but what if you have a group of states that need to access a shared set of data? In this section, we'll take a look at a good technique to do exactly that.

The gist of the technique is simple: given a group - or cluster - of states, store the shared data on the cluster's root state. Then, inner states access the data by retrieving a pointer to the root state, and access the shared data through it. Let's take a look at an example of this technique:

// cluster_root_state_data_1.cpp

#include "hsm/statemachine.h"

using namespace hsm;

class Character
{
public:
	Character();
	void Update();

	bool mJump;

private:
	friend struct CharacterStates;
	StateMachine mStateMachine;
};

struct CharacterStates
{
	struct BaseState : StateWithOwner<Character>
	{
	};

	struct Alive : BaseState
	{
		virtual Transition GetTransition()
		{
			return InnerEntryTransition<Stand>();
		}
	};

	struct Stand : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().mJump)
			{
				Owner().mJump = false;
				return SiblingTransition<Jump>();
			}
			
			return NoTransition();
		}
	};

	struct Jump : BaseState
	{
		int mJumpValue1;
		float mJumpValue2;
		bool mJumpValue3;

		Jump() : mJumpValue1(0), mJumpValue2(0.0f), mJumpValue3(false) { }

		virtual Transition GetTransition()
		{
			if (IsInInnerState<Jump_Done>())
				return SiblingTransition<Stand>();

			return InnerEntryTransition<Jump_Up>();
		}
	};

	struct Jump_Up : BaseState
	{
		virtual void OnEnter()
		{
			GetOuterState<Jump>()->mJumpValue1 = 1;
			GetOuterState<Jump>()->mJumpValue2 = 2.0f;
			GetOuterState<Jump>()->mJumpValue3 = true;
		}

		virtual Transition GetTransition()
		{
			return SiblingTransition<Jump_Down>();
		}
	};

	struct Jump_Down : BaseState
	{
		virtual void OnEnter()
		{
			GetOuterState<Jump>()->mJumpValue1 = 2;
			GetOuterState<Jump>()->mJumpValue2 = 4.0f;
			GetOuterState<Jump>()->mJumpValue3 = false;
		}

		virtual Transition GetTransition()
		{
			return SiblingTransition<Jump_Done>();
		}
	};

	struct Jump_Done : BaseState
	{
	};
};

Character::Character()
	: mJump(false)
{
	mStateMachine.Initialize<CharacterStates::Alive>(this);
	mStateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
}

void Character::Update()
{
	// Update state machine
	mStateMachine.ProcessStateTransitions();
	mStateMachine.UpdateStates();
}

int main()
{
	Character character;
	character.Update();
	character.mJump = true;
	character.Update();
}

Here's the plotHsm for this example:

cluster_root_state_data_1

In this example, the Jump state cluster has some data it wants to share across two of its inner states: Jump_Up and Jump_Down. The shared data is declared simply as data members of the Jump state itself:

	struct Jump : BaseState
	{
		int mJumpValue1;
		float mJumpValue2;
		bool mJumpValue3;

		Jump() : mJumpValue1(0), mJumpValue2(0.0f), mJumpValue3(false) { }

		virtual Transition GetTransition()
		{
			if (IsInInnerState<Jump_Done>())
				return SiblingTransition<Stand>();

			return InnerEntryTransition<Jump_Up>();
		}
	};

The Jump state is the root state of this cluster, which means that when we want the character to jump, we always transition to the Jump state first. Then inner states are pushed, and transition between each other. Because of this, inner states can always access the outer Jump state using the GetOuterState state stack query function. Both Jump_Up and Jump_Down do exactly that to grab a pointer to Jump and access its members:

	struct Jump_Up : BaseState
	{
		virtual void OnEnter()
		{
			GetOuterState<Jump>()->mJumpValue1 = 1;
			GetOuterState<Jump>()->mJumpValue2 = 2.0f;
			GetOuterState<Jump>()->mJumpValue3 = true;
		}

		virtual Transition GetTransition()
		{
			return SiblingTransition<Jump_Down>();
		}
	};

	struct Jump_Down : BaseState
	{
		virtual void OnEnter()
		{
			GetOuterState<Jump>()->mJumpValue1 = 2;
			GetOuterState<Jump>()->mJumpValue2 = 4.0f;
			GetOuterState<Jump>()->mJumpValue3 = false;
		}

		virtual Transition GetTransition()
		{
			return SiblingTransition<Jump_Done>();
		}
	};

This works as expected; however, invoking GetOuterState to access each member carries some overhead, as it crawls up the state stack to check if the input state is on the stack. To avoid this overhead, we can cache a pointer to the root state, as shown in this next example:

// cluster_root_state_data_2.cpp

<snip>

	struct JumpBaseState : BaseState
	{
		JumpBaseState() : mJumpState(NULL) {}

		virtual void OnEnter()
		{
			mJumpState = GetOuterState<Jump>();
			assert(mJumpState);
		}

		Jump& JumpState()
		{
			return *mJumpState;
		}

	private:
		Jump* mJumpState;
	};

	struct Jump_Up : JumpBaseState
	{
		virtual void OnEnter()
		{
			JumpBaseState::OnEnter();
			JumpState().mJumpValue1 = 1;
			JumpState().mJumpValue2 = 2.0f;
			JumpState().mJumpValue3 = true;
		}

		virtual Transition GetTransition()
		{
			return SiblingTransition<Jump_Down>();
		}
	};

	struct Jump_Down : JumpBaseState
	{
		virtual void OnEnter()
		{
			JumpBaseState::OnEnter();
			JumpState().mJumpValue1 = 2;
			JumpState().mJumpValue2 = 4.0f;
			JumpState().mJumpValue3 = false;
		}

		virtual Transition GetTransition()
		{
			return SiblingTransition<Jump_Done>();
		}
	};

In this second version, we introduced a new base class named JumpBaseState, that derives from the usual BaseState. In its OnEnter function, it caches the result of GetOuterState<Jump> in a data member, and provides a getter named JumpState that returns it. The inner states Jump_Up and Jump_Down now derive from JumpBaseState, making sure to first invoke JumpBaseState::OnEnter in their own OnEnter functions before invoking JumpState to access the cluster root state.

We can generalize this technique of accessing the cluster root state from inner states by transforming JumpBaseState into a template class, as show in this this third version of our example:

// cluster_root_state_data_3.cpp

<snip>

	template <typename RootStateType, typename BaseStateType>
	struct ClusterBaseState : BaseStateType
	{
		ClusterBaseState() : mRootState(NULL) {}

		virtual void OnEnter()
		{
			mRootState = this->template GetOuterState<RootStateType>();
			assert(mRootState);
		}

		RootStateType& ClusterRootState()
		{
			return *mRootState;
		}

	private:
		RootStateType* mRootState;
	};

<snip>

	typedef ClusterBaseState<Jump, BaseState> JumpBaseState;

	struct Jump_Up : JumpBaseState
	{
		virtual void OnEnter()
		{
			JumpBaseState::OnEnter();
			ClusterRootState().mJumpValue1 = 1;
			ClusterRootState().mJumpValue2 = 2.0f;
			ClusterRootState().mJumpValue3 = true;
		}

		virtual Transition GetTransition()
		{
			return SiblingTransition<Jump_Down>();
		}
	};

	struct Jump_Down : JumpBaseState
	{
		virtual void OnEnter()
		{
			JumpBaseState::OnEnter();
			ClusterRootState().mJumpValue1 = 2;
			ClusterRootState().mJumpValue2 = 4.0f;
			ClusterRootState().mJumpValue3 = false;
		}

		virtual Transition GetTransition()
		{
			return SiblingTransition<Jump_Done>();
		}
	};

JumpBaseState is now replaced by template class ClusterBaseState that can be used to declare a base type for any cluster in your state machine. In this case, we use a typedef to declare JumpBaseState:

typedef ClusterBaseState<Jump, BaseState> JumpBaseState;

The Jump_Up and Jump_Down states now invoke ClusterRootState() to access the Jump the state on the stack.

NOTE: The reason why the call to GetOuterState in ClusterBaseState is prefixed by this->template is because of C++ argument dependent lookup (ADL) rules. We must let the compiler know that we mean to call the member function named GetOuterState, and one way is to make it explicit by calling it via 'this'. Alternatively, we could also bring in the name by adding a using BaseStateType::GetOuterState; declaration to the class.

Restarting States

One useful feature of HSM is the ability to restart a state. This is accomplished by having a state return a sibling transition to itself. When this happens, the state class is exited, destroyed, and the same state is then created and entered.

Let's take a look at an example of how restarting states can be used to implement attack combos in a character controller:

// restarting_states.cpp

#include "hsm/statemachine.h"

using namespace hsm;

class AnimComponent
{
public:
	AnimComponent() {}
	void PlayAnim(const char* name)
	{
		printf(">>> PlayAnim: %s\n", name);
	}

	bool IsFinished() const { return false; } // Stub

	// Return true if input event was processed in animation
	bool PollEvent(const char*) { return true; } // Stub
};

class Character
{
public:
	Character();
	void Update();

	// Public to simplify sample
	bool mMove;
	bool mAttack;

private:
	friend struct CharacterStates;
	StateMachine mStateMachine;

	AnimComponent mAnimComponent;
};

struct CharacterStates
{
	struct BaseState : StateWithOwner<Character>
	{
	};

	struct Alive : BaseState
	{
		virtual Transition GetTransition()
		{
			return InnerEntryTransition<Locomotion>();
		}
	};

	struct Locomotion : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().mAttack)
			{
				// Start attack sequence with combo index 0
				return SiblingTransition<Attack>( Attack::Args(0) );
			}

			return InnerEntryTransition<Stand>();
		}
	};

	struct Stand : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().mMove)
				return SiblingTransition<Move>();

			return NoTransition();
		}
	};

	struct Move : BaseState
	{
		virtual Transition GetTransition()
		{
			if (!Owner().mMove)
				return SiblingTransition<Stand>();

			return NoTransition();
		}
	};

	struct Attack : BaseState
	{
		struct Args : StateArgs
		{
			Args(int comboIndex) : mComboIndex(comboIndex) {}
			int mComboIndex;
		};

		virtual void OnEnter(const Args& args)
		{
			Owner().mAttack = false;

			mComboIndex = args.mComboIndex;

			static const char* AttackAnim[] =
			{
				"Attack_1",
				"Attack_2",
				"Attack_3"
			};
			assert(mComboIndex < sizeof(AttackAnim) / sizeof(AttackAnim[0]));

			Owner().mAnimComponent.PlayAnim(AttackAnim[mComboIndex]);
		}

		virtual Transition GetTransition()
		{
			// Check if player can chain next attack
			if (Owner().mAttack
				&& mComboIndex < 2
				&& Owner().mAnimComponent.PollEvent("CanChainCombo"))
			{
				// Restart state with next combo index
				return SiblingTransition<Attack>( Attack::Args(mComboIndex + 1) );
			}

			if (Owner().mAnimComponent.IsFinished())
				return SiblingTransition<Locomotion>();

			return NoTransition();
		}

		virtual void Update()
		{
			printf(">>> Attacking: %d\n", mComboIndex);
		}

		int mComboIndex;
	};
};

Character::Character()
	: mMove(false)
	, mAttack(false)
{
	mStateMachine.Initialize<CharacterStates::Alive>(this);
	mStateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
}

void Character::Update()
{
	// Update state machine
	mStateMachine.ProcessStateTransitions();
	mStateMachine.UpdateStates();
}

int main()
{
	Character character;

	character.Update();

	character.mMove = true;
	character.Update();

	// First attack
	character.mAttack = true;
	character.Update();
	character.Update();
	character.Update();

	// Second attack combo
	character.mAttack = true;
	character.Update();
	character.Update();
	character.Update();

	// Third attack combo
	character.mAttack = true;
	character.Update();
	character.Update();
	character.Update();

	// Another attack has no effect (reached our max combo of 3)
	character.mAttack = true;
	character.Update();
}

Here's the plotHsm for this code:

restarting_states

From the plot, we can see that our character toggles between Locomotion and Attack states. While in Locomotion, our character can Stand or Move. The state that interests us is the Attack state: although it may not be perfectly clear in the image, along with the sibling transition arrows between Attack and Locomotion, there is an arrow that loops from Attack back to itself. This last arrow signifies a sibling transition to itself.

Let's focus on the Attack state:

	struct Attack : BaseState
	{
		struct Args : StateArgs
		{
			Args(int comboIndex) : mComboIndex(comboIndex) {}
			int mComboIndex;
		};

		virtual void OnEnter(const Args& args)
		{
			Owner().mAttack = false;

			mComboIndex = args.mComboIndex;

			static const char* AttackAnim[] =
			{
				"Attack_1",
				"Attack_2",
				"Attack_3"
			};
			assert(mComboIndex < sizeof(AttackAnim) / sizeof(AttackAnim[0]));

			Owner().mAnimComponent.PlayAnim(AttackAnim[mComboIndex]);
		}

		virtual Transition GetTransition()
		{
			// Check if player can chain next attack
			if (Owner().mAttack
				&& mComboIndex < 2
				&& Owner().mAnimComponent.PollEvent("CanChainCombo"))
			{
				// Restart state with next combo index
				return SiblingTransition<Attack>( Attack::Args(mComboIndex + 1) );
			}

			if (Owner().mAnimComponent.IsFinished())
				return SiblingTransition<Locomotion>();

			return NoTransition();
		}

		int mComboIndex;
	};

The idea behind this code is that we want to be able to chain up to three attacks. If the player presses the attack input, the character plays a first attack animation. The attack animations contain an event "CanChainCombo" at a specific time that signify that after this event, another attack can be chained. Thus, during the first attack, after the "CanChainCombo" event, and before the animation ends, if the player presses the attack input again, a second attack will be chained. The same logic is repeated for chaining a third attack.

To achieve the chaining of attacks, the Attack state accepts the "combo index" as an argument. When we enter Attack the first time, from the Locomotion state, index 0 is passed in. Once in the Attack state, if another attack is to be chained, GetTransition returns a sibling transition to itself, but this time passing in the current combo index + 1.

In the main function, we simulate the three attacks:

int main()
{
	Character character;

	character.Update();

	character.mMove = true;
	character.Update();

	// First attack
	character.mAttack = true;
	character.Update();
	character.Update();
	character.Update();

	// Second attack combo
	character.mAttack = true;
	character.Update();
	character.Update();
	character.Update();

	// Third attack combo
	character.mAttack = true;
	character.Update();
	character.Update();
	character.Update();

	// Another attack has no effect (reached our max combo of 3)
	character.mAttack = true;
	character.Update();
}

The output from the program clearly shows how the Attack state siblings to itself for the second and third attack:

HSM_1_TestHsm: Init    : struct CharacterStates::Alive
HSM_1_TestHsm:  Entry   : struct CharacterStates::Locomotion
HSM_1_TestHsm:   Entry   : struct CharacterStates::Stand
HSM_1_TestHsm:   Sibling : struct CharacterStates::Move
HSM_1_TestHsm:  Sibling : struct CharacterStates::Attack
>>> PlayAnim: Attack_1
>>> Attacking: 0
>>> Attacking: 0
>>> Attacking: 0
HSM_1_TestHsm:  Sibling : struct CharacterStates::Attack
>>> PlayAnim: Attack_2
>>> Attacking: 1
>>> Attacking: 1
>>> Attacking: 1
HSM_1_TestHsm:  Sibling : struct CharacterStates::Attack
>>> PlayAnim: Attack_3
>>> Attacking: 2
>>> Attacking: 2
>>> Attacking: 2
>>> Attacking: 2

In general, restarting states is a useful paradigm when you find yourself writing a sequence of very similar states that all do the same thing, but with slightly different parameters, as in the above example.

Selector States

In this section, we will learn a useful technique that can be used to reduce the number of explicit transitions in a set of sibling states by centralizing them into a selector state.

First let's take a look at an example that does not use selector states:

// selector_states_without.cpp

#include "hsm/statemachine.h"

using namespace hsm;

class Character
{
public:
	Character();
	void Update();

	// Public to simplify sample
	bool mMove;
	bool mJump;

private:
	friend struct CharacterStates;
	StateMachine mStateMachine;
};

struct CharacterStates
{
	struct BaseState : StateWithOwner<Character>
	{
	};

	struct Alive : BaseState
	{
		virtual Transition GetTransition()
		{
			return InnerEntryTransition<Locomotion>();
		}
	};

	struct LocomotionBaseState : BaseState
	{
		bool ShouldJump() const
		{
			return Owner().mJump;
		}

		bool ShouldMove() const
		{
			// Jumping has priority over moving
			return !ShouldJump() && Owner().mMove;
		}

		bool ShouldStand() const
		{
			return !ShouldJump() && !ShouldMove();
		}
	};

	struct Locomotion : LocomotionBaseState
	{
		virtual Transition GetTransition()
		{
			if (ShouldJump())
				return InnerEntryTransition<Jump>();

			if (ShouldMove())
				return InnerEntryTransition<Move>();

			assert(ShouldStand());
			return InnerEntryTransition<Stand>();
		}
	};

	struct Stand : LocomotionBaseState
	{
		virtual Transition GetTransition()
		{
			if (ShouldJump())
				return SiblingTransition<Jump>();

			if (ShouldMove())
				return SiblingTransition<Move>();

			return NoTransition();
		}
	};

	struct Move : LocomotionBaseState
	{
		virtual Transition GetTransition()
		{
			if (ShouldJump())
				return SiblingTransition<Jump>();

			if (ShouldStand())
				return SiblingTransition<Stand>();

			return NoTransition();
		}
	};

	struct Jump : LocomotionBaseState
	{
		virtual Transition GetTransition()
		{
			if (ShouldMove())
				return SiblingTransition<Move>();

			if (ShouldStand())
				return SiblingTransition<Stand>();

			return NoTransition();
		}
	};
};

Character::Character()
	: mMove(false)
	, mJump(false)
{
	mStateMachine.Initialize<CharacterStates::Alive>(this);
	mStateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
}

void Character::Update()
{
	printf(">>> Character::Update\n");

	// Update state machine
	mStateMachine.ProcessStateTransitions();
	mStateMachine.UpdateStates();
}

int main()
{
	Character character;

	character.Update();

	character.mMove = true;
	character.Update();

	character.mJump = true;
	character.Update();

	character.mJump = false;
	character.Update();

	character.mMove = false;
	character.Update();
}

This code is yet another example of a typical character controller for a character that can stand, move, and jump. Here's the output of the program:

>>> Character::Update
HSM_1_TestHsm: Init    : struct CharacterStates::Alive
HSM_1_TestHsm:  Entry   : struct CharacterStates::Locomotion
HSM_1_TestHsm:   Entry   : struct CharacterStates::Stand
>>> Character::Update
HSM_1_TestHsm:   Sibling : struct CharacterStates::Move
>>> Character::Update
HSM_1_TestHsm:   Sibling : struct CharacterStates::Jump
>>> Character::Update
HSM_1_TestHsm:   Sibling : struct CharacterStates::Move
>>> Character::Update
HSM_1_TestHsm:   Sibling : struct CharacterStates::Stand

And the plotHsm for this state machine:

selector_states_without

The plot of this state machine shows quite a mess of transition arrows between the Locomotion, Jump, Move, and Stand states. First let's take a look at the Locomotion state code:

	struct Locomotion : LocomotionBaseState
	{
		virtual Transition GetTransition()
		{
			if (ShouldJump())
				return InnerEntryTransition<Jump>();

			if (ShouldMove())
				return InnerEntryTransition<Move>();

			assert(ShouldStand());
			return InnerEntryTransition<Stand>();
		}
	};

So far in most of our examples, a state like Locomotion would usually select a single inner entry state, such as Stand. Why would we make it choose among Jump, Move, or Stand as its initial state like this? Well, in this case, let's assume it's possible for the player to activate the jump or move inputs before we enter this state. Always going through Stand first may not be desirable, especially if Stand's OnEnter has a side-effect that may affect the behaviour of the character when it finally ends up in Move or Jump. For instance, perhaps Stand::OnEnter resets some physics momentum variables, which is not what we want if we actually intend to transition to Move. In such cases, it makes sense to select the correct entry state right away.

Ok, so that explains the three arrows from Locomotion to Stand, Move, and Jump. Between these three sibling states, each state may transition to any other two:

	struct Stand : LocomotionBaseState
	{
		virtual Transition GetTransition()
		{
			if (ShouldJump())
				return SiblingTransition<Jump>();

			if (ShouldMove())
				return SiblingTransition<Move>();

			return NoTransition();
		}
	};

	struct Move : LocomotionBaseState
	{
		virtual Transition GetTransition()
		{
			if (ShouldJump())
				return SiblingTransition<Jump>();

			if (ShouldStand())
				return SiblingTransition<Stand>();

			return NoTransition();
		}
	};

	struct Jump : LocomotionBaseState
	{
		virtual Transition GetTransition()
		{
			if (ShouldMove())
				return SiblingTransition<Move>();

			if (ShouldStand())
				return SiblingTransition<Stand>();

			return NoTransition();
		}
	};

With three states, the transition code is not that hard to understand; however, as you add more sibling states, this can become more cumbersome to manage. It's easy to forget a transition, and the transition code itself becomes more noise than signal. To solve this problem, you can make use of a selector state. Let's take a look at the same example, but this time modified to make use of a selector state:

// selector_states_with.cpp

#include "hsm/statemachine.h"

using namespace hsm;

class Character
{
public:
	Character();
	void Update();

	// Public to simplify sample
	bool mMove;
	bool mJump;

private:
	friend struct CharacterStates;
	StateMachine mStateMachine;
};

struct CharacterStates
{
	struct BaseState : StateWithOwner<Character>
	{
	};

	struct Alive : BaseState
	{
		virtual Transition GetTransition()
		{
			return InnerEntryTransition<Locomotion>();
		}
	};

	struct LocomotionBaseState : BaseState
	{
		bool ShouldJump() const
		{
			return Owner().mJump;
		}

		bool ShouldMove() const
		{
			// Jumping has priority over moving
			return !ShouldJump() && Owner().mMove;
		}

		bool ShouldStand() const
		{
			return !ShouldJump() && !ShouldMove();
		}
	};

	struct Locomotion : LocomotionBaseState
	{
		virtual Transition GetTransition()
		{
			return InnerEntryTransition<Selector>();
		}
	};

	struct Selector : LocomotionBaseState
	{
		virtual Transition GetTransition()
		{
			if (ShouldJump())
				return SiblingTransition<Jump>();

			if (ShouldMove())
				return SiblingTransition<Move>();

			assert(ShouldStand());
			return SiblingTransition<Stand>();
		}
	};

	struct Stand : LocomotionBaseState
	{
		virtual Transition GetTransition()
		{
			if (!ShouldStand())
				return SiblingTransition<Selector>();

			return NoTransition();
		}
	};

	struct Move : LocomotionBaseState
	{
		virtual Transition GetTransition()
		{
			if (!ShouldMove())
				return SiblingTransition<Selector>();

			return NoTransition();
		}
	};

	struct Jump : LocomotionBaseState
	{
		virtual Transition GetTransition()
		{
			if (!ShouldJump())
				return SiblingTransition<Selector>();

			return NoTransition();
		}
	};
};

Character::Character()
	: mMove(false)
	, mJump(false)
{
	mStateMachine.Initialize<CharacterStates::Alive>(this);
	mStateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
}

void Character::Update()
{
	printf(">>> Character::Update\n");

	// Update state machine
	mStateMachine.ProcessStateTransitions();
	mStateMachine.UpdateStates();
}

int main()
{
	Character character;

	character.Update();

	character.mMove = true;
	character.Update();

	character.mJump = true;
	character.Update();

	character.mJump = false;
	character.Update();

	character.mMove = false;
	character.Update();
}

The main difference in this code is the addition of a new state named Selector that simply returns transitions to Stand, Move, or Jump based on the current inputs:

	struct Selector : LocomotionBaseState
	{
		virtual Transition GetTransition()
		{
			if (ShouldJump())
				return SiblingTransition<Jump>();

			if (ShouldMove())
				return SiblingTransition<Move>();

			assert(ShouldStand());
			return SiblingTransition<Stand>();
		}
	};

First, this selector state is used by Locomotion, simplifying its GetTransition:

	struct Locomotion : LocomotionBaseState
	{
		virtual Transition GetTransition()
		{
			return InnerEntryTransition<Selector>();
		}
	};

The three sibling states, Stand, Move, and Jump also transition to Selector as soon as they know they should no longer be in their state:

	struct Stand : LocomotionBaseState
	{
		virtual Transition GetTransition()
		{
			if (!ShouldStand())
				return SiblingTransition<Selector>();

			return NoTransition();
		}
	};

	struct Move : LocomotionBaseState
	{
		virtual Transition GetTransition()
		{
			if (!ShouldMove())
				return SiblingTransition<Selector>();

			return NoTransition();
		}
	};

	struct Jump : LocomotionBaseState
	{
		virtual Transition GetTransition()
		{
			if (!ShouldJump())
				return SiblingTransition<Selector>();

			return NoTransition();
		}
	};

As you can see, the states are simpler to understand. More importantly, using a selector state like this makes it significantly easier to scale up the state machine: adding a new sibling state involves simply adding a transition in Selector, and modifying the Should* input query functions to manage the priority of the input values.

Now let's take a look at the plotHsm for this code:

selector_states_with

Compared to the plot from the example without a selector state, it should be easier to understand the transitions between the states.

And finally, let's look at the output for this example using selector states:

>>> Character::Update
HSM_1_TestHsm: Init    : struct CharacterStates::Alive
HSM_1_TestHsm:  Entry   : struct CharacterStates::Locomotion
HSM_1_TestHsm:   Entry   : struct CharacterStates::Selector
HSM_1_TestHsm:   Sibling : struct CharacterStates::Stand
>>> Character::Update
HSM_1_TestHsm:   Sibling : struct CharacterStates::Selector
HSM_1_TestHsm:   Sibling : struct CharacterStates::Move
>>> Character::Update
HSM_1_TestHsm:   Sibling : struct CharacterStates::Selector
HSM_1_TestHsm:   Sibling : struct CharacterStates::Jump
>>> Character::Update
HSM_1_TestHsm:   Sibling : struct CharacterStates::Selector
HSM_1_TestHsm:   Sibling : struct CharacterStates::Move
>>> Character::Update
HSM_1_TestHsm:   Sibling : struct CharacterStates::Selector
HSM_1_TestHsm:   Sibling : struct CharacterStates::Stand

As expected, we can see how the Selector state is used to move between the states. It's interesting to note that selector states like this never remain on the state stack once it has settled (i.e. once StateMachine::UpdateStateTransitions has completed). It's sole purpose is to route transitions between states that do remain on a settled state stack.

Done States

As you know by now, there is no way for an inner state to directly force a transition for an outer state. This is by design as it reduces coupling between sets of states at different depths by keeping dependencies in one direction - that is, only outer states know about inner states. Of course, when designing state machines, you will often find yourself in a situation where you would like an inner state to communicate to an outer state that it can now make a sibling transition. In this section, we'll take a look at a common technique to solve this problem.

Let's say we're implementing a character state machine, and we'd like to add the ability for our character to open doors. Opening a door is a sequence of actions: first get into position in front of the door, then play the open door animation. One this sequence is done, we'd like our character to go back to the normal standing position. The following example shows how we could implement this:

// done_states.cpp

#include "hsm/statemachine.h"

using namespace hsm;

class Character
{
public:
	Character();
	void Update();

	// Public to simplify sample
	bool mOpenDoor;

private:
	friend struct CharacterStates;
	StateMachine mStateMachine;
};

struct CharacterStates
{
	struct BaseState : StateWithOwner<Character>
	{
	};

	struct Alive : BaseState
	{
		virtual Transition GetTransition()
		{
			return InnerEntryTransition<Stand>();
		}
	};

	struct Stand : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().mOpenDoor)
			{
				Owner().mOpenDoor = false;
				return SiblingTransition<OpenDoor>();
			}
			
			return NoTransition();
		}
	};

	struct OpenDoor : BaseState
	{
		virtual Transition GetTransition()
		{
			if (IsInInnerState<OpenDoor_Done>())
				return SiblingTransition<Stand>();

			return InnerEntryTransition<OpenDoor_GetIntoPosition>();
		}
	};

	struct OpenDoor_GetIntoPosition : BaseState
	{
		bool IsInPosition() const { return true; } // Stub

		virtual Transition GetTransition()
		{
			if (IsInPosition())
				return SiblingTransition<OpenDoor_PlayOpenAnim>();

			return NoTransition();
		}
	};

	struct OpenDoor_PlayOpenAnim : BaseState
	{
		bool IsAnimDone() const { return true; } // Stub

		virtual Transition GetTransition()
		{
			if (IsAnimDone())
				return SiblingTransition<OpenDoor_Done>();

			return NoTransition();
		}
	};

	struct OpenDoor_Done : BaseState
	{
	};
};

Character::Character()
	: mOpenDoor(false)
{
	mStateMachine.Initialize<CharacterStates::Alive>(this);
	mStateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
}

void Character::Update()
{
	printf(">>> Character::Update\n");

	// Update state machine
	mStateMachine.ProcessStateTransitions();
	mStateMachine.UpdateStates();
}

int main()
{
	Character character;

	character.Update();

	character.mOpenDoor = true;
	character.Update();
}

Here's a plot of the state machine:

done_states

From the plot, we can clearly see that once Stand siblings to OpenDoor, OpenDoor starts up a sequence of inner states: first it enters OpenDoor_GetIntoPosition, which siblings to OpenDoor_PlayOpenAnim, which finally siblings to OpenDoor_Done. This last transition is the key to making it all work. If we take a look at the code for the OpenDoor outer state, we can see that it uses the IsInInnerState state stack query function to look for when OpenDoor_Done is on the stack, upon which it siblings back to Stand:

	struct OpenDoor : BaseState
	{
		virtual Transition GetTransition()
		{
			if (IsInInnerState<OpenDoor_Done>())
				return SiblingTransition<Stand>();

			return InnerEntryTransition<OpenDoor_GetIntoPosition>();
		}
	};

One very important thing to realize about using done states is that the done state itself, OpenDoor_Done in this case, is what we call a "transient state" because it does not remain on the stack very long. In fact, by the time the StateMachine::ProcessStateTransitions function is finished, it is guaranteed to never be on the state stack. As explained in Chapter 3, GetTransition will be called over and over from outermost to innermost state every time a transition occurs until the state stack has settled. So when OpenDoor_PlayOpenAnim siblings to OpenDoor_Done, outer state OpenDoor's GetTransition will be called, where it will see that OpenDoor_Done is on the stack, and make a sibling transition to Stand, thereby exiting both OpenDoor_Done and OpenDoor.

In effect, a done state acts much like a boolean return value from the set of inner states to an outer state. In fact, it can be much more than a simple boolean; for instance, we could store any data on a done state, perhaps passing them by state arguments, and the outer state could retrieve this data by using the GetInnerState query function. In our example, this would look something like:

	struct OpenDoor : BaseState
	{
		virtual Transition GetTransition()
		{
			if (OpenDoor_Done* doneState = GetInnerState<OpenDoor_Done>())
			{
				// Now we know we're done and we can read values on doneState
				//...
				return SiblingTransition<Stand>();
			}

			return InnerEntryTransition<OpenDoor_GetIntoPosition>();
		}
	};

When the call to GetInnerState returns a valid value, we know that the done state is on the stack, and we've got a pointer to it, so we can read any values stored on it.

Sharing Functions Across States

While authoring states in HSM, you will likely find yourself repeating bits of code. Naturally, you will want to factor these out into functions. In this section, we'll take a look at some techniques for doing that.

The trick to sharing functions across states is to define the function in a base class that the states derive from. So far in most of our examples, we have defined a base class for our states that derives from hsm::StateWithOwner<OwnerType>. For example:

// sharing_functions_across_states.cpp
<snip>

	struct BaseState : StateWithOwner<Character>
	{
	};

Note that this empty class, BaseState, could just have easily been declared using a typedef:

	typedef StateWithOwner<Character> BaseState;

However, we opted to define an empty base class because it's a good place to add shared functions that can be used across states. For example:

	struct BaseState : StateWithOwner<Character>
	{
		void ClearJump() { Owner().mJump = false; }
	};

Here we've added a shared function ClearJump that any state can use to clear a flag in the owner class. Note that because BaseState derives from StateWithOwner, it can access the owner instance via the Owner function, as in any other state.

If you only need to share some functions across a group of states, rather than all states, create a new BaseState-derived class from which your set of states will derive, and implement your shared functions in this new class. For example:

	struct LocomotionBaseState : BaseState
	{
		bool ShouldJump() const
		{
			return Owner().mJump;
		}

		bool ShouldMove() const
		{
			// Jumping has priority over moving
			return !ShouldJump() && Owner().mMove;
		}

		bool ShouldStand() const
		{
			return !ShouldJump() && !ShouldMove();
		}
	};

We've defined a base class LocomotionBaseState that derives from BaseState, and that exposes some utility functions for our locomotion-related states.

Finally, what if you've created a few different utility base states, and you want a state to have access to more than one of them? Your first thought might have the state class multiply inherit from each of the utility base state classes. Unfortunately, inheriting from multiple states that eventually derive from hsm::State is not supported by HSM for various reasons.

NOTE: The main reason for which state classes can not multiply inherit from classes that implement hsm::State is that a state must be convertible to hsm::State*, and multiple inheritance leads to ambiguity. Furthermore, even if state classes were to use virtual inheritance to guarantee a single hsm::State base, a dynamic_cast would be required to perform the cast; however, C++ RTTI is explicitly not required by HSM.

The solution is to chain base states using a template parameter to specify the base state:

	template <typename BaseType = BaseState>
	struct JumpBaseState : BaseType
	{
		using BaseType::Owner;

		void ClearJump() { Owner().mJump = false; }
	};

	template <typename BaseType = BaseState>
	struct MoveBaseState : BaseType
	{
		using BaseType::Owner;

		void ClearMove() { Owner().mMove = false; }
	};

	struct JumpAndMove : JumpBaseState< MoveBaseState<> >
	{
		virtual void OnEnter()
		{
			ClearJump();
			ClearMove();
		}
	};

As you can see, JumpAndMove is able to bring in the utility functions from both JumpBaseState and MoveBaseState by chaining them together. Effectively, in this case, the inheritance order is: JumpAndMove : JumpBaseState : MoveBaseState : BaseState : hsm::State.

This technique of making a template state is useful in many cases; for instance, it can also be used to share states across different state machines that each have a different OwnerType. In these cases, the BaseType template parameter would not specify a default, as in our example above; it would be explicitly passed in when used.

A final note on this technique: you may have noticed the using BaseType::Owner; declaration in the template base states. This is needed by certain compilers that cannot determine the scope of the name 'Owner'.

Deferred Transitions

So far, we've seen how a state returns what transition to make via its GetState function. You may have noticed that the GetState function is expected to return a Transition object, and we use functions like SiblingTransition<TargetState>, InnerTransition<TargetState>, and InnerEntryTransition<TargetState> to create these Transition objects.

There is nothing special about the Transition class itself; it's a simple class that stores the type of transition it represents (sibling, inner, inner entry, or no transition), the target state of the transition, and optionally state arguments. As such, you can store a Transition instance as a state data member, and return its value via a state's GetTransition function. Doing so allows you to separate the point at which you decide what transition to make from the point at which it's returned. We call this technique deferring a transition, and we'll take a look at an example of how to use them in this section.

One reason to use deferred transitions is to avoid (or fix) infinite transition loops. Let's take a look at an example:

// deferred_transitions.cpp

#include "hsm/statemachine.h"

using namespace hsm;

class Character
{
public:
	Character();
	void Update();

	// Public to simplify sample
	bool mCrouchInputPressed;

private:
	friend struct CharacterStates;
	StateMachine mStateMachine;
};

struct CharacterStates
{
	struct BaseState : StateWithOwner<Character>
	{
	};

	struct Alive : BaseState
	{
		virtual Transition GetTransition()
		{
			return InnerEntryTransition<Stand>();
		}
	};

	struct Stand : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().mCrouchInputPressed)
			{
				return SiblingTransition<Crouch>();
			}

			return NoTransition();
		}
	};

	struct Crouch : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().mCrouchInputPressed)
				return SiblingTransition<Stand>();

			return NoTransition();
		}
	};
};

Character::Character()
	: mCrouchInputPressed(false)
{
	mStateMachine.Initialize<CharacterStates::Alive>(this);
	mStateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
}

void Character::Update()
{
	// Update state machine
	mStateMachine.ProcessStateTransitions();
	mStateMachine.UpdateStates();
}

int main()
{
	Character character;

	character.Update();

	printf(">>> Crouch!\n");
	character.mCrouchInputPressed = true;
	character.Update();
	character.mCrouchInputPressed = false;
	character.Update();

	printf(">>> Stand!\n");
	character.mCrouchInputPressed = true;
	character.Update();
	character.mCrouchInputPressed = false;
	character.Update();

	printf(">>> Crouch!\n");
	character.mCrouchInputPressed = true;
	character.Update();
	character.mCrouchInputPressed = false;
	character.Update();
}

In this simple character controller, we want to be able to toggle between the Stand and Crouch states by pressing the same input button, the state of which is represented by the Character::mCrouchInputPressed bool. The above example presents a typical first attempt, except it doesn't work and produces the following output:

HSM_1_TestHsm: Init    : struct CharacterStates::Alive
HSM_1_TestHsm:  Entry   : struct CharacterStates::Stand
>>> Crouch!
HSM_1_TestHsm:  Sibling : struct CharacterStates::Crouch
HSM_1_TestHsm:  Sibling : struct CharacterStates::Stand
HSM_1_TestHsm:  Sibling : struct CharacterStates::Crouch
HSM_1_TestHsm:  Sibling : struct CharacterStates::Stand
HSM_1_TestHsm:  Sibling : struct CharacterStates::Crouch
HSM_1_TestHsm:  Sibling : struct CharacterStates::Stand
HSM_1_TestHsm:  Sibling : struct CharacterStates::Crouch
HSM_1_TestHsm:  Sibling : struct CharacterStates::Stand
HSM_1_TestHsm:  Sibling : struct CharacterStates::Crouch
HSM_1_TestHsm:  Sibling : struct CharacterStates::Stand
HSM_1_TestHsm:  Sibling : struct CharacterStates::Crouch
HSM_1_TestHsm:  Sibling : struct CharacterStates::Stand
HSM_1_TestHsm:  Sibling : struct CharacterStates::Crouch
HSM_1_TestHsm:  Sibling : struct CharacterStates::Stand
HSM_1_TestHsm:  Sibling : struct CharacterStates::Crouch
HSM_1_TestHsm:  Sibling : struct CharacterStates::Stand
HSM_1_TestHsm:  Sibling : struct CharacterStates::Crouch
HSM_1_TestHsm:  Sibling : struct CharacterStates::Stand
HSM_1_TestHsm:  Sibling : struct CharacterStates::Crouch
HSM_1_TestHsm:  Sibling : struct CharacterStates::Stand
HSM_1_TestHsm:  Sibling : struct CharacterStates::Crouch
<snip>
Assertion failed: (false) && "ProcessStateTransitions: detected infinite transition loop", file C:\hsm\src\statemachine.cpp, line 125

From the output we see that we have introduced an infinite transition loop between the Stand and Crouch states (HSM issues an assertion when it detects this condition in debug builds). The reason this happens is that, as you may recall, whenever a transition is made, ProcessStateTransitions will call GetTransition on the entire state stack from outermost to innermost state all over again, until no more transitions are made (until the stack has settled). In this case, both states use the same condition to transition between each other, causing a transition from one to the other infinitely.

There are a few different ways to solve this problem. As we've done in previous examples, one way is to simply make sure to reset the bool, Character::mCrouchInputPressed in this case, just before we transition. Although this works in our examples, in production code, it's not always feasible. For instance, in a game engine, we'd normally query the input state of a controller or keyboard, and this state is usually read only, except when it gets updated once per frame. A potential solution is to mirror the input state into variables for use by the state machine, which would then be allowed to write to them; but this is cumbersome.

A better solution is to defer the transition by a frame by moving the decision making logic to the Update function:

	struct Stand : BaseState
	{
		virtual Transition GetTransition()
		{
			return mTransition;
		}

		virtual void Update()
		{
			if (Owner().mCrouchInputPressed)
				mTransition = SiblingTransition<Crouch>();
		}

		Transition mTransition;
	};

	struct Crouch : BaseState
	{
		virtual Transition GetTransition()
		{
			return mTransition;
		}

		virtual void Update()
		{
			if (Owner().mCrouchInputPressed)
				mTransition = SiblingTransition<Stand>();
		}

		Transition mTransition;
	};

As you can see, we now store a Transition data member named mTransition on each state, which has type "no transition" by default, so returning it in GetTransition as we do will have no effect until we set it. Now in Update, we perform the same check as we did previously, but this time we store the sibling transition into mTransition. By doing this, we delay the transition by "one frame" - or rather, by one call to StateMachine::ProcessStateTransitions. In between, the input state can be updated. An input pressed event would be true for only one frame until the player releases and re-presses the same button/key, so we'd only sibling from one state to the other for a single input pressed event. Now the program behaves as expected, as we can see from the output:

HSM_1_TestHsm: Init    : struct CharacterStates::Alive
HSM_1_TestHsm:  Entry   : struct CharacterStates::Stand
>>> Crouch!
HSM_1_TestHsm:  Sibling : struct CharacterStates::Crouch
>>> Stand!
HSM_1_TestHsm:  Sibling : struct CharacterStates::Stand
>>> Crouch!
HSM_1_TestHsm:  Sibling : struct CharacterStates::Crouch

One important thing to note is that deferring transitions this way should not be a general solution. In other words, except when needed, do not opt to compute transitions in Update and return the cached value in GetTransition by default. It is always better to compute and return transitions in GetTransition as much as possible. The rule of thumb should be: after calling StateMachine::ProcessStateTransitions, calling the same function a second time immediately should have no effect on the state stack. This is the best way to avoid being in an unexpected or "in between" state. In our example, calling StateMachine::ProcessStateTransitions a second time would result in a different state stack, but we've made an exception in this case because we know we have ended in a valid state, and purposely deferred the transition to avoid an infinite transition loop.

In the example above, we saw how to use deferred transitions to avoid infinite transition loops. There are many other ways to apply this technique, not only to fix problems like infinite transition loops, but to improve state reuse, as we'll see in the next section.

Reusable States

When implementing state machines, as with programming in general, you will want to avoid duplicating code. We've already seen how to avoid duplicating functions by sharing them across states via base state classes. Another useful way to avoid code duplication is by creating reusable states, which is the topic of this section.

The key to reusable states is combining two techniques we've covered so far: state arguments and deferred transitions. Let's take a look at an example:

// reusable_states.cpp

#include "hsm/statemachine.h"

using namespace hsm;

class AnimComponent
{
public:
	AnimComponent() : mLoop(false) {}
	void PlayAnim(const char* name, bool loop)
	{
		printf(">>> PlayAnim: %s, looping: %s\n", name, loop ? "true" : "false");
		mLoop = loop;
	}

	bool IsFinished() const { return !mLoop; }

private:
	bool mLoop;
};

class Character
{
public:
	Character();
	void Update();

	// Public to simplify sample
	bool mAttack;

private:
	friend struct CharacterStates;
	StateMachine mStateMachine;

	AnimComponent mAnimComponent;
};

struct CharacterStates
{
	struct BaseState : StateWithOwner<Character>
	{
	};

	struct PlayAnim_Done : BaseState
	{
	};

	struct PlayAnim : BaseState
	{
		struct Args : StateArgs
		{
			Args(const char* animName
				, bool loop = true
				, const Transition& doneTransition = SiblingTransition<PlayAnim_Done>()
				)
				: animName(animName)
				, loop(loop)
				, doneTransition(doneTransition)
			{}

			const char* animName;
			bool loop;
			Transition doneTransition;
		};

		virtual void OnEnter(const Args& args)
		{
			Owner().mAnimComponent.PlayAnim(args.animName, args.loop);
			mDoneTransition = args.doneTransition;
		}

		virtual Transition GetTransition()
		{
			if (Owner().mAnimComponent.IsFinished())
				return mDoneTransition;
			
			return NoTransition();
		}

		Transition mDoneTransition;
	};

	struct Alive : BaseState
	{
		virtual Transition GetTransition()
		{
			return InnerEntryTransition<Stand>();
		}
	};

	struct Stand : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().mAttack)
			{
				Owner().mAttack = false;
				return SiblingTransition<Attack>();
			}

			return NoTransition();
		}
	};

	struct Attack : BaseState
	{
		virtual Transition GetTransition()
		{
			if (IsInInnerState<PlayAnim_Done>())
				return SiblingTransition<Stand>();

			return InnerEntryTransition<PlayAnim>(PlayAnim::Args("Attack_1", false,
				SiblingTransition<PlayAnim>(PlayAnim::Args("Attack_2", false,
				SiblingTransition<PlayAnim>(PlayAnim::Args("Attack_3", false))))));
		}
	};
};

Character::Character()
	: mAttack(false)
{
	mStateMachine.Initialize<CharacterStates::Alive>(this);
	mStateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
}

void Character::Update()
{
	// Update state machine
	mStateMachine.ProcessStateTransitions();
	mStateMachine.UpdateStates();
}

int main()
{
	Character character;

	character.Update();

	character.mAttack = true;
	character.Update();
}

This example is similar to the one from the State Arguments section, where a reusable state named PlayAnim is used to play an animation from any other state. In this version, we've removed a few state arguments to PlayAnim, but have added a new one named doneTransition:

	struct PlayAnim : BaseState
	{
		struct Args : StateArgs
		{
			Args(const char* animName
				, bool loop = true
				, const Transition& doneTransition = SiblingTransition<PlayAnim_Done>()
				)
				: animName(animName)
				, loop(loop)
				, doneTransition(doneTransition)
			{}

			const char* animName;
			bool loop;
			Transition doneTransition;
		};

The new state argument, doneTransition, is a deferred transition that is returned by the PlayAnim state when it detects that the animation has finished playing. By exposing which transition to make when the animation is done playing makes this reusable state much more flexible. For instance, the Attack state queues up three PlayAnims to play a sequence of three animations before returning back to the Stand state:

	struct Attack : BaseState
	{
		virtual Transition GetTransition()
		{
			if (IsInInnerState<PlayAnim_Done>())
				return SiblingTransition<Stand>();

			return InnerEntryTransition<PlayAnim>(PlayAnim::Args("Attack_1", false,
				SiblingTransition<PlayAnim>(PlayAnim::Args("Attack_2", false,
				SiblingTransition<PlayAnim>(PlayAnim::Args("Attack_3", false))))));
		}
	};

The Attack state begins by returning an InnerEntryTransition to PlayAnim to play the first animation, and passes in as the doneTransition argument a sibling transition to another instance of PlayAnim, this time to play the second animation, and sibling to a third instance as its doneTransition. The third and final PlayAnim will sibling to PlayAnim_Done, the default doneTransition value, which Attack::GetTransition looks for to sibling back to Stand.

Here's the output from our program:

HSM_1_TestHsm: Init    : struct CharacterStates::Alive
HSM_1_TestHsm:  Entry   : struct CharacterStates::Stand
HSM_1_TestHsm:  Sibling : struct CharacterStates::Attack
HSM_1_TestHsm:   Entry   : struct CharacterStates::PlayAnim
>>> PlayAnim: Attack_1, looping: false
HSM_1_TestHsm:   Sibling : struct CharacterStates::PlayAnim
>>> PlayAnim: Attack_2, looping: false
HSM_1_TestHsm:   Sibling : struct CharacterStates::PlayAnim
>>> PlayAnim: Attack_3, looping: false
HSM_1_TestHsm:   Sibling : struct CharacterStates::PlayAnim_Done
HSM_1_TestHsm:  Sibling : struct CharacterStates::Stand

From the output, we can see clearly that the first PlayAnim state siblings to another PlayAnim instance, which in turn siblings to a third PlayAnim instance that finally siblings to PlayAnim_Done, at which point the outer state Attack siblings back to Stand.

Passing in transitions to states via state arguments is a powerful technique that increases state reuse. One downside to using reusable states is that it can make it more difficult to read and understand a state machine. For instance, in our example, Stand could have made a sibling transition directly to PlayAnim, queuing up the next 2 PlayAnims, and setting the last one to sibling back to Stand. However, to improve readability, Stand siblings to Attack, which is just a "shell" state that starts up the PlayAnim sequence as inner states. This is a good technique as it effectively gives a name to each instance of a reusable state usage.

Sharing HSMs

In all our examples so far, we've looked at how to author a single state machine, say, for a character controller. However, in a real project, you will likely find yourself needing to implement multiple state machines for different systems. In such situations, we would like to avoid duplicating code as much as possible. In this section, we will look at a couple of different techniques to share state machine code.

Sharing states with unrelated owners

One common situation that often arises when authoring state machines is the need to share a state, or a set of states, across different state machines. For example, say we're writing a game, and we have a state machine to control the hero, and another one to control enemies, and in both these state machines, we want to be able to play animations. The following example code shows how we can share PlayAnim states across both state machines:

// shared_states_unrelated_owners.cpp

#include "hsm/statemachine.h"

using namespace hsm;

struct SharedStates
{
	template <typename BaseState>
	struct PlayAnim_Done : BaseState
	{
	};

	template <typename BaseState>
	struct PlayAnim : BaseState
	{
		using BaseState::Owner;

		struct Args : StateArgs
		{
			Args(const char* animName
				, bool loop = true
				, const Transition& doneTransition = SiblingTransition< PlayAnim_Done<BaseState> >()
				)
				: animName(animName)
				, loop(loop)
				, doneTransition(doneTransition)
			{}

			const char* animName;
			bool loop;
			Transition doneTransition;
		};

		virtual void OnEnter(const Args& args)
		{
			Owner().mAnimComponent.PlayAnim(args.animName, args.loop);
			mDoneTransition = args.doneTransition;
		}

		virtual Transition GetTransition()
		{
			if (Owner().mAnimComponent.IsFinished())
				return mDoneTransition;

			return NoTransition();
		}

		Transition mDoneTransition;
	};
};

class AnimComponent
{
public:
	AnimComponent() : mLoop(false) {}
	void PlayAnim(const char* name, bool loop)
	{
		printf(">>> PlayAnim: %s, looping: %s\n", name, loop ? "true" : "false");
		mLoop = loop;
	}

	bool IsFinished() const { return !mLoop; }

private:
	bool mLoop;
};


////////////////////// Hero //////////////////////

class Hero
{
public:
	Hero();
	void Update();

	// Public to simplify sample
	bool mAttack;

private:
	friend struct SharedStates;
	friend struct HeroStates;
	StateMachine mStateMachine;

	AnimComponent mAnimComponent;
};

struct HeroStates
{
	struct BaseState : StateWithOwner<Hero>
	{
	};

	typedef SharedStates::PlayAnim_Done<BaseState> PlayAnim_Done;
	typedef SharedStates::PlayAnim<BaseState> PlayAnim;

	struct Alive : BaseState
	{
		virtual Transition GetTransition()
		{
			return InnerEntryTransition<Stand>();
		}
	};

	struct Stand : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().mAttack)
			{
				Owner().mAttack = false;
				return SiblingTransition<Attack>();
			}

			return NoTransition();
		}
	};

	struct Attack : BaseState
	{
		virtual Transition GetTransition()
		{
			if (IsInInnerState<PlayAnim_Done>())
				return SiblingTransition<Stand>();

			return InnerEntryTransition<PlayAnim>(PlayAnim::Args("Attack_1", false));
		}
	};
};

Hero::Hero()
	: mAttack(false)
{
	mStateMachine.Initialize<HeroStates::Alive>(this);
	mStateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
}

void Hero::Update()
{
	// Update state machine
	mStateMachine.ProcessStateTransitions();
	mStateMachine.UpdateStates();
}

////////////////////// Enemy //////////////////////

class Enemy
{
public:
	Enemy();
	void Update();

	// Public to simplify sample
	bool mAttack;

private:
	friend struct SharedStates;
	friend struct EnemyStates;
	StateMachine mStateMachine;

	AnimComponent mAnimComponent;
};

struct EnemyStates
{
	struct BaseState : StateWithOwner<Enemy>
	{
	};

	typedef SharedStates::PlayAnim_Done<BaseState> PlayAnim_Done;
	typedef SharedStates::PlayAnim<BaseState> PlayAnim;

	struct Alive : BaseState
	{
		virtual Transition GetTransition()
		{
			return InnerEntryTransition<Stand>();
		}
	};

	struct Stand : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().mAttack)
			{
				Owner().mAttack = false;
				return SiblingTransition<Attack>();
			}

			return NoTransition();
		}
	};

	struct Attack : BaseState
	{
		virtual Transition GetTransition()
		{
			if (IsInInnerState<PlayAnim_Done>())
				return SiblingTransition<Stand>();

			return InnerEntryTransition<PlayAnim>(PlayAnim::Args("Attack_1", false));
		}
	};
};

Enemy::Enemy()
	: mAttack(false)
{
	mStateMachine.Initialize<EnemyStates::Alive>(this);
	mStateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
}

void Enemy::Update()
{
	// Update state machine
	mStateMachine.ProcessStateTransitions();
	mStateMachine.UpdateStates();
}


////////////////////// main //////////////////////

int main()
{
	Hero hero;
	hero.Update();
	hero.mAttack = true;
	hero.Update();

	Enemy enemy;
	enemy.Update();
	enemy.mAttack = true;
	enemy.Update();
}

In this example, we have two state machines: one for the Hero class and one for the Enemy class. In both state machines, state Attack wants to push the PlayAnim state, and checks for the PlayAnim_Done state. The definitions for these states is in a struct named SharedStates:

struct SharedStates
{
	template <typename BaseState>
	struct PlayAnim_Done : BaseState
	{
	};

	template <typename BaseState>
	struct PlayAnim : BaseState
	{
		using BaseState::Owner;

		<snip>
	};
};

These states look very much like the usual states that we write, but with a couple of important differences. First of all, they are template classes so that the base state class can be specified. We do this because the base state classes are different and unrelated types in both our state machines:

struct HeroStates
{
	struct BaseState : StateWithOwner<Hero>
	{
	};
	
	<snip>
};

<snip>

struct EnemyStates
{
	struct BaseState : StateWithOwner<Enemy>
	{
	};
	
	<snip>
};

As usual, our BaseState is a StateWithOwner, and in our example, the OwnerTypes, Hero and Enemy are unrelated. Now one consequence of using template classes to represent our states is that we need to deal with C++ argument dependent lookup (ADL) rules. For instance, the PlayAnim state makes calls to the Owner() function, which is expected to be implemented in its base class. As the base class is a template type, the calls to Owner() depend on the template argument, so we must let the compiler know that this is the case. We solve this by bringing in the dependent name into the PlayAnim class with a using declaration: using BaseState::Owner;. Alternatively, you can also prefix each call to Owner() with this-> to achieve the same result.

That's all there is to it! With this technique, states can be easily shared between arbitrary state machines with unrelated owners. Of course, one important thing to keep in mind is that, although the base states don't have to be related, they must provide the same functions or types that are accessed by that state. In our example, the PlayAnim state expects an AnimComponent named mAnimComponent to exist on the Owner type.

Sharing states with related owners

Although the technique we presented in the previous section works for states with unrelated owner types, we can simplify the technique when the owner types are related. Let's take a look at a modified version of our example where both Hero and Enemy derive from a common base named Character:

// shared_states_related_owners.cpp

#include "hsm/statemachine.h"

using namespace hsm;

class AnimComponent
{
public:
	AnimComponent() : mLoop(false) {}
	void PlayAnim(const char* name, bool loop)
	{
		printf(">>> PlayAnim: %s, looping: %s\n", name, loop ? "true" : "false");
		mLoop = loop;
	}

	bool IsFinished() const { return !mLoop; }

private:
	bool mLoop;
};

////////////////////// Character //////////////////////

class Character
{
public:
	void Update();

protected:
	friend struct SharedStates;
	StateMachine mStateMachine;
	AnimComponent mAnimComponent;
};

void Character::Update()
{
	// Update state machine
	mStateMachine.ProcessStateTransitions();
	mStateMachine.UpdateStates();
}

struct SharedStates
{
	// These states can be shared by state machines with Character-derived owners

	struct BaseState : StateWithOwner<Character>
	{
	};

	struct PlayAnim_Done : BaseState
	{
	};

	struct PlayAnim : BaseState
	{
		struct Args : StateArgs
		{
			Args(const char* animName
				, bool loop = true
				, const Transition& doneTransition = SiblingTransition<PlayAnim_Done>()
				)
				: animName(animName)
				, loop(loop)
				, doneTransition(doneTransition)
			{}

			const char* animName;
			bool loop;
			Transition doneTransition;
		};

		virtual void OnEnter(const Args& args)
		{
			Owner().mAnimComponent.PlayAnim(args.animName, args.loop);
			mDoneTransition = args.doneTransition;
		}

		virtual Transition GetTransition()
		{
			if (Owner().mAnimComponent.IsFinished())
				return mDoneTransition;

			return NoTransition();
		}

		Transition mDoneTransition;
	};
};

////////////////////// Hero //////////////////////

class Hero : public Character
{
public:
	Hero();

	// Public to simplify sample
	bool mAttack;

private:
	friend struct HeroStates;
};


struct HeroStates
{
	struct BaseState : StateWithOwner<Hero, SharedStates::BaseState>
	{
	};

	typedef SharedStates::PlayAnim_Done PlayAnim_Done;
	typedef SharedStates::PlayAnim PlayAnim;

	struct Alive : BaseState
	{
		virtual Transition GetTransition()
		{
			return InnerEntryTransition<Stand>();
		}
	};

	struct Stand : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().mAttack)
			{
				Owner().mAttack = false;
				return SiblingTransition<Attack>();
			}

			return NoTransition();
		}
	};

	struct Attack : BaseState
	{
		virtual Transition GetTransition()
		{
			if (IsInInnerState<PlayAnim_Done>())
				return SiblingTransition<Stand>();

			return InnerEntryTransition<PlayAnim>(PlayAnim::Args("Attack_1", false));
		}
	};
};

Hero::Hero()
	: mAttack(false)
{
	mStateMachine.Initialize<HeroStates::Alive>(this);
	mStateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
}


////////////////////// Enemy //////////////////////

class Enemy : public Character
{
public:
	Enemy();

	// Public to simplify sample
	bool mAttack;

private:
	friend struct EnemyStates;
};

struct EnemyStates
{
	struct BaseState : StateWithOwner<Enemy, SharedStates::BaseState>
	{
	};

	typedef SharedStates::PlayAnim_Done PlayAnim_Done;
	typedef SharedStates::PlayAnim PlayAnim;

	struct Alive : BaseState
	{
		virtual Transition GetTransition()
		{
			return InnerEntryTransition<Stand>();
		}
	};

	struct Stand : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().mAttack)
			{
				Owner().mAttack = false;
				return SiblingTransition<Attack>();
			}

			return NoTransition();
		}
	};

	struct Attack : BaseState
	{
		virtual Transition GetTransition()
		{
			if (IsInInnerState<PlayAnim_Done>())
				return SiblingTransition<Stand>();

			return InnerEntryTransition<PlayAnim>(PlayAnim::Args("Attack_1", false));
		}
	};
};

Enemy::Enemy()
	: mAttack(false)
{
	mStateMachine.Initialize<EnemyStates::Alive>(this);
	mStateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
}


////////////////////// main //////////////////////

int main()
{
	Hero hero;
	hero.Update();
	hero.mAttack = true;
	hero.Update();

	Enemy enemy;
	enemy.Update();
	enemy.mAttack = true;
	enemy.Update();
}

In this example, we've introduced a new Character base class that both Hero and Enemy derive from. We've moved some of the common members into Character, such as the StateMachine and AnimComponent data members. Now that both Hero and Enemy derive from Character, the states in SharedStates are no longer template classes; instead, they now derive from StateWithOwner<Character>. Notice how we no longer have to deal with C++ ADL rules. The states simply access their owner type, Character, via the Owner() member.

Consequently, the typedefs for the shared states in both HeroStates and EnemyStates has also been simplified as we no longer need to specify the owner type as a template parameter:

	typedef SharedStates::PlayAnim_Done PlayAnim_Done;
	typedef SharedStates::PlayAnim PlayAnim;

There is one final difference between this example and the one from the last section. Take a look at how the BaseState structs are defined in both HeroStates and EnemyStates:

struct HeroStates
{
	struct BaseState : StateWithOwner<Hero, SharedStates::BaseState>
	{
	};

	<snip>
};

struct EnemyStates
{
	struct BaseState : StateWithOwner<Enemy, SharedStates::BaseState>
	{
	};

	<snip>
};

Notice how we specify SharedStates::BaseState as a second template parameter to StateWithOwner. This second template parameter is an optional parameter that specifies StateWithOwner's base class:

namespace hsm {

template <typename OwnerType, typename StateBaseType = State>
struct StateWithOwner : StateBaseType

<snip>

};

As you can see, by default, StateWithOwner will derive from hsm::State, the base class for all States in HSM. In our example, we choose, instead, to derive from SharedStates::BaseState. For example, the inheritance chain for HeroStates::BaseState looks like this (from base to most-derived):

Inheritance Chain
hsm::State
hsm::StateWithOwner
SharedStates::BaseState
hsm::StateWithOwner<Hero, SharedStates::BaseState>
HeroStates::BaseState

Effectively, we've simply made sure to derive HeroStates::BaseState from SharedStates::BaseState. Is this necessary? No, not in our example. However, by doing this, we can now add functions to SharedStates::BaseState that would be accessible by all states in both HeroStates and EnemyStates. So not only are we able to share states across our state machines, but also functions.

Sharing State Machines (State Overrides)

In the previous section, we learned how to share states across different state machines. This is a very useful technique that works well for leaf states - that is, states that are pushed deeper on the stack. However, it's not always easy to generalize the more outer states of state machines. In the previous section's example where Hero and Enemy that both derive from Character, the state machines for both classes are very similar. It would be nice to be able to share a core state machine structure between the two classes, while allowing each one to override specific states. In this section, we will take a look at how to achieve exactly that by using the state override feature of HSM:

// state_overrides.cpp

#include "hsm/statemachine.h"

using namespace hsm;

////////////////////// Character //////////////////////

class Character
{
public:
	Character();
	void Update();

	// Public to simplify sample
	bool mAttack;
	bool mJump;

protected:
	friend struct CharacterStates;
	StateMachine mStateMachine;
};

struct CharacterStates
{
	struct BaseState : StateWithOwner<Character>
	{
	};

	struct PlayAnim_Done : BaseState
	{
	};

	struct Alive : BaseState
	{
		virtual Transition GetTransition()
		{
			return InnerEntryTransition<Stand>();
		}
	};

	struct Stand : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().mAttack)
			{
				Owner().mAttack = false;
				return SiblingTransition(GetStateOverride<Attack>());
			}

			if (Owner().mJump)
			{
				Owner().mJump = false;
				return SiblingTransition(GetStateOverride<Jump>());
			}

			return NoTransition();
		}
	};

	struct Attack : BaseState
	{
		virtual Transition GetTransition()
		{
			return SiblingTransition<Stand>();
		}
	};

	struct Jump : BaseState
	{
		virtual Transition GetTransition()
		{
			return SiblingTransition<Stand>();
		}
	};
};

Character::Character()
	: mAttack(false)
	, mJump(false)

{
	mStateMachine.Initialize<CharacterStates::Alive>(this);
	mStateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
}

void Character::Update()
{
	// Update state machine
	mStateMachine.ProcessStateTransitions();
	mStateMachine.UpdateStates();
}


////////////////////// Hero //////////////////////

class Hero : public Character
{
public:
	Hero();

private:
	friend struct HeroStates;
};

struct HeroStates
{
	struct BaseState : StateWithOwner<Hero, CharacterStates::BaseState>
	{
	};

	struct Attack : BaseState
	{
		virtual Transition GetTransition()
		{
			return SiblingTransition<CharacterStates::Stand>();
		}
	};

	struct Jump : BaseState
	{
		virtual Transition GetTransition()
		{
			return SiblingTransition<CharacterStates::Stand>();
		}
	};
};

Hero::Hero()
{
	mStateMachine.AddStateOverride<CharacterStates::Attack, HeroStates::Attack>();
	mStateMachine.AddStateOverride<CharacterStates::Jump, HeroStates::Jump>();
}


////////////////////// Enemy //////////////////////

class Enemy : public Character
{
public:
	Enemy();

private:
	friend struct EnemyStates;
};


struct EnemyStates
{
	struct BaseState : StateWithOwner<Enemy, CharacterStates::BaseState>
	{
	};

	struct Attack : BaseState
	{
		virtual Transition GetTransition()
		{
			return SiblingTransition<CharacterStates::Stand>();
		}
	};
};

Enemy::Enemy()
{
	mStateMachine.AddStateOverride<CharacterStates::Attack, EnemyStates::Attack>();
}


////////////////////// main //////////////////////

int main()
{
	Hero hero;
	hero.Update();
	hero.mAttack = true;
	hero.Update();
	hero.mJump = true;
	hero.Update();

	printf("\n");

	Enemy enemy;
	enemy.Update();
	enemy.mAttack = true;
	enemy.Update();
	enemy.mJump = true;
	enemy.Update();
}

In the example above, we have a single state machine defined for the Character class in the CharacterStates struct. This state machine looks a lot like the ones we've seen so far, except for one important difference, which can be seen in the Stand state:

	struct Stand : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().mAttack)
			{
				Owner().mAttack = false;
				return SiblingTransition(GetStateOverride<Attack>());
			}

			if (Owner().mJump)
			{
				Owner().mJump = false;
				return SiblingTransition(GetStateOverride<Jump>());
			}

			return NoTransition();
		}
	};

Rather than returning the usual SiblingTransition<Attack>(), for example, we now use an overload of SiblingTransition that accepts a runtime-defined parameter for which state to transition to, which in this case is returned by the function GetStateOverride<Attack>(). What this means is that we are asking the state machine to return a sibling transition to the CharacterStates::Attack state by default, unless an override has been defined for that state. We do this for both the Attack and Jump states, effectively providing hooks to override these specific states.

Now let's look at how these states are overridden. The Hero class wants to override both the Attack and Jump states, so it defines its own versions of these states in the HeroStates struct:

struct HeroStates
{
	struct BaseState : StateWithOwner<Hero, CharacterStates::BaseState>
	{
	};

	struct Attack : BaseState
	{
		virtual Transition GetTransition()
		{
			return SiblingTransition<CharacterStates::Stand>();
		}
	};

	struct Jump : BaseState
	{
		virtual Transition GetTransition()
		{
			return SiblingTransition<CharacterStates::Stand>();
		}
	};
};

To override the versions of these states defined in CharacterStates, Hero explicitly does so in its constructor:

Hero::Hero()
{
	mStateMachine.AddStateOverride<CharacterStates::Attack, HeroStates::Attack>();
	mStateMachine.AddStateOverride<CharacterStates::Jump, HeroStates::Jump>();
}

The StateMachine::AddStateOverride function can be used to dynamically add an override at any time for given state machine instance, while StateMachine::RemoveStateOverride can be used to remove an override. In this example, we want to permanently override the states, so we do this once in the constructor.

The Enemy class is implemented similarly to Hero, except it only overrides the Attack state.

Let's take a look at the output from this program:

HSM_1_TestHsm: Init    : struct CharacterStates::Alive
HSM_1_TestHsm:  Entry   : struct CharacterStates::Stand
HSM_1_TestHsm:  Sibling : struct HeroStates::Attack
HSM_1_TestHsm:  Sibling : struct CharacterStates::Stand
HSM_1_TestHsm:  Sibling : struct HeroStates::Jump
HSM_1_TestHsm:  Sibling : struct CharacterStates::Stand

HSM_1_TestHsm: Init    : struct CharacterStates::Alive
HSM_1_TestHsm:  Entry   : struct CharacterStates::Stand
HSM_1_TestHsm:  Sibling : struct EnemyStates::Attack
HSM_1_TestHsm:  Sibling : struct CharacterStates::Stand
HSM_1_TestHsm:  Sibling : struct CharacterStates::Jump
HSM_1_TestHsm:  Sibling : struct CharacterStates::Stand

From this output, we can clearly see how both the Hero and Enemy state overrides end up being transitioned to from the Stand state.

The mechanism behind state overrides isn't particularly complicated. When you add an override, internally the state machine just stores this mapping of source to target state, and when you call GetStateOverride<SourceState>, the mapped state is returned if found, otherwise the source state is returned.

You might be wondering why we need to bother with calling GetStateOverride explicitly - why doesn't the state machine just always check the mapping for every transition? There are two reasons: first, we don't want to pay the performance penalty of looking up state overrides for every transition, especially if we don't use this feature. Second, because the state override hooks are explicit, it makes it easier to understand a state machine and know where states might be overridden. This is very much analogous to how class functions must be explicitly declared as virtual to be overridden in derived classes.

Parallel State Machines

As we have seen, using a hierarchical state machine is a useful tool to represent multiple states at different levels of abstraction. In effect, it is very much like running a non-hierarchical state machine where any state itself may run another state machine, and so on. Although we are effectively running multiple state machines, the existence of inner machines depends on the outer state machines. Put another way: an inner state cannot "survive" across outer state transitions. Sometimes we need that, and the solution is to run multiple state machines in parallel.

HSM does not have any special support for parallel state machines. All you need to do is run multiple instances of hsm::StateMachine; the tricky part is keeping them in sync. In this section, we'll take a look at one way to do that using the features of HSM we've seen so far.

The motivation behind the example below is to implement a character controller with the following gameplay constraints:

Our character can stand, move, jump, and reload its weapon;
Reloading cannot happen while jumping. Thus, if the character is standing or moving around, it can reload; if it's jumping, it can't reload; and if it starts reloading while standing/moving, and then jumps, the reload is cancelled.

The key here is that reloading is a parallel process: you can start the reload process while toggling between standing and moving at any time; however, if you jump, reloading is cancelled and cannot happen again until jumping is finished.

In our example, we implement two state machines to solve this problem: a "full body" state machine that controls the full body actions and animations, like stand/move/jump; and an "upper body" state machine that controls upper-body actions and animations like reloading.

// parallel_state_machines.cpp

#include "hsm/statemachine.h"

using namespace hsm;

class Hero
{
public:
	Hero();
	void Update();

	// Public to simplify sample
	bool mMove;
	bool mJump;
	bool mReload;

private:

	// Functions that simulate playing an animation that always lasts 3 frames
	void PlayAnim(const char*) { mAnimFrame = 0; }
	bool IsAnimDone() const { return mAnimFrame >= 2; }

	void ReloadWeapon() { printf(">>> WEAPON RELOADED!\n"); }

	friend struct HeroFullBodyStates;
	friend struct HeroUpperBodyStates;
	StateMachine mStateMachines[2];

	hsm::StateValue<bool> mUpperBodyEnabled;

	int mAnimFrame;
};

struct HeroFullBodyStates
{
	struct BaseState : StateWithOwner<Hero>
	{
	};

	struct Alive : BaseState
	{
		virtual void OnEnter()
		{
			// By default, upper body is enabled
			SetStateValue(Owner().mUpperBodyEnabled) = true;
		}

		virtual Transition GetTransition()
		{
			return InnerEntryTransition<Stand>();
		}
	};

	struct Stand : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().mMove)
			{
				return SiblingTransition<Move>();
			}

			if (Owner().mJump)
			{
				Owner().mJump = false;
				return SiblingTransition<Jump>();
			}

			return NoTransition();
		}
	};

	struct Move : BaseState
	{
		virtual Transition GetTransition()
		{
			if (!Owner().mMove)
			{
				return SiblingTransition<Stand>();
			}

			if (Owner().mJump)
			{
				Owner().mJump = false;
				return SiblingTransition<Jump>();
			}
			
			return NoTransition();
		}
	};

	struct Jump : BaseState
	{
		virtual void OnEnter()
		{
			// Don't allow upper body to do anything while jumping
			SetStateValue(Owner().mUpperBodyEnabled) = false;
			Owner().PlayAnim("Jump");
		}

		virtual Transition GetTransition()
		{
			if (Owner().IsAnimDone())
			{
				if (!Owner().mMove)
				{
					return SiblingTransition<Stand>();
				}
				else
				{
					return SiblingTransition<Move>();
				}
			}

			return NoTransition();
		}
	};
};

struct HeroUpperBodyStates
{
	struct BaseState : StateWithOwner < Hero >
	{
	};

	struct Disabled : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().mUpperBodyEnabled)
				return SiblingTransition<Enabled>();

			return NoTransition();
		}
	};

	struct Enabled : BaseState
	{
		virtual Transition GetTransition()
		{
			if (!Owner().mUpperBodyEnabled)
				return SiblingTransition<Disabled>();

			return InnerEntryTransition<Idle>();
		}
	};

	struct Idle : BaseState
	{
		virtual void OnEnter()
		{
			Owner().PlayAnim("Idle");
		}

		virtual Transition GetTransition()
		{
			if (Owner().mReload)
			{
				Owner().mReload = false;
				return SiblingTransition<Reload>();
			}

			return NoTransition();
		}
	};

	struct Reload : BaseState
	{
		virtual Transition GetTransition()
		{
			if (IsInInnerState<Reload_Done>())
				return SiblingTransition<Idle>();

			return InnerEntryTransition<Reload_PlayAnim>();
		}
	};

	struct Reload_PlayAnim : BaseState
	{
		virtual void OnEnter()
		{
			Owner().PlayAnim("Reload");
		}

		virtual Transition GetTransition()
		{
			if (Owner().IsAnimDone())
				return SiblingTransition<Reload_Done>();

			return NoTransition();
		}
	};

	struct Reload_Done : BaseState
	{
		virtual void OnEnter()
		{
			// Only once we're done the anim to we actually reload our weapon
			Owner().ReloadWeapon();
		}
	};
};

Hero::Hero()
	: mMove(false)
	, mJump(false)
	, mReload(false)
	, mUpperBodyEnabled(false)

{
	mStateMachines[0].Initialize<HeroFullBodyStates::Alive>(this);
	mStateMachines[0].SetDebugInfo("FullBody ", TraceLevel::Basic);

	mStateMachines[1].Initialize<HeroUpperBodyStates::Disabled>(this);
	mStateMachines[1].SetDebugInfo("UpperBody", TraceLevel::Basic);
}

void Hero::Update()
{
	// Update state machines
	for (int i = 0; i < 2; ++i)
	{
		mStateMachines[i].ProcessStateTransitions();
		mStateMachines[i].UpdateStates();
	}

	++mAnimFrame;
}

////////////////////// main //////////////////////

int main()
{
	Hero hero;
	
	int whichUpdate = 0;

	printf(">>> Update %d\n", whichUpdate++);
	hero.Update();

	printf(">>> Input: Reload\n");
	hero.mReload = true;

	printf(">>> Update %d\n", whichUpdate++);
	hero.Update();

	printf(">>> Input: Move\n");
	hero.mMove = true;

	printf(">>> Update %d\n", whichUpdate++);
	hero.Update();

	printf(">>> Update %d\n", whichUpdate++);
	hero.Update();

	printf(">>> Input: Reload\n");
	hero.mReload = true;

	printf(">>> Update %d\n", whichUpdate++);
	hero.Update();

	printf(">>> Input: Jump\n");
	hero.mJump = true;

	printf(">>> Update %d\n", whichUpdate++);
	hero.Update();

	printf(">>> Update %d\n", whichUpdate++);
	hero.Update();

	printf(">>> Update %d\n", whichUpdate++);
	hero.Update();
}

The first thing to notice is that the Hero class contains an array of 2 state machine instances, StateMachine mStateMachines[2], which are initialized in the constructor, and updated in Hero's Update function:

Hero::Hero()
<snip>
{
	mStateMachines[0].Initialize<HeroFullBodyStates::Alive>(this);
	mStateMachines[0].SetDebugInfo("FullBody ", TraceLevel::Basic);

	mStateMachines[1].Initialize<HeroUpperBodyStates::Disabled>(this);
	mStateMachines[1].SetDebugInfo("UpperBody", TraceLevel::Basic);
}

void Hero::Update()
{
	// Update state machines
	for (int i = 0; i < 2; ++i)
	{
		mStateMachines[i].ProcessStateTransitions();
		mStateMachines[i].UpdateStates();
	}
<snip>
}

The implementation of each state machine can be found in the HeroFullBodyStates struct and the HeroUpperBodyStates struct. Let's take a look at the plots of both state machines:

The FullBody state machine:

parallel_state_machines_fullbody

The UpperBody state machine:

parallel_state_machines_upperbody

The FullBody state machine is straightforward: it controls moving, standing, and jumping. The UpperBody state machine is slightly more complex: the upper body is either enabled or disabled; in a real game, being "enabled" would mean animations could override the upper part of the character's skeleton, otherwise when "disabled", the full body animation controls the entire skeleton. While enabled, the UpperBody is either Idle (playing an idle animation), or in the Reload state.

The Reload state starts off a sequence where it first enters Reload_PlayAnim, responsible for playing a reload animation, before it siblings to Reload_Done, which is when the character's weapon is actually reloaded. If the animation doesn't get a chance to finish playing, then the weapon does not get reloaded. This is exactly what would happen if the player were to jump while the reload animation is playing. To illustrate this situation, the example code implements animation playback as always taking 3 frames to complete (see mAnimFrame).

To synchronize the FullBody and UpperBody state machines, we use a StateValue: hsm::StateValue<bool> mUpperBodyEnabled. This boolean StateValue is set to true while the FullBody is in the Alive state, and is only set to false while in the Jump state (one of Alive's inner state). The UpperBody state machine simply polls this StateValue to determine whether it should be in the Enabled or Disabled state.

Now let's see this code in action. Rather than simply show the output from the code in one block, we will mix snippets of the code in main with the corresponding output, and explain each part.

Code from main:

	Hero hero;
	
	int whichUpdate = 0;

	printf(">>> Update %d\n", whichUpdate++);
	hero.Update();

Output:

>>> Update 0
HSM_1_FullBody : Init    : struct HeroFullBodyStates::Alive
HSM_1_FullBody :  Entry   : struct HeroFullBodyStates::Stand
HSM_1_UpperBody: Init    : struct HeroUpperBodyStates::Disabled
HSM_1_UpperBody: Sibling : struct HeroUpperBodyStates::Enabled
HSM_1_UpperBody:  Entry   : struct HeroUpperBodyStates::Idle

At this point, we've created a Hero with default values and have updated it once. Here we see how the FullBody state machine ends up in Alive.Stand, while the UpperBody state machine ends up in Enabled.Idle.

Code from main (continued):

	printf(">>> Input: Reload\n");
	hero.mReload = true;

	printf(">>> Update %d\n", whichUpdate++);
	hero.Update();

Output:

>>> Input: Reload
>>> Update 1
HSM_1_UpperBody:  Sibling : struct HeroUpperBodyStates::Reload
HSM_1_UpperBody:   Entry   : struct HeroUpperBodyStates::Reload_PlayAnim

We've initiated a reload, which results in the UpperBody state machine transitioning from Idle to Reload. Note that it starts up the reload sequence by playing a reload animation in the Reload_PlayAnim state. In our example, this will take 2 more Update calls to complete.

Code from main (continued):

	printf(">>> Input: Move\n");
	hero.mMove = true;

	printf(">>> Update %d\n", whichUpdate++);
	hero.Update();

Output:

>>> Input: Move
>>> Update 2
HSM_1_FullBody :  Sibling : struct HeroFullBodyStates::Move

Now while reloading, we decide to start moving. This simply affects the FullBody state machine, making it sibling from Stand to Move. Note that this has no affect on the UpperBody state machine, which happily continues reloading.

Code from main (continued):

	printf(">>> Update %d\n", whichUpdate++);
	hero.Update();

Output:

>>> Update 3
HSM_1_UpperBody:   Sibling : struct HeroUpperBodyStates::Reload_Done
>>> WEAPON RELOADED!
HSM_1_UpperBody:  Sibling : struct HeroUpperBodyStates::Idle

With one more update, the reload sequence is now complete. We see that the UpperBody state machine siblings to Reload_Done, which triggers the weapon reload, and then the Reload outer state siblings back to Idle.

Code from main (continued):

	printf(">>> Input: Reload\n");
	hero.mReload = true;

	printf(">>> Update %d\n", whichUpdate++);
	hero.Update();

Output:

>>> Input: Reload
>>> Update 4
HSM_1_UpperBody:  Sibling : struct HeroUpperBodyStates::Reload
HSM_1_UpperBody:   Entry   : struct HeroUpperBodyStates::Reload_PlayAnim

Now we initiate another reload, which once again results in the UpperBody state machine starting the reload sequence.

Code from main (continued):

	printf(">>> Input: Jump\n");
	hero.mJump = true;

	printf(">>> Update %d\n", whichUpdate++);
	hero.Update();

Output:

>>> Input: Jump
>>> Update 5
HSM_1_FullBody :  Sibling : struct HeroFullBodyStates::Jump
HSM_1_UpperBody: Sibling : struct HeroUpperBodyStates::Disabled

This time, we decide to jump while reloading. As we saw earlier, the Jump state disables the upper body state machine via the mUpperBodyEnabled StateValue. The result is that as the FullBody state machine enters the Jump state, the UpperBody enters the Disabled state, effectively stopping the Reload state from finishing.

Code from main (continued):

	printf(">>> Update %d\n", whichUpdate++);
	hero.Update();

	printf(">>> Update %d\n", whichUpdate++);
	hero.Update();

Output:

>>> Update 6
>>> Update 7
HSM_1_FullBody :  Sibling : struct HeroFullBodyStates::Move
HSM_1_UpperBody: Sibling : struct HeroUpperBodyStates::Enabled
HSM_1_UpperBody:  Entry   : struct HeroUpperBodyStates::Idle

The last two update calls allow the Jump state to complete its animation, which results in Jump sibling back to Move, and the UpperBody state machine is now re-enabled and enters Idle.

Although this example is minimal, even more complex set of parallel state machines are typically implemented in a similar fashion. One important thing to note is that the update order of the parallel state machines matter: in this case, we make sure to update the FullBody before the UpperBody, because the former effectively controls the latter. In practice, there is usually a "master" state machine, and one or more "slave" state machines; just make sure to update the master first.

Chapter 5. Best Practices

Introduction

By now you should be fairly comfortable with how HSM works, and have been exposed to many different techniques on how to use it. This chapter will focus on some best practices to follow when developing state machines with HSM. Many of these were already covered to some degree in the previous chapters, so the aim of this chapter is to provide a high level summary of what you should or should not do.

Before we begin, it's important to understand that these best practices are derived from years of experience implementing state machines in real software. Having said that, they are not hard and fast rules, and in certain cases, it may make sense to go against them. As usual, you'll have to use your judgement.

Prefer InnerEntry + Sibling to Inner

Inner transitions are almost never the right type of transition to use. The only times it makes sense to use Inner transitions is when a state needs to force transitions to specific inner states immediately. Typically, these inner states map directly to an enum value or to a series of simple if-else conditions, for example:

	struct Locomotion : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().PressedMove())
				return InnerTransition<Move>();
			else
				return InnerTransition<Stand>();
		}
	};

The key thing to realize about Inner transitions is that inner states have no control over when and where transitions between siblings occur. The outer state is the "boss". This becomes problematic as soon as you want an inner state to have some control over its transitions; for instance, in the example above, let's say that when we stop pressing the move input, we want the character to play a stopping animation before going to Stand. Using Inner transitions would make this very awkward:

	struct Locomotion : BaseState
	{
		bool mStopping;
	
		Locomotion() : mStopping(false) {}
	
		virtual Transition GetTransition()
		{
			if (Owner().PressedMove())
			{
				return InnerTransition<Move>();
			}
			else if (IsInInnerState<Move>()) // We were in Move and just stopped pressing move input
			{
				mStopping = true;
			}
			
			if (mStopping && IsInInnerState<Stop_Done>()) // Stop animation complete?
			{
				mStopping = false;
			}
			
			if (mStopping)
			{
				return InnerTransition<Stop>();
			}
			
			return InnerTransition<Stand>();
		}
	};
	
	struct Stand : BaseState
	{
		virtual void OnEnter()
		{
			PlayAnim("Stand");
		}
	};

	struct Move : BaseState
	{
		virtual void OnEnter()
		{
			PlayAnim("Move");
		}
	};
	
	struct Stop : BaseState	
	{
		virtual void OnEnter()
		{
			PlayAnim("Stop");
		}
		
		virtual Transition GetTransition()
		{
			if (IsAnimDone())
				return SiblingTransition<Stop_Done>();
			
			return NoTransition();
		}
	};
	
	struct Stop_Done : BaseState
	{
	};

The transition logic above is not easy to follow. The main problem is that the outer state, Locomotion, is deeply coupled with the transition logic of its inner states. Let's rewrite the above logic using InnerEntry + Sibling transitions:

	struct Locomotion : BaseState
	{
		virtual Transition GetTransition()
		{
			return InnerEntryTransition<Stand>();
		}
	};
	
	struct Stand : BaseState
	{
		virtual void OnEnter()
		{
			PlayAnim("Stand");
		}
	
		virtual Transition GetTransition()
		{
			if (Owner().PressedMove())
				return SiblingTransition<Move>();
				
			return NoTransition();
		}
	};

	struct Move : BaseState
	{
		virtual void OnEnter()
		{
			PlayAnim("Move");
		}
	
		virtual Transition GetTransition()
		{
			if (Owner().PressedMove())
				return SiblingTransition<Stop>();
				
			return NoTransition();
		}
	};
	
	struct Stop : BaseState	
	{
		virtual void OnEnter()
		{
			PlayAnim("Stop");
		}
	
		virtual Transition GetTransition()
		{
			if (Owner().PressedMove())
				return SiblingTransition<Move>();
				
			if (IsAnimDone())
				return SiblingTransition<Stand>();
				
			return NoTransition();
		}
	};

Understanding the transition logic in this second version is much easier. The three states, Stand, Move, and Stop, form a flat state machine that take care of transitioning between each other. The outer state, Locomotion, simply chooses the initial state, Stand in this case, and doesn't interfere afterwards.

In general, InnerEntry transitions coupled with Sibling transitions is almost always the best way to manage a state machine. The main reason is that it allows inner states full control over its sibling transitions. In effect, when an outer state uses an InnerEntry transition, it is starting up a new flat state machine. It is easier to both reason about and manipulate flat state machines. Using InnerEntry + Sibling transitions allows you to build your hierarchical state machine as a series of flat state machines, where certain states push new flat state machines.

Nest state-related variables as deeply as possible

When working with HSM, you often find yourself wondering where to declare state-related variables. In general, try to nest your variables as deeply as possible; that is, prefer the following order from most deeply nested to least:

State : if your variable is only used by a single state, make it a data member of the state. This way, the lifetime of the variable is tied to that of the state instance.
Outer State : if your variable must be accessed by a set of states, make it a data member of a common outer state. This is described in detail in the section Storing Data on Cluster Root State.
Owner : if your variable must be accessed by many states in your state machine, make it a data member of the owner class.

Note that if you find yourself needing to often reset a state-related variable declared on the owner class because it would otherwise contain "stale" data, you are likely in a situation where this variable should be more deeply nested - perhaps on a state cluster. If this is not the case, consider using a state value instead to have its value automatically reset to a default value on state exit.

Clean up in cluster root state

One common situation you may come across when implementing state machines is one where you have a sequence of sibling states, where one state makes a change, and a separate state "undoes" this change. In such a situation, there's a possibility that the state that is meant to undo the change may never be reached due to an outer state transition. The strategy to avoid such a problem is to make sure to perform the undo code in an outer state - typically in its OnExit.

To better explain this best practice, let's take a look at an example:

// cluster_root_clean_up.cpp

#include "hsm/statemachine.h"

using namespace hsm;

class Character
{
public:
	Character();
	void Update();

private:
	bool IsHurt() const { return false; }
	bool ShouldGetOnLadder() const { return true; }
	bool ShouldGetOffLadder() const { return false; }
	void AttachToLadder() {}
	void DetachFromLadder() {}

	friend struct CharacterStates;
	StateMachine mStateMachine;
};

struct CharacterStates
{
	struct BaseState : StateWithOwner<Character>
	{
	};

	struct Alive : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().IsHurt())
				return SiblingTransition<Hurt>();

			return InnerEntryTransition<Stand>();
		}
	};

	struct Hurt : BaseState
	{
	};

	struct Stand : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().ShouldGetOnLadder())
				return SiblingTransition<Ladder>();

			return NoTransition();
		}
	};

	struct Ladder : BaseState
	{
		virtual Transition GetTransition()
		{
			return InnerEntryTransition<Ladder_GetOn>();
		}
	};

	struct Ladder_GetOn : BaseState
	{
		virtual void OnEnter()
		{
			Owner().AttachToLadder();
		}

		virtual Transition GetTransition()
		{
			return SiblingTransition<Ladder_OnLadder>();
		}
	};

	struct Ladder_OnLadder : BaseState
	{
		virtual Transition GetTransition()
		{
			if (Owner().ShouldGetOffLadder())
				return SiblingTransition<Ladder_GetOff>();
			
			return NoTransition();
		}
	};

	struct Ladder_GetOff : BaseState
	{
		virtual void OnEnter()
		{
			Owner().DetachFromLadder();
		}
	};
};

Character::Character()
{
	mStateMachine.Initialize<CharacterStates::Alive>(this);
	mStateMachine.SetDebugInfo("TestHsm", TraceLevel::Basic);
}

void Character::Update()
{
	// Update state machine
	mStateMachine.ProcessStateTransitions();
	mStateMachine.UpdateStates();
}

int main()
{
	Character character;
	character.Update();
}

In the example above, we have implemented a character controller that supports climbing ladders. Let's look at a plot of this state machine:

cluster_root_clean_up

This is a straightforward state machine: we have a state that takes care of getting our character onto a ladder, then it siblings to a state while we're on the ladder, which in turn siblings to a state that takes care of getting off the ladder. The important part to highlight is how Ladder_GetOn invokes Owner().AttachToLadder(), while Ladder_GetOff will later invoke Owner().DetachFromLadder():

	struct Ladder_GetOn : BaseState
	{
		virtual void OnEnter()
		{
			Owner().AttachToLadder();
		}
		
		<snip>
	};

	<snip>

	struct Ladder_GetOff : BaseState
	{
		virtual void OnEnter()
		{
			Owner().DetachFromLadder();
		}
	};

At the outset, there's nothing wrong with this code, and indeed it will probably work as expected most of the time. However, there is a potential problem here: what happens if the current state is Ladder_OnLadder, and suddenly outer state Alive makes a sibling transition to Hurt? If this happens, the call to Owner().DetachFromLadder() would never be made, and our character could end up in a strange and unexpected state.

The solution to this problem is to clean up in a common outer state. In this example, we could simply add a redundant call to DetachFromLadder to the Ladder cluster's root state:

	struct Ladder : BaseState
	{
		virtual void OnExit()
		{
			// In case we get booted out, make sure we're no longer attached
			Owner().DetachFromLadder();
		}
	
		virtual Transition GetTransition()
		{
			return InnerEntryTransition<Ladder_GetOn>();
		}
	};

Now there is no way for our character to be attached to a ladder when we're not in the Ladder state.

The best practice here is to make sure to clean up in a cluster's root state. Whenever you find yourself having to undo/release/clean up some operation that was performed in a sibling state, make sure to add or move this code to a common outer state.

Avoid state stack queries outside of states

In the section on state stack queries, we learned about how to use functions such as InInState to check if a state is on the stack. These query functions can be very useful; however, their use should be minimized outside of states themselves. It can be tempting to use functions like IsInState in the owner class, for instance, to perform some action every frame:

void Character::Update()
{
	if (mStateMachine.IsInState<CharacterStates::Jumping>())
	{
		ShowJumpingUI();
	}
}

Instead, it is almost always a better idea to push this code into the states themselves:

	struct Jumping : BaseState
	{
		virtual void Update()
		{
			Owner().ShowJumpUI();
		}
	}

The reasons why you should avoid state stack query functions outside of states include the following:

It reduces coupling between code outside of states and the states themselves. This allows you to more easily rename states, refactor them, etc.;
It unifies state-driven code in one place, rather than splitting it across states and sections of code outside of the state machine. Indeed, one of the main purposes of HSM is to allow you to drive state-specific code directly within the states themselves;
It's better for performance. The state stack query functions must traverse the state stack and compare state identifiers against the input one. This cost must be paid even when that state is not on the stack, and is worse in this case since the entire stack must be traversed. On the other hand, moving the code into the state means it only executes when that state is on the stack, and there is no extra cost for querying the state stack.

One potentially valid use case for using state stack query functions outside of states is when you need to communicate your current state without giving direct access to the state machine. For instance, we may want to add a public function to Character such as IsJumping, which we'd implement as follows:

class Character
{
public:
	bool IsJumping() const;
};

bool Character::IsJumping const
{
	return mStateMachine.IsInState<CharacterStates::Jumping>();
}

Even in this case, it may be preferable to have the Jumping state simply set a bool (or better yet, a StateValue) on the Owner to signify that it's jumping as this would reduce the dependency on state names.

Make each state machine update count

When authoring a state machine, try to minimize the number of updates required for states to transition between each other. Concretely, if a state A needs to get to D, ideally it would be best if it went from A -> B -> C - > D in a single call to StateMachine::ProcessStateTransitions, rather than multiple calls. If it takes multiple calls, then these "in-between" states may be more difficult to reason about and handle correctly.

To understand how do this, it's important to understand how StateMachine::ProcessStateTransitions works, which was covered in detail in Chapter 3. The idea is to take advantage of the fact that StateMachine::ProcessStateTransitions will only end once the state stack has settled. This means that in order to minimize the number of times you need to call this function to get from one state to another, you should:

Compute transition-related data in a state's OnEnter rather than its Update. The idea is that when a state is transitioned to, its OnEnter will get called, then GetTransition will be called on it (in fact, GetTransition will be called on all states from outermost to innermost). If you can determine what transition the state needs to make in its OnEnter, its GetTransition will be able to act on it immediately. If this decision is made in Update instead, then this transition can only be made on the subsequent StateMachine::ProcessStateTransitions. This is because State::Update is not called by StateMachine::ProcessStateTransitions, but rather by StateMachine::UpdateStates, which is typically called immediately following the call to ProcessStateTransitions.
Prefer to use transient states, such as Done States, over writing to shared variables. Transitioning to a transient state will trigger another GetTransition pass on the state stack, allowing outer states to make more transitions based on the existence of these transient states.

Of course, in some cases, you have no choice but to delay transitions between states, such as when you need to break infinite transition cycles, as shown in the section on Deferred Transitions. However, this is an exception, and you should try to avoid using this technique unless you really need to.

Wiki

Home

Single Page Version

HSM Book (Single Page)

Table of Contents

Chapter 1. Getting Started

Chapter 2. The Basics

Chapter 3. The H in HSM

Chapter 4. Advanced Techniques

Chapter 5. Best Practices

Chapter 1. Getting Started

About HSM

Benefits of using HSM

License

Installation

Build Environment

Configuration

RTTI

Tools

plotHsm

Book Samples

Chapter 2. The Basics

Introduction

The Simplest State Machine

States and Transitions

Improving Readability

State OnEnter and OnExit

OnEnter/OnExit vs Constructor/Destructor

ProcessStateTransitions

UpdateStates

Ownership

Basic Usage

Easier Owner Access

Accessing Owner's Private Members

Storing Data

Chapter 3. The H in HSM

Introduction

Why Use Hierarchical State Machines?

Drawing HSMs

Inner and Outer States

The State Stack

InnerEntry Transitions

Inners and Trace Output

Inner Transitions

State Stack Queries

ProcessStateTransitions Revisited

Algorithm

Rationale

Implications

UpdateStates Revisited

Chapter 4. Advanced Techniques

Introduction

StateValue

Without StateValue

With StateValue

How does it work?

Initializing StateValues

Reading StateValues

Modifying StateValues

When to modify StateValues

State Arguments

Storing Data on Cluster Root State

Restarting States

Selector States

Done States

Sharing Functions Across States

Deferred Transitions

Reusable States

Sharing HSMs

Sharing states with unrelated owners

Sharing states with related owners

Sharing State Machines (State Overrides)

Parallel State Machines

Chapter 5. Best Practices

Introduction

Prefer InnerEntry + Sibling to Inner

Nest state-related variables as deeply as possible

Clean up in cluster root state

Avoid state stack queries outside of states

Make each state machine update count

Wiki

Book