c++implementationhierarchicalfsm

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


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.


Solution

  • 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.