Game State 'Stack'?

I was thinking about how to implement game states into my game. The main things I want for it are:

• Semi-transparent top states-being able to see through a pause menu to the game behind

• Something OO-I find this easier to use and understand the theory behind, as well as keeping orgranised and adding more to.

I was planning on using a linked list, and treat it as a stack. This means I could access the state below for the semi-transparency.
Plan: Have the state stack be a linked list of pointers to IGameStates. The top state handles its own update and input commands, and then has a member isTransparent to decide whether the state underneath should be drawn.
Then I could do:

states.push_back(new MainMenuState());
states.pop_front();


Is this a good idea, or...? Should I look at something else?

Thanks.

• Do you want to see the MainMenuState behind the OptionsMenuState? Or just the game screen behind the OptionsMenuState? – Skizz Jul 30 '10 at 19:49
• The plan was that the states would have an opacity/isTransparent value/flag. I would check and see if the top state had this true, and if so what value it had. Then render it with that much opacity over the other state. In this case, no I would not. – The Communist Duck Aug 1 '10 at 9:30
• I know it's late in the day, but to future readers: do not use new in the way shown in the sample code, it's just asking for memory leaks or other, more serious errors. – Pharap May 24 '16 at 5:23

I worked on the same engine as coderanger. I have a differing viewpoint. :)

First, we did not have a stack of FSMs - we had a stack of states. A stack of states makes a single FSM. I don't know what a stack of FSMs would look like. Probably too complicated to do anything practical with.

As two examples of things this made ugly:

• We had several functions like "if in character creator go to gameplay; if in gameplay go to character select; if in character select go back to login", because we wanted to show the same interface windows in different states but make the Back/Forward buttons still work.

Despite the name, it was not very "global". Most internal game systems did not use it to track their internal states, because they didn't want their states mucking about with other systems. Others, e.g. the UI system, could use it but only to copy state into their own local state systems. (I would especially caution against the system for UI states. UI state is not a stack, it's really a DAG, and trying to force any other structure on it is only going to make UIs that are frustrating to use.)

What it was good for was isolating tasks for integrating code from infrastructure programmers who didn't know how the game flow was actually structured, so you could tell the guy writing the patcher "put your code in Client_Patch_Update", and the guy writing the graphics loading "put your code in Client_MapTransfer_OnEnter", and we could swap certain logic flows around without much trouble.

On a side project, I have had better luck with a state set rather than a stack, not being afraid to make multiple machines for unrelated systems, and refusing to let myself fall into the trap of having a "global state", which is really just a complicated way to synchronize things through global variables - Sure, you're going to end up doing it near some deadline, but don't design with that as your goal. Fundamentally, state in a game is not a stack, and states in a game are not all related.

The GSM also, as function pointers and non-local behavior tend to do, made debugging things more difficult, though debugging those kind of large state transitions wasn't very fun before we had it either. State-sets instead of state-stacks does not really help this, but you should be aware of it. Virtual functions rather than function pointers may alleviate that somewhat.

• Great answer, thanks! I think I can take a lot from your post and your past experiences. :D +1/Tick. – The Communist Duck Jul 29 '10 at 10:19
• The nice thing about a hierarchy is you can build utility states that are just pushed to the top and don't have to worry about what else is running. – coderanger Jul 29 '10 at 21:01
• I don't see how that's an argument for a hierarchy rather than sets. Rather, a hierarchy makes all inter-state communication more complicated, because you have no idea where they were pushed. – user744 Jul 29 '10 at 21:30
• The point that UIs are actually DAGs is well-taken, but I do disagree in that it certainly can be represented in a stack. Any connected directed acyclic graph (and I can't think of a case where it wouldn't be a connected DAG) can be displayed as a tree, and a stack is essentially a tree. – Ed Ropple Jul 30 '10 at 17:05
• Stacks are a subset of trees, which are a subset of DAGs, which are a subset of all graphs. All stacks are trees, all trees are DAGs, but most DAGs are not trees, and most trees are not stacks. DAGs do have a topological ordering which will allow you to store them in a stack (for traversal e.g. dependency resolution), but once you cram them into the stack you have lost valuable information. In this case, the ability to navigate between a screen and its parent if it has a prior sibling. – user744 Jul 30 '10 at 18:06

Here's an example implementation of a gamestate stack that I found to be very useful: http://creators.xna.com/en-US/samples/gamestatemanagement

It's written in C# and to compile it you need the XNA framework, however you could just check out the code, the documentation and the video to get the idea.

I use the same concepts in my (non-C#) hobby projects now (granted, it might not be suitable for larger projects) and for small/hobby projects I can definitely recommend the approach.

This is similar to what we use, a stack of FSMs. Basically just give each state an enter, exit, and tick function and call them in order. Works very nicely for handling things like loading too.

One of the "Game Programming Gems" volumes had a state machine implementation in it intended for game states; http://emergent.net/Global/Documents/textbook/Chapter1_GameAppFramework.pdf has an example of how to use it for a small game, and shouldn't be too Gamebryo-specific to be readable.

• The first section of "Programming Role Playing Games with DirectX" also implements a state system (and a process system - very interesting distinction). – Ricket Aug 2 '10 at 14:10
• That's a great doc and explains it almost exactly how I've implemented it in the past, short of the needless object hierarchy that they use in the examples. – dash-tom-bang Sep 28 '10 at 23:52

Just to add a little standardization to the discussion, the classic CS term for this kind of data structures is a pushdown automaton.

• I'm not sure any real-world implementation of state stacks is nearly equivalent to a pushdown automaton. As mentioned in other answers, practical implementations invariably end up with commands like "pop two states", "swap these states", or "pass this data onto the next state outside of the stack". And an automaton is an automaton - a computer - not a data structure. Both state stacks and pushdown automata use a stack as a data structure. – user744 Sep 11 '10 at 12:16
• "I'm not sure any real-world implementation of state stacks is nearly equivalent to a pushdown automaton." What's the difference? Both have a finite set of states, a history of states, and primitive operations to push and pop states. None of the other operations you mention are fundmentally different from that. "Pop two states" is just popping twice. "swap" is a pop and a push. Passing data is outside of the core idea, but every game that uses an "FSM" also tacks on additional data without feeling like the name no longer applies. – munificent Sep 12 '10 at 22:17
• In a pushdown automaton, the only state that can affect your transition is the state on top. Swapping two states in the middle is not allowed; even looking at the states in the middle is not allowed. I feel like the semantic expansion of the term "FSM" is reasonable and has benefits (and we still have the terms "DFA" and "NFA" for the most restricted meaning), but "pushdown automaton" is strictly a computer science term and there is only confusion waiting if we apply it to every single stack-based system out there. – user744 Sep 15 '10 at 8:49
• I prefer those implementations where the only state that can affect anything is the state that's on top, although in some cases it is handy to be able to filter the state input and pass processing to a "lower" state. (E.g. controller input processing maps to this method, the top state takes the bits it cares about and possibly clears them then passes control to the next state on the stack.) – dash-tom-bang Sep 28 '10 at 23:56
• Good point, fixed! – munificent Mar 11 '16 at 18:01

I not sure a stack is entirely necessary as well as limiting the functionality of the state system. Using a stack, you can't 'exit' a state to one of several possibilities. Say you start off in "Main Menu" then go to "Load Game", you may want to go to a "Pause" state after successfully loading the saved game and return to "Main Menu" if the user cancels the load.

I would just have the state specify the state to follow when it exits.

For those instances where you want to return to the state preceding the current state, for example "Main Menu->Options->Main Menu" and "Pause->Options->Pause", just pass as a startup parameter to the state the state to go back to.

• Maybe I misunderstood the question? – Skizz Jul 30 '10 at 19:48
• No, you did not. I think the down-voter did. – The Communist Duck Aug 2 '10 at 15:37
• Using a stack does not preclude the use of explicit state transitions. – dash-tom-bang Sep 28 '10 at 23:50

Another solution to transitions and other such things is to provide the destination and source state, along with the state machine, which could be linked to the "engine", whatever that may be. The truth is that most state machines are probably going to need to be tailored to the project at hand. One solution might benefit this or that game, other solutions may hinder it.

class StateMachine
{
public:
StateMachine(Engine *);
void Push(State *);
State *Pop();
void Update();
Engine *GetEngine();

private:
std::stack<State *> _states;
Engine *_engine;
};


States are pushed with the current state and the machine as parameters.

void StateMachine::Push(State *state)
{
State *from = 0;
if (!_states.empty()) from = _states.top();
_states.push(state);
state->Enter(this, from);
}


States are popped in the same fashion. Whether you call Enter() on the lower State is an implementation question.

State *StateMachine::Pop()
{
_ASSERT(!_states.empty());
State *state = _states.top();
State *to = 0;
_states.pop();
if (!_states.empty()) to = _states.top();
state->Exit(this, to);
return state;
}


When entering, updating or exiting, the State gets all the information it needs.

void SomeGameState::Enter(StateMachine *sm, State *from)
{
Engine *eng = sm->GetEngine();
eng->GetKeyboard()->KeyDown.Bind(this, &SomeGameState::KeyDown);
state->SetLevel(eng->GetSaveGame()->GetLevelName());
sm->Push(state);
}

void SomeGameState::Update(StateMachine *sm)
{
Engine *eng = sm->GetEngine();
float time = eng->GetFrameTime();
if (shouldExit)
sm->Pop();
}

void SomeGameState::Exit(StateMachine *sm, State *from)
{
Engine *eng = sm->GetEngine();
eng->GetKeyboard()->KeyDown.UnsubscribeAll(this);
}


I've used a very similar system across several games and found that with a couple of exceptions, it serves as an excellent UI model.

The only issues we encountered were cases where it's desired in certain cases to pop back multiple states before pushing a new state (we re-flowed the UI to remove the requirement, as it was usually a sign of bad UI) and creating wizard-style linear flows (solved easily by passing the data along to the next state).

The implementation we used actually wrapped the stack and handled the logic for updating and rendering, as well as operations on the stack. Each operation on the stack triggered events on the states to notify them of the operation occurring.

A few helper functions were added as well to simplify common tasks, such as Swap (Pop & Push, for linear flows) and Reset (for dropping back to the main menu, or ending a flow).

• As a UI model this makes some sense. I would hesitate to call them states, since in my head I would associate that with the internals of the main game engine, while "Main Menu", "Options Menu", "Game Screen", and "Pause screen" are higher level, and often have only no interaction with the internal state of the core game, and simply send commands to the core engine of the form "Pause", "Unpause", "Load level 1", "Start Level", "Restart Level", "Save", and "Restore", "set Volume level 57", etc. Obviously though this could vary significantly by game. – Kevin Cathcart Sep 29 '11 at 16:51

This is the approach I take for nearly all of my projects, because it works incredibly well and is extremely simple.

My most recent project, Sharplike, handles control flow in this exact way. Our states are all wired up with a set of event functions that are called when states change, and it features a "named stack" concept in which you can have multiple stacks of states within the same state machine and branch among them--a conceptual tool, and not necessary, but handy to have.

I would caution against the "tell the controller what state should follow this one when it ends" paradigm suggested by Skizz: it's not structurally sound, and it makes stuff like dialog boxes (which in the standard stack-state paradigm just involves creating a new state subclass with new members, then reading off it when you return to the invoking state) much much harder than it has to be.

I used basically this exact system in several systems orthogonally; the frontend and in-game menu (aka "pause") states, for instance, had their own state stacks. The in-game UI also used something like this although it had "global" aspects (like the healthbar and the map/radar) that the state switching might tint but which updated in a common way across states.

The in-game menu may be "better" represented by a DAG, but with an implicit state machine (each menu option that goes to another screen knows how to go there, and pressing the back button always popped the top state) the effect was exactly the same.

Some of these other systems also had "replace top state" functionality, but that was typically implemented as StatePop() followed by StatePush(x);.

Memory card handling was similar since I did actually push a ton of "operations" into the operation queue (which functionally did the same thing as the stack, just as FIFO rather than LIFO); once you start using this sort of structure ("there's one thing happening now, and when it's done it pops itself") it starts infecting every area of the code. Even the AI started using something like this; the AI was "clueless" then switched into "wary" when the player made noises but wasn't seen, and then finally elevated to "active" when they saw the player (and unlike lesser games of the time, you couldn't hide in a cardboard box and make the enemy forget about you! Not that I'm bitter...).

GameState.h:

enum GameState
{
k_frontend,
k_gameplay,
k_moviePlayback,
k_numStates
};

void GameStatePush(GameState);
void GameStatePop();
void GameStateUpdate();


GameState.cpp:

// k_maxNumStates could be bigger, but we don't need more than
// one of each state on the stack.
static const int k_maxNumStates = k_numStates;
static GameState s_states[k_maxNumStates] = { k_frontEnd };
static int s_numStates = 1;

static void (*s_startupFunctions)()[] =
{ FrontEndStart, GameplayStart, InGameMenuStart, MovieStart };
static void (*s_shutdownFunctions)()[] =
{ FrontEndStop, GameplayStop, InGameMenuStop, MovieStop };
static void (*s_updateFunctions)()[] =
{ FrontEndUpdate, GameplayUpdate, InGameMenuUpdate, MovieUpdate };

static void GameStateStart(GameState);
static void GameStateStop(GameState);

void GameStatePush(GameState gs)
{
Assert(s_numStates < k_maxNumStates);
GameStateStop(s_states[s_numStates - 1])
s_states[s_numStates] = gs;
s_numStates++;
GameStateStart(gs);
}

void GameStatePop()
{
Assert(s_numStates > 1);  // can't pop last state
s_numStates--;
GameStateStop(s_states[s_numStates]);
GameStateStart(s_states[s_numStates - 1]);
}

void GameStateUpdate()
{
GameState current = s_states[s_numStates - 1];
s_updateFunctions[current]();
}

void GameStateStart(GameState gs)
{
s_startupFunctions[gs]();
}

void GameStateStop(GameState gs)
{
s_shutdownFunctions[gs]();
}