The Gist of Hierarchical FSM

Alex J. Champandard on September 5, 2007

This previous article discussed how traditional finite state machines don’t scale very well. FSM don’t provide ways for reusing logic in different contexts, which leaves you with a choice of two evils: redundancy or complicatedness.

Game developers have found many different solutions to this problem, but one is most popular these days.

Figure: A simple hierarchical state machine.

Introducing HFSM

Hierarchical finite state machines offer some help for reusing logic. The design process is very similar to non-hierarchical finite state machines:

  1. You build the logic state by state, connecting them up with transitions bottom up.

  2. While creating new states, you may group them together to share transitions.

This gives you a simple way to avoid duplicating transition logic… For some extra background behind these ideas, the original paper on HFSM can be found here:

Statecharts: A Visual Formalism for Complex Systems
D. Harel
Science of Computer Programming 8, 1987

Super-States and Generalized Transitions

Harel uses the term super-states to indicate groups of states. These super-states too can have transitions, which theoretically allows you to prevent redundant transitions by applying them only once to super-states rather than each state individually. These are called generalized transitions.

Because Harel intended this as a visual tool, states typically only fall within one super-state, so you end up with a strict hierarchy like folders on a hard-disk. In most game implementations of HFSM, you can’t have states within multiple super-states either. So, in effect, everything is organised cleanly within the correct folders.

Is this Good Enough?

HFSM certainly provide a way to reuse transitions, but it’s still not an ideal solution. The problem is that:

  • Reusing transitions isn’t trivial to achieve, and requires a lot of thought when you have to create logic for many different contexts (e.g. dynamic goals, actor status).

  • Editing transitions manually is rather tedious in the first place.

Another solution is to focus on making individual states modular so they can be easily reused as-is different parts of the logic. Behavior trees take this approach (as do certain hybrid HFSM implementations), and you’ll learn about them in the next article in this series.

Discussion 2 Comments

tylo on February 13th, 2011

Is there a next article in this series? I'd be interested to know.

niello on March 11th, 2011

"Understanding Behavior Trees" seems to be the next article. Search it here. Not sure why link isn't provided in HFSM article.

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!