8

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.

Rivasa
  • 6,510
  • 3
  • 35
  • 64

1 Answers1

17

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.

Some programmer dude
  • 400,186
  • 35
  • 402
  • 621
  • 1
    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. – HolyBlackCat May 04 '18 at 21:31
  • 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. – Rivasa May 04 '18 at 21:43
  • 1
    @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. – Some programmer dude May 05 '18 at 10:35