Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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?

share|improve this question
    
What is hierarchical FSM? Are you referring to the State Pattern? –  XiaoChuan Yu Mar 20 '12 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. –  Kylotan Mar 20 '12 at 19:38
    
@Kylotan: That's a useful piece of information. Thanks for adding this. –  user8363 Mar 20 '12 at 22:55

3 Answers 3

up vote 4 down vote accepted

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:

Hierarchical state machine

This is a SFSM (or nested FSM):

Nested state machine

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)

share|improve this answer
1  
-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. –  Jonathan Dickinson Mar 20 '12 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. –  user8363 Mar 20 '12 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 :-) –  brice Mar 20 '12 at 18:45
    
Much better, vote converted to +1 :). –  Jonathan Dickinson Mar 20 '12 at 19:01
    
I agree. This is indeed a clear answer to the question I asked, so I will accept it. Thanks! –  user8363 Mar 20 '12 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 readonly ScreenManagerCommandType Type;
    public readonly Screen Screen;

    public ScreenManagerCommand(ScreenManagerCommandType type, Screen screen)
    {
        Type = type;
        Screen = screen;
    }
}
share|improve this answer
1  
All of this is very easy to follow if you've ever used an HP RPN calculator =) Or programmed in Forth. Nice coverage. –  Patrick Hughes Mar 20 '12 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! –  user8363 Mar 20 '12 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. –  David Gouveia Mar 20 '12 at 19:04

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.

share|improve this answer
    
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. –  user8363 Mar 20 '12 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. –  Boreal Mar 20 '12 at 18:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.