What are the principles involved for an Hierarchical State Machine, and how to implement a basic model?

Question

So I'm attempting to make a game using C++, and I've read a ton of articles on Finite State Machines (FSM), and Hierarchical State Machines (HSM). However I will admit most of the stuff I've read is a bit dense and hard to understand, so I was hoping someone can simplify it for me. Is this answer an FSM or an HSM?

From what I would like to clear up:

1. How is an HSM different from a normal FSM, and why is it better for games?

2. Regarding C++, How do you implement a basic HSM following the state pattern? (I might be incorrect on this/using the wrong words.)

3. How exactly do you handle transitions? What is the on_exit and on_enter method I keep hearing a lot about?

4. Do I need one HSM for my entire game? (e.g. Handling all enemies, player actions, game menus) or do I use multiple HSMs?

5. When implementing player entities, would they all be a subset of an Entity state?

6. Lastly if someone could give some pseudo-code to help visualize these questions, I would appreciate it.

Dudley

Answer 1

It's just about nesting. An HSM is basically an FSM, but where each state in turn can be a separate FSM.

For an example in a game, consider an NPC. It has multiple states:

1. Walk to point A
2. Wait a minute
3. Walk to point B
4. Wait a minute
5. Continue from 1
6. Fighting with PC

This FSM is simple, but all states needs to have a transition to state 6 (Fighting with PC) for when the NPC is attacked by a PC. This makes the FSM kind of ugly. So instead lets have this much more simple FSM:

1. Walking about
2. Fighting with PC

This FSM is very simple, there's only two transitions, and it's easy to understand. The major parts of state 1 is then a secondary FSM:

1. Walk to point A
2. Wait a minute
3. Walk to point B
4. Wait a minute

If there's an event which doesn't match the secondary FSM transitions, like a PC attacking, you go up a level to the top-level FSM to match the event and find a suitable transition.

You could in a way think about it as a stack, each state in a higher level could push a new lower-level FSM. If there's an event that doesn't match any possible transitions, pop the stack and go back up a level. Continue until there's a matching transition.

In short, it's a way to simplify an FSM.

Succentor

Great explanation. I've never heard of HSMs before and I just randomly stumbled upon this question, but probably will use them from now on. – Rounds

Great explanation! If you don't mind me asking, so an HSM is a bunch of FSMs put together. How exactly does the go up one level work? I'm not quite sure on it. – Dudley

@Annabelle Simplest way is probably think about it as functions. Each FSM is a single function. When you enter a new FSM, you call a function. Going "up" is simply returning from the current function. – Succentor