Game State 'Stack'?

Question

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.push_back(new OptionsMenuState());
states.pop_front();

To represent the player loading, then going to options, and then main menu.
Is this a good idea, or...? Should I look at something else?

Thanks.

Answer 1

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.

My biggest problem with our Global State Machine was that it was a stack of states, and not a set of states. This means, e.g., .../MainMenu/Loading was different than .../Loading/MainMenu, depending on if you got the main menu up before or after the loading screen (the game is asynchronous and loading is mostly server-driven).

As two examples of things this made ugly:

• It led to e.g. the LoadingGameplay state, so you had Base/Loading, and Base/Gameplay/LoadingGameplay for loading within the Gameplay state, which had to repeat much of the code in the normal loading state (but not all, and add some more).
• 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.

Answer 2

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.

It can support state transitions, transparent states (such as modal message boxes) and loading states (that manage the unloading of existing states and loading of the next state).

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.

Answer 3

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.

Answer 4

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

Answer 5

One of the "Game Programming Gems" volumes had a state machine implementation in it intended for game states.

This archived document has an example of how to use it for a small game, and shouldn't be too Gamebryo-specific to be readable.

Answer 6

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.

Answer 7

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);
    LoadLevelState *state = new LoadLevelState();
    state->SetLevel(eng->GetSaveGame()->GetLevelName());
    state->Load.Bind(this, &SomeGameState::OnLevelLoaded);
    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);
}

Answer 8

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

Answer 9

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.

Answer 10

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_inGameMenu,
   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]();
}