Game State 'Stack'?

The Communist Duck
  • Game State 'Stack'? The Communist Duck

    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.

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

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

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

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

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

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

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

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

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

  • 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);
    }
    

Tags
c++ architecture state
Related questions and answers
  • . state_->handleEvent(event, this); } That means that I don't really ever need more than one instance of a particular entity state; doing something like entity.setState(new StandState) is therefore highly wasteful. Then again, making each entity state a singleton hardly seems appropriate. What do you suggest I do? (The same can be said about game states, so whatever the solution to this is, I guess it can be applied to game states as well.) 2. The state of the entity sprite. Most of the time, whenever the state of the entity changes, the sprite that is used to represent it must

  • I have a simple question. For people that know and built ogre3D from source as a Static library, what is the order of which the libraries should be linked? The libraries I need to be organized are: Ogre Plugins 'libOgreMain.a' Ogre RenderSystems Boost(version 1.47)link Ogre's Dependencies The reason I'm asking is because in the Ogre forums, I have asked about this and didn't get a good reply... yet. The other reason is because even though I link to the boost library, I get this error: undefined reference to '_imp___ZN5boost6thread20hardware_concurrencyEv' My compiler is MinGW

  • I'm creating a component-based game object system. Some tips: GameObject is simply a list of Components. There are GameSubsystems. For example, rendering, physics etc. Each GameSubsystem contains pointers to some of Components. GameSubsystem is a very powerful and flexible abstraction: it represents any slice (or aspect) of the game world. There is a need in a mechanism of registering... coupling. A. We can add new GameSubsystem. For example, let's add GameSubsystemTitles that registers all ComponentTitle and guarantees that every title is unique and provides interface to quering objects

  • Say I develop a game for mobile platform running OpenGL ES 2.0. I have done 2D part, and now I wish to import some 3D objects. The imported 3D objects must contain the following: Vertices positions Normals UVs Texturing information Animation information Collision mesh Maybe some other things... I am aware, that I could and (maybe should) create my own file format that brings these data from..., that will let me import 3d meshes into my game, ready to use? The solution/middleware should be: easy to use easy to port efficient not consuming too much memory with unnecessary things containing all

  • screen, a map screen, an inventory screen, a battle screen, a battle GUI screen, and basically I could stack these screens on top of each other as necessary to create the game graphics. Whatever... sort of designs other people used to overcome them, or would use. For a little background, I started working on it in my free time last summer. I was initially making the game in C#, but about 3 months... areas of concern I have and wanted to get some opinions on the proper way others have solved them or would solve them. 1. Cyclical Dependencies When I was doing the game in C#, I didn't really have

  • I want to be able to (only) define game states using Lua script, but I'm not sure how I should do it. Here's what I have in mind currently: For each state, I will create a .lua file that contains... exiting the state). So if I want to have a MainMenuState, I will have a file called "MainMenuState.lua" which will contain something like this: MainMenuState = {} MainMenuState["onEnter"] = function() end MainMenuState["onUpdate"] = function(elapsedTime) end MainMenuState["onExit"] = function() end Defined states will be exposed to the game engine via a singleton StateManager class

  • for making a game. What are the basic game logics i need to start with? - Should i write Tic-Tac-Toe game? - Actually this seem very basic to me. I'm totally confused on where to start with.I like to create big games but after starting i feel the game is too heavy to handle. Can any one list out the basic needs of a Game Play programmer? I don't mind using any platform (Flash,c++,objective-c) but i need to know what are the game logic's i need to know before i start a big game.

  • that. All this seems well and good, except I have one question, why not linked lists rather than arrays? Sure, if you had to make your own linked list class, I would be on board, but in c++ anyway, assuming... at the source code since I have not a clue to where I should begin). The reason he gave for this was because while it may be slightly slower to do things the naive way, it's not much, and in many cases.... And I could see a case there for using arrays rather than linked lists, because you would have to make your own (which while simple enough to do, could potentially lead to many more errors). I also

  • I'm having a problem with the way I designed my first simple game in C++. I have GameObject (abstract class) and ObjectA which inherits the update() and draw() methods from GameObject. My main loop contains a linked list of GameObject*, and while that list is not empty it cycles through it, calling update on each one. Up until this point, I thought the design was standard(?) and would work. However, when I call update on ObjectA() I run into two problems: ObjectA can die which messes up the list, which in turn throws off the loop in main. ObjectA can spawn more ObjectA's