# Using a stack for the gamestate

This topic is 4544 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

First of all I would say that what everyone is describing is not a State Machine but is more of a Task Management system. The methods that everyone is using i.e. Render, Update, Push, Pop, Dispose. Is akin to Start, Stop, Pause, Run, Push Task, Pop Task onto a Task System or a Event Handler. A true state system does not have a State Manager but simple proceeds from one state to the next as each state knows what criteria is needed for moving another state and therefore decoupling that responsiblity and allowing for 'any' functionality within a state.
Quote:
To handle a popup menu state like that one would derived all the GUI states from a PopupState which would be derived from the main GameState or State class. This would allow for all the Derived object to have the funcitonality of the PopupState where the input say a right mouse click would then prompt run the code within the PopupStates input handler which would initialize the popupmenu and display it. So, that would be a simple solution to use with an actual state machine system.

Just a thought but how exactly are the states your describing and the state "stack" different from a Task Management system or System Kernel Architecture.

I'm not trying to belittle anyones design I think some of these are really quiet intriquing only I think that everyones use of gamestate is really more gametask or Itask rather than a state machine.

##### Share on other sites
@ sirGustav:

Quote:
 Do a FSM need to [know what state came before it]?

A state in an FSM needs to know what state came before to do such tasks as returning to the previous state.

Quote:
 In this case I would probably have done a state in a popup-stack that overrides the game-state. ie:update: if popupstack is empty update game-state, if popup is nonempty - update popup.rendering: render game-state, then render popups

If I understand correctly, then you are proposing to implement a stack system for only those "base" states that really need a stack, which also turns it into a "bottom-up" system rather than a "top-down" system. Other than requiring a (probably insignificant) amount of work, I only see one problem with this method: By having a base state manually implement a stack system you are requiring every base state to know whether another state may or may not be pushed on top of it. In my opinion, this limits extensibility, though an argument could be made that it also keeps the state system from being abused with needless pushing of states ontop of other states.

Quote:
 void GameState::update(float p_deltaTime) { m_currentGame->update(p_deltaTime); if( someCondition ) gameMashine->setState(InGameMenyState::instance());}orvoid GameState::update(float p_deltaTime) { m_currentGame->update(p_deltaTime); if( someCondition ) gameStack->pushState(InGameMenyState::instance());}

Again, if a pure FSM was used, you would need to hardcode in or otherwise tell the new state which state it should return to after it is done executing. In the first chunk of code, InGameMenyState::instance() would need to be passed a handle to the previous state.

Quote:
 I really can't argue with this, but is it needed? A pause state might want to update the view, but not the game logic(like max payne pause) and there goes IMHO the beauty of stack.

Hm... maybe "stack" isn't the proper term... How about "runtime state inheritance"? What I'm describing is actually a lot like type inheritance and polymorphism, except with states instead of classes. For example, pushing state A onto a stack whose top state is state B really means that A is inheriting (and probably overriding some of) the functionality of B, which in turn may inherit and override the functionality of C, and so on... So yeah, it's like polymorphic states where inheritance happens a runtime.

Quote:
 So the options-state updates the one underneath? Doesn't this mean you can click around in the main-menu, or is there an option that comes w/ the option-menu? If so that is IMHO a bad design since it allows to add several option-menu's on the stack...

My system seperates the handling of user input from the handling of game logic. My "options menu" state calls the rendering and game-logic code of the state beneath it, but does NOT call the user-input code. So no, the user can't actually click on anything beneath since the state beneath can't respond to user input. (though in my system, a state could call the previous state's input code if it really wanted to)

@ Toolmaker:

Quote:
 Allowing each state have a set of sub-states(Such as Controls in C# *ALL* have a Controls member) allows things such as small Windows(Inventory in an RPG for instance) to be on top of the current state, but not block it. Without showing any code, calling Update() on the top state, would first have it update itself, and then call the Base.Update() function, which then updates all the sub-states. Same accounts for Render() function.

Yeah... there's no reason that an individual state in a stack-like state system couldn't also implement is own sub-states, such as gui controls and whatnot.

Quote:
 The pro of using a TaskManager however allows things to be more seperated out. I could write a NetworkTask which is responsible for sending/receiving player information over the network. Instead of stashing it into the MainGameState, I shove it directly into the TaskManager and give it a high priority.

@ 5MinuteGaming:

Quote:
 A true state system does not have a State Manager but simple proceeds from one state to the next as each state knows what criteria is needed for moving another state and therefore decoupling that responsiblity and allowing for 'any' functionality within a state.

Right, and that's what's limiting about a pure FSM. Oftentimes you want a state to behave in an abstract manner based on some previous or related state.

Quote:
 To handle a popup menu state like that one would derived all the GUI states from a PopupState which would be derived from the main GameState or State class. This would allow for all the Derived object to have the funcitonality of the PopupState where the input say a right mouse click would then prompt run the code within the PopupStates input handler which would initialize the popupmenu and display it. So, that would be a simple solution to use with an actual state machine system.

Wait, I'm afraid I don't quite understand what you're saying. Could you explain in more detail?

Quote:
 Just a thought but how exactly are the states your describing and the state "stack" different from a Task Management system or System Kernel Architecture.

In a task manager or kernel architecture, a bunch of different tasks are all run in parallel, meaning that more than one state can be active at a time. In my stack-like system, *only* the top state is executed, and it may explicitly decide whether the state directly beneath it may also execute some portion of its code.

- Fuzz

##### Share on other sites
First of all, let me start off by saying that I think the nature/genre of the game should be primarily considered when deciding to use a game stack, task manager, or whatever your design is. Some games would be more suited for a game stack than others, so I don't think there is any "one solution fits all" design here.

Having said that, my game is a (non-MMO) 2D RPG and we use a classic game stack engine. There is a base class that all the different mode classes inherit from, and the top of the stack is the active game state (and there can only ever be *one* active state). The (GPL) code for this can be seen in the following two files (look at the GameMode and GameModeManager classes):

engine.h
engine.cpp

It's been working great so far and its a really simple, convenient, and intuitive interface.

Quote:

You don't have to do it this way (ie, you don't need a state for every little piece of code in the game). We define our states as different "game modes" (modes of operation). There's map mode for exploration, boot mode for the boot menu, battle mode, menu mode, etc. It doesn't make since to write a seperate state for every different active GUI menu: it's just too many states. Instead what you can do is implement your Update function for a game state (like menu mode) to take different actions based on the value of different class members. So if I keep a pointer to the currently selected menu in Menu Mode, I call a different sub-Update function that processes code specific to that menu.

The only thing we've had trouble with so far is when a game mode wants to destroy itself. For example, when you select a new game in Boot mode you want to destroy Boot mode (and hence free up the resources it consumes) and push a Map mode. But having a class object destroy itself is a very risky/daring thing to do (its been working so far). Here's an e-mail excerpt I sent one of my new developers on the matter and my idea for circumventing the problem.

Quote:
 I was concerned about this for a long time too. I know that it's bad coding practice, but it worked at the time. What I wanted to happen when switching modes was the following:1) Construct the new mode2) Push it to the top of the game stack3) Wait for the current mode's subroutine to exit4) Pop the old modeThe problem with this was that I couldn't think of a good way to do this. But now I think I do, so tell me how this sounds. Currently, there is this line in the main game loop:ModeManager->GetTop()->Update(SettingsManager->UpdateTime());Which calls the Update function for the game mode on the top of the stack. What if I modify this call to check a change in game state. So for example, first lets assume that there's a temporary "staging" pointer in the GameModeManager class that is NULL except when there's a new game mode to push. Then I can write the following function:void GameModeManager::UpdateGameState(Uint32 update_time) { if (next_state != NULL) { Pop(); // Remove the old state Push(next_state); // Put the new state on the stack next_state = NULL; } game_stack.top()->Update(update_time); // Update the game state on the top of the stack}But there are problems with this too. 1) We check for a state change every iteration through the main loop and since 99.9999% of the time there is no change, it seems wasteful. 2) Just because we push a new state doesn't mean we want to pop the old state. To solve #2, I guess I could do something like write the Pop function to keep a vector of states that are expired and periodically the GameModeManager will check it and remove any old game modes (updating the game stack accordingly in the process). But I still have a feeling that there should be a better way to do this.

A modern processor's branch predictor should be able to guess the 99.99999% that that if statement is false, so I don't think there would be a big performance hit or anything. But I'm wondering if anyone else knows of a better solution to the problem?

##### Share on other sites
Quote:
Original post by Holy Fuzz

Quote:
 To handle a popup menu state like that one would derived all the GUI states from a PopupState which would be derived from the main GameState or State class. This would allow for all the Derived object to have the funcitonality of the PopupState where the input say a right mouse click would then prompt run the code within the PopupStates input handler which would initialize the popupmenu and display it. So, that would be a simple solution to use with an actual state machine system.

Wait, I'm afraid I don't quite understand what you're saying. Could you explain in more detail?

##### Share on other sites
Although a stack-like state system is certainly useful for more than just a popup window, here's my reasoning for using it in this one particular case: The popup window is entirely self-contained, meaning that it is not associated with any other gui control, and in addition it blocks EVERYTHING ELSE on the screen from responding to user input (not just what is visibly obscured by the window). My gui system itself supports popup windows very nicely, but not the ability to easily prevent controls outside the window's region from responding to user input. (the popup window actually dims everything else on the screen by drawing a screen-sized translucent grey rectangle behind the window). The popup window is, in effect, its very own self-encapsulated state, even though at appears translucently ontop of another state.

##### Share on other sites
Quote:
 Original post by Holy FuzzA state in an FSM needs to know what state came before to do such tasks as returning to the previous state.

The code in that link that I posted earlier, everything that the fsm need is in the fsm class. Even the previous state, but (IIRC) in a real FSM "returning to the previous state" doesn't exist, only going to new states :)

Quote:
Original post by Holy Fuzz
Quote:
 In this case I would probably have done a state in a popup-stack that overrides the game-state. ie:update: if popupstack is empty update game-state, if popup is nonempty - update popup.rendering: render game-state, then render popups

If I understand correctly, then you are proposing to implement a stack system for only those "base" states that really need a stack, which also turns it into a "bottom-up" system rather than a "top-down" system. Other than requiring a (probably insignificant) amount of work, I only see one problem with this method: By having a base state manually implement a stack system you are requiring every base state to know whether another state may or may not be pushed on top of it. In my opinion, this limits extensibility, though an argument could be made that it also keeps the state system from being abused with needless pushing of states ontop of other states.

no no no ;) That system would be used for popups only to override the game-loop. In this system a popup != gameloop. Popup stops the loop(to some extent) while the game loop is a loop, so the game loop lives in a happy little world not knowing what happens with the popup and for what it is conserned popups doesn't exist. sortof like popup(msg); could also be print(msg);.

Quote:
Original post by Holy Fuzz
Quote:
 void GameState::update(float p_deltaTime) { m_currentGame->update(p_deltaTime); if( someCondition ) gameMashine->setState(InGameMenyState::instance());}orvoid GameState::update(float p_deltaTime) { m_currentGame->update(p_deltaTime); if( someCondition ) gameStack->pushState(InGameMenyState::instance());}

Again, if a pure FSM was used, you would need to hardcode in or otherwise tell the new state which state it should return to after it is done executing. In the first chunk of code, InGameMenyState::instance() would need to be passed a handle to the previous state.

See above, but if a true fsm would be used, I would have to send events to it all the time and have it call the updates.

Quote:
Original post by Holy Fuzz
Quote:
 I really can't argue with this, but is it needed? A pause state might want to update the view, but not the game logic(like max payne pause) and there goes IMHO the beauty of stack.

Hm... maybe "stack" isn't the proper term... How about "runtime state inheritance"? What I'm describing is actually a lot like type inheritance and polymorphism, except with states instead of classes. For example, pushing state A onto a stack whose top state is state B really means that A is inheriting (and probably overriding some of) the functionality of B, which in turn may inherit and override the functionality of C, and so on... So yeah, it's like polymorphic states where inheritance happens a runtime.

So the update function in the pause state can move the game camera? but isn't this one hidden from the pause state since it belongs to the game state? How would it be coded into the states? Giving the state a getCamera() function seems like a stupid idea? A Meny or a popup state can't return a camera, right?

I think this isn't really a discussion about game-states but on if a meny state(Game Menu, Options Menu, Quit Menu etc) is a game state or a menu is a game state?
Maybee itsn't such a bad idea if you can make the whole menu as a single gamestate(and menu states as nodes in a tree). But I'm still unsure of wether it's a good idea to have a stack - stack overflow (and underflow) might occur unless managed correctly [rolleyes] ...

##### Share on other sites
Quote:
 no no no ;) That system would be used for popups only to override the game-loop. In this system a popup != gameloop. Popup stops the loop(to some extent) while the game loop is a loop, so the game loop lives in a happy little world not knowing what happens with the popup and for what it is conserned popups doesn't exist. sortof like popup(msg); could also be print(msg);.

Ah... I think I get it now. So a popup like that would actually provide its *own* game loop? Much like calling message box functions in Win32 looks like a function call but actually pops up a box that the user can interact with, without breaking the flow of the code. You could still pass the popup an interface to the state so that it can call its code if necessary. I like the idea, and the only problem I see with it is implementing the system.

Have you indeed implemented such a system? If so, what issues did you have to deal with to implement it? My engine has some pretty strict definitions of where a frame begins and ends, and so providing a game loop inside of a frame that has already begun might cause some issues, as well as some timing issues and such. My game loop is a pretty hefty beast, and so providing a generic game-loop that any class can implement is crucial.

Quote:
 See above, but if a true fsm would be used, I would have to send events to it all the time and have it call the updates.

This makes sense now that I understand how you're handling the game loop.

Quote:
 So the update function in the pause state can move the game camera? but isn't this one hidden from the pause state since it belongs to the game state? How would it be coded into the states? Giving the state a getCamera() function seems like a stupid idea? A Meny or a popup state can't return a camera, right?

My states each have Input(), Update(), and Draw() methods which are exposed through an interface. A pause state (BTW, there are probably better ways to pause a game than using a state, but that's beside the point) would almost certainly call the game state's Draw() function, and would almost certainly NOT call the game state's Update() function (that's the whole point of pausing, right?). The pause state might or might not call the game state's Input() function, depending on whether the pause state wanted to let the user interact with the game state's UI. Whether the camera movement code is put inside Input() or Update() is really just a judgement call (do you consider it part of the UI or part of the gameplay?).

Quote:
 I think this isn't really a discussion about game-states but on if a meny state(Game Menu, Options Menu, Quit Menu etc) is a game state or a menu is a game state?Maybee itsn't such a bad idea if you can make the whole menu as a single gamestate(and menu states as nodes in a tree). But I'm still unsure of wether it's a good idea to have a stack - stack overflow (and underflow) might occur unless managed correctly ...

Here's a rough example some of the possible stacks in one of my games:

Game

I've ommitted an options menu and some multiplayer stuff, but you get the point.

The GameSetup screen creates a new game, clears the state stack, and pushes the new game onto the stack. When the game exits, it clears the stack and pushes the main menu onto the stack. I don't consider individual gui elements to be their own states. The game state itself contains an in-game gui, which is not a seperate state, though when the user clicks on the "menu" button in the game it pushes the GameMenu state onto the stack, which effectively pauses the game and blocks the in-game UI from responding to user input.

There is of course no reason the functionality described above couldn't be done in your system. MainMenu and Game could be two states in the FSM, and SinglePlayer, GameSetup, Multiplayer, DisplayOptions, and GameMenu could be function calls that implement their own game loops.

##### Share on other sites
Quote:
 So a popup like that would actually provide its *own* game loop?

Not quite. To the game-loop it would appear as such, but the reality could more look like this:
void popup(str) {  popupstack.push(new Popup(str));}void main() {  init();  while(run) {    if( popupstack.empty() ) {      update(deltaTime);    }    else {      popupstack.peek().update(deltaTime);    }    render();    if( !popupstack.empty() ) popupstack.peek().render();  }}

It't more or less a (poor) hack, but it does the job and quiet nice IMHO - so I guess it isn't a hack after all :).

Quote:
 Have you indeed implemented such a system?
nope, haven't had the time (or need) to do it. Since my current game (3 years of coding in october) is almost complete (and 100% badly designed) I plan to design my new game(Cpp this time instead of C) alot better ;)

Quote:
 (do you consider it part of the UI or part of the gameplay?)
The code should IMHO go into update() since it doesn't rely on input.
However in my current (planned) design a pause state probably would have pushed a PauseCameraControler onto the CameraControler stack.
(The Controler idea is basicly to have a stack with controlrs such as AI, Keyboard, Script etc. Some controlers should pop() themself(such as the script when it's done) and some should stay until pop()ed by someone else).

Quote:
 The GameSetup screen creates a new game, clears the state stack, and pushes the new game onto the stack.

Nice, I might try a sytem like this soon, however I got one (more) question for you: How do your exit-button function / game-loop header look like:
something like this:
while( !stack.isEmpty() ) gameLoop();

or something like this:
while(running) gameLoop();void onExit() {running=false;}
?

##### Share on other sites
Quote:
 Nice, I might try a sytem like this soon, however I got one (more) question for you: How do your exit-button function / game-loop header look like:something like this:while( !stack.isEmpty() ) gameLoop();or something like this:while(running) gameLoop();void onExit() {running=false;}?

Actually, both:

while(running && !stack.isEmpty()) gameLoop();
void onExit(){running=false;}

is roughly what it looks like. I realize I could have onExit() clear the stack to the same effect, but by setting a flag instead I allow the application to examine and manipulate the stack without any unexpected errors (if the stack was cleared, and then something tried to pop a state off, this would result in an exception).

##### Share on other sites
Quote:
 Original post by nilknOther than this, there aren't any other non-superficial differences between my system and yours.

I would disagree, these two designs are highly different. A stack based state machine makes the prequisite that all states must be designed as a tree-graph where iteration between states goes from node to node. I.e. you can't "jump" from one state to another. Simple example, you have set it up like this:

|- Options
|- Play Game

Now say you're in options, with a state stack you aren't allowed to start the game from there (not a problem in this case IMHO, but you get my point). You have to pop out of Options back to Main Menu, and from there push Play Game.

joanusdmentia shows a perfect example where this becomes a problem. For simple games I would even consider it good because it forces you to have states that are logically ordered hierarchly. I haven't used hplus0603 idea but it seems simple and good.

Toolmaker, your responce to joanusdmentia hacks in a fix to the problem. As I said, a state stack isn't done for "jumping". So looping until size==1 or current==MainMenu is more of a hack than good state stack management.

Niteage system is a bit like mine, where I did something I call substates. A substate calls the parent states update/render etc. so it doesn't pause its parent. This is useful for ingame menus that shouldn't pause the game, like weapon switching in a action game (think HL and Max Payne). (as Toolmaker noticed)

Quote:
 Original post by 5MinuteGamingI believe xSKOTTIEx had the right idea. A separate manager is like putting more gas on the flames.

As I understood xSKOTTIEx he does use a manager, just not stack based. Having to repeat this:
current()->pause();
stack().push( newState );
current()->play();
everywhere you want to switch state is pretty bad, thus the manager.

Something I always keep getting back to is, how to switch states in a "nice way". Having a StateStack* in each state, so they can go pop/push whenever they want or using a event system or simple quering? hmm =)