Choosing a Hierarchical FSM or a Hierarchy of Nested FSMs?

Alex J. Champandard on October 21, 2007

Sundays at is dedicated to explaining problems visually using sketches. This article extrapolates from last week’s discussion (thanks Sergio) and explains different ways of looking at hierarchies.

Most developers say they use a “HFSM” in their games. But you’ll be surprised how different their technology can be — despite them using the same name to describe it.

There are two reasons why you want a hierarchy for your finite state machine:

  1. To provide ways to re-use logic by sharing external transitions.

  2. To help split up the problem internally into sub-parts.

Granted, there’s a certain overlap between these two concepts, but yet they are orthogonal issues (you can do one without doing the other). Here are two opposing examples, one FSM for animation and the other for AI behaviors.

Using Groups of States to Share Transitions

Say you want to build a finite state machine for an animation system. In this case, you need:

  • Complete control over every low-level state in the system, so you can make sure the correct animation is played in every case.

  • A set of tools to help you reuse logic so that you don’t have too much redundancy in the transitions.

To build this kind of FSM, you do the following:

  1. You build the system as a flat state machine by default, only grouping states together to reuse transition logic.

  2. You follow the process of reusing logic by “tagging,” e.g. you can dive/sprint/crouch from this state.

  3. You think from the bottom-up deciding which transitions each state should inherit.

  4. You always edit the FSM as a whole to keep the big picture, as much of the system doesn’t make sense when broken down into small parts.

When you do this, the hierarchy becomes loose collection of states used informally to reduce redundant logic by sharing transitions.

HFSM for Animation

Making Modular FSM and Assembling them Hierarchically

Now on the other hand, assuming you want to build a FSM for high-level AI, you’d need:

  • A well-structured strict hierarchy that will scale to handle many states.

  • A logical way to break down states based on recursively decomposing tasks.

  • Fully modular states so that they can be changed locally without risking breaking the rest of the logic.

To build this kind of system, you follow these steps:

  1. You create many small modular FSMs that handle sub-parts of the problem witohut refering to any other FSM.

  2. You think from the top-down by breaking up problems into smaller modular parts.

  3. You build a tree structure that reflects the AI solving problems recursively.

  4. You design your editor as a tree editor rather than tag-based like in the animation system.

When you do this, the hierarchy becomes a strict tree of nested states, each completely encapsulated to define sub-behaviors modularly.

HFSM for Animation

Finding a Compromise

Now ideally, you want to be able to use both. But sadly, you can’t get complete control at the lowest-level if you have states that are encapsulated modularly, and vice versa. So, it’s always a trade-off!

How would you approach this problem?

Discussion 4 Comments

Sergio on October 23rd, 2007

As with all modularity, the HFSM will work as well as you can split the functionality into smaller pieces. Grouping four sub-states inside the IDLE state automatically reuses the transition to INVESTIGATE or ATTACK, effectively doing the same thing you presented in your animation FSM. You need to work on your architecture so the behaviours are grouped properly, and sharing transitions is a strong indicator that they belong together. An important factor in making an HFSM flexible enough is how sub-states communicate with their parent state. IIRC, in the original statechart representations you could put a transition at the state level (affecting all the sub-states inside) or have a specific sub-state force a transition on the parent. Also, you could have incoming transitions directed to specific sub-states. So in your example you could connect directly, say, "shoot" and "look around" (which would also force a transition from ATTACK to INVESTIGATE at the top level). With this, you can break modularity a little when you need to, and look inside states, gaining some flexibility and possibly losing some reuse opportunities. I have encountered in several occasions an FSM similar to the first sketch you presented, and I always get the feeling of "spaghetti" FSM. I much prefer starting with a perfect hierarchy and use exceptions as late as possible and only when it makes sense.

Jare on October 27th, 2007

A reasonable compromise could be to use the 2nd HFSM approach, but allow sharing of sub-states between states. For example, you might have the HIDE substate present in both the ATTACK and INVESTIGATE states. If the AI is hiding while attacking and loses track of the target, the 1st level FSM wants to switch from ATTACK to INVESTIGATE. It is able to do so smoothly by keeping the HIDE substate active. You are not breaking modularity as Sergio proposes; you simply recognize that there are low-level activities that make sense in multiple high-level states, but the kind of available transitions between substates (and conditions to perform these transitions) are different in different states. Another candidate for this kind of sharing could be the RELOAD substate, which could be triggered during the ATTACK only when you run out of ammo, or during the INVESTIGATE while you are looking around. The states in the animation graph would be grouped at a slightly higher level of abstraction (stationary vs moving for example). along the lines of what Matthias suggests, you could us a mini-pathfinder to find the closest sub-state in your current state that is also present in the state you want to transition to. The obvious drawbacks of this approach are: - potential combinatorial explosion where each state contains many substates and the number of transitions there explodes. - need to create "gate" substates that serve purely to connect between states. The advantage is that you can create any transition you want between two low-level states, while maintaining the encapsulation of transitions that are valid within a high-level state.

alexjc on October 28th, 2007

[B]Sergio,[/B] These spaghetti FSMs aren't great for AI because it benefits from being well structured hierarchically, but they do serve a purpose. For animation specifically, when you need the perfect control and edit states individually by tagging them it works fine. I like to make child states completely unaware of their parents. That's how behavior trees work and it gives you most of the modularity you need. [B]matthias,[/B] Good idea. Backward chaining would help, but you can also do this the "hard way" by editing lots of transitions into the FSM that take into account these required steps. :-) This brings up some interesting questions about decoupling animation postures from the logical states. Need to think about that one more! [B]Jare,[/B] Yes, that's a great insight. Most often, the HFSM are not trees but direct acyclic graphs (DAGs). This works in many cases, as you described... the only catch is that any nested states inherit the transitions of their parents, so you still need to be able to jump out when the transitions are no longer applicable. Alex

alexjc on November 10th, 2007

[B]James[/B], Well, if you look at the hierarchy as a tree or DAG, then lower-levels never point back to a higher-level. So in that sense, HFSM are acyclic. However, in the graphs that are drawn, the arrows are transitions and not cycles in the hierarchy. So in that sense, the HFSM is just a way to reuse transition logic. You could flatten it down to a normal FSM if you wanted to. Does that make sense? Alex

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!