# GameState management hierarchical FSM vs stack based FSM

I'm reading a bit on Finite State Machines to handle game states (or screens). I would like to build a rather decent FSM that can handle multiple screens.

e.g. while the game is running I want to be able to pop-up an ingame menu and when that happens the main screen must stop updating (the game is paused) but must still be visible in the background. However when I open an inventory pop-up the main screen must be visible and continue updating etc.

I'm a bit confused about the difference in implementation and functionality between hierarchical FSM's and FSM's that handle a stack of states instead. Are they basically the same? Or are there important differences?

• What is hierarchical FSM? Are you referring to the State Pattern? Mar 20, 2012 at 3:01
• The state pattern is one part of how you could implement a hierarchical state machine, but a hierarchical state machine is a concept that pre-dates any individual design pattern. Mar 20, 2012 at 19:38
• @Kylotan: That's a useful piece of information. Thanks for adding this. Mar 20, 2012 at 22:55

As I understand it, the major difference between hierarchical state machines and stacked FSMs (HFSM and SFSM from now on) is that in an HFSM transitions away from a low level state can be specified directly, whereas in a SFSM, states in the subgroups cannot have specific exit conditions that leave the subgroup.

Probably best with an example:

This is a HFSM:

This is a SFSM (or nested FSM):

Essentially, the SFSM is "context free", in that a lower subgraph does not need to know about the implementation of the greater machine, while in a HFSM, the lower subgraphs will transition out to specific states in the greater machine. SFSM have clear benefits in that the lower subgraphs can be modified without knowledge of the complete machine.

There are some decent resources online that cover this topic too.

Images from http://aigamedev.com/open/article/hierarchical-or-nested-fsm/ (2012-03-20)

• -1 you shouldn't answer questions if you "have no idea what you are talking about". State machines can be applied to this domain; in fact they are applied to a vast array of domains: business workflow, compilers, AI, etc. Big pity - your answer would have received a definite +1 in an AI question. Mar 20, 2012 at 12:14
• I appreciate your input. However your answer focusses on the use of FMS's in Ai and doesn't answer my question. Though your link helps me understand FSM better in general, thanks. Mar 20, 2012 at 18:17
• Jonathan,user8363: The question was "I'm a bit confused about the difference in implementation and functionality between hierarchical FSM's and FSM's that handle a stack of states instead. Are they basically the same? Or are there important differences?" I'll reword to sound less like an idiot :-) Mar 20, 2012 at 18:45
• Much better, vote converted to +1 :). Mar 20, 2012 at 19:01
• I agree. This is indeed a clear answer to the question I asked, so I will accept it. Thanks! Mar 20, 2012 at 19:26

I'm not sure what sort of hierarchical FSM do you have in mind, so I'm sorry if this does not directly answer your question, but I'd really like to take the chance and add some input from my own experience using a stack based screen manager.

Since you need the ability to open a popup screen but still be able to see the screens below, having a stack based implementation will make implementing it pretty easy - you can just push the popup screen into the stack, and pop it again when you're done.

You can also easily wire it so that all screens on the stack will be drawn at all times (from top to bottom), but only the topmost screen will be updated. But here's a few extra tips that I find useful in my managers.

Tip 1 - Provide a Switch operation

Pushing a new state is useful, but I find that most of the time you won't be creating popup windows but rather transitioning between larger states. So I like to add a third operation besides the push and pop that allows me to swap states in one go. Something like:

1. Push(State) - Pushes a new state into the stack.
2. Switch(State) - Replaces the current topmost state in the stack with a new one.
3. Pop(Amount) - Removes the N topmost states from the stack.

Tip 2 - Registering states and addressing them by ID

I've seen some state manager implementations that expect you to pass the actual state object when pushing a new state. This means that you will either be using it as Push(new TitleScreen()) and creating a new screen object everytime, or you will have to create and store references to your screens and reuse those references.

Usually I don't want to recreate the same state everytime, but I don't want to have to manage the references myself either, so I always add a a method such as Register(Name, State) to my state manager which stores the states in a Dictionary and then I do all push or switch operations using the state name instead (e.g. Push("PauseScreen") instead of Push(new PauseScreen()).

I tend to create and register all my states at once when the application starts, although most of them hold little state until they are actually added to the stack.

Tip 3 - Transition callbacks

It's also useful to add a few callbacks to your states to be called whenever the state is pushed or popped. For instance, I use these four callbacks:

1. OnEnter - Called when the state is pushed into the stack.
2. OnExit - Called when the state is removed from the stack.
3. OnSuspend - Called when a new state is pushed on top of the current one.
4. OnWakeup - Called when the state on top of this one is popped.

I tend to put little or no processing in my states' constructors, and leave all the actual initialization to the OnEnter method. This way I can reuse my state object multiple times without having to create a new one.

You can also define a duration for your transitions, so that when you push or pop a state, the operation does not take place automatically, but only after a small transitioning phase, which you can use for fading or other animations.

Tip 4 - Delayed operations

Pushing or popping states right in the middle of the update phase can have unpredictable results. In order to address this, I delay my operations and queue them to be executed at the end of the update phase instead.

So when I issue a push/switch/pop operation I simply instantiate a new struct object with the parameters and type of operation that was performed and add it to a list.

Then after all states have been updates, I go over the list and apply any operation that have been queued. I use something like this inside my screen manager class:

private enum ScreenManagerCommandType
{
Switch,
Push,
Pop
}

private struct ScreenManagerCommand
{

public ScreenManagerCommand(ScreenManagerCommandType type, Screen screen)
{
Type = type;
Screen = screen;
}
}

• All of this is very easy to follow if you've ever used an HP RPN calculator =) Or programmed in Forth. Nice coverage. Mar 20, 2012 at 1:53
• However this answer still leaves me in the dark how other approaches would work and I'm still undereducated in the difference between a hierarchical FSM and a stack based FSM and how to apply them to game states, I will take this as a base for my implementation. You explained it very well and it seems rather intuitive. I'm not going to accept this as answer because it doesn't exactly answer my qustion. I don't have enough reputation to vote it up though, otherwise I would. Thanks a lot this really helps me! Mar 20, 2012 at 18:29
• @user8363 No problem! By the way, I learnt most of these tips from an article in Game Programming Gems 5 in case you'd like a reference. Mar 20, 2012 at 19:04
• Great tips. Glad to see concepts from functional programming in mainstream. 1. Function Composition, 2. Memoization, 3. Higher Order Functions, 3. Monads Nov 2, 2016 at 23:48
• TIP: Regarding this answer's Tip 2; a different (possibly better) way of doing it is to use a reference to the class-type, instead of a string name. --- You don't get the risk of messing the string with typos or during changes in refactors, because you kinda get type-safety from the compiler; while still getting the same effect of not having to instantiate states every time, or worry about containers/management (well, you do, but it's just a dictionary; same as the string/name approach). Might even save a few bytes of memory (because [class-]reference instead of string)! Jun 21, 2017 at 19:09

Give screens blocksUpdate and blocksRender fields. That way, you can easily tell a menu to stop the game from updating (and maybe rendering if you can't see the game anymore). So loop backwards through the stack until you reach a block and then loop forwards updating or drawing.

• This answer doesn't suffice to answer my question. Perhaps you can elaborate more on this? I started out doing something like this, however I'd add an option 'input' to enable or disable input on that screen / state. How would this fit into the bigger system? When and where would these be blocks be changed on a screen? I'm mostly struggling with fitting it all together in an elegant and intuitive way. Mar 20, 2012 at 18:25
• Personally, I'd just go with a simple stack of GameScreens. I'd create a GameScreenManager class to handle that, where you can call Push(GameScreen) or Pop to add/remove a layer. I've never found the need for a state-based system myself. Mar 20, 2012 at 18:54