🔒 Locked

Managing Game States: The Stack Method

Started by Phineas Nov 30, 2005 at 1:39 AM 24 replies 7.4k views

Original Post

Nov 30, 2005 at 1:39 AM

Like most budding game programmers, I started by creating clones of the classics. No, the world did not need another version of Pong or Asteroids; but, as classically-trained musicians may begin with Mozart, so game programmers may begin with Tetris. In writing Pong, Asteroids and Tetris I managed states the easy way: using a switch-case block. This is nice for simple projects, but for more complicated projects the code becomes messy. Enough of my preamble about what many of you already know. On to the point: In researching alternative methods, I came across this tutorial about managing states using a stack (which most of you already know of as well). I adapted this method, changed a few things to suit my needs, and I came up with reusable code for managing game states. gamestack.zip comes with the reusable code, as well as a sample (text) game as a proof-of-concept¹ to show how it all comes together. download gamestack.zip (c++) Changes from the tutorial: 1. Removed SDL code. 2. Removed the need for GameStates to be singleton classes. I know it takes a lot to download source code and look at it, but if you could take look and give me some pointers, I would be very grateful. Even if you can't, I'd like to discuss any conceptual problems with managing states this way, and any alternatives you may have (though I have used the gamedev.net search function a bit). (1) I’ve always wanted an excuse to say “proof-of-concept.” Edit: Updated code per suggestions below [Edited by - Phineas on December 1, 2005 4:41:16 PM]

ToohrVyk

238

ToohrVyk

Nov 30, 2005 at 1:53 AM

A very good initiative, which earns you an increased rating from me.

I do have some questions, though:

Why use a vector to implement manually a stack, when the SC++L already provides std::stack?

Wouldn't it make sense to have GameStack inherit from GameState?

Shouldn't the documentation for functions be in the header, rather than in the implementation file?

I disagree with your handling of popState in the situation where the stack is empty. My reflex would have been to throw an exception (or an assert, depending on who is allowed to use the object).

Similarly, you should issue at least warnings or errors when a stack that was disabled is used.

Who is responsible for destroying objects added to the stack? Note that quit destroys all objects, while popState does not destroy the removed object (and as a consequence, you have a memory leak in your example code).

You already implemented a method to push/pop states. Why, then, reimplement both functionalities in changeState, when you could simply make two successive calls to popState and pushState?

Also, I have two short suggestions to make:

Don't force the programmer to implement all of the virtual functions in GameState. As you noticed, it results in empty functions, which is useless to have or write. Have the base functions do nothing instead.

You should also add onEnable and onDisable functions to GameState, and have these functions be called whenever the game state gains focus (is pushed onto the stack, or the state above it is popped) or loses focus (is removed from the stack, or a state is pushed on top of it).

Phineas

Author

Phineas

Nov 30, 2005 at 8:35 AM

Thanks for your reply. The code was taken from the tutorial mentioned above and modified, so perhaps I was not as thorough as I should have been. My main objective was to remove singletons, which I have been indoctrinated to avoid. You've presented a lot of ways in which GameStack may be improved, and a lot of your suggestions I am taking.

Quote:
Wouldn't it make sense to have GameStack inherit from GameState?

Its logical in the sense that most of GameStack's functions (init, exit, input, process, output) are also functions of GameState. But, to inherit GameStack from GameState would imply that GameStack is-a GameState, when the purpose of GameStack is to control GameStates.

Quote:
I disagree with your handling of popState in the situation where the stack is empty. My reflex would have been to throw an exception (or an assert, depending on who is allowed to use the object).

Good point. If there is no state on the stack, GameStack isn't doing anything anyway. Although, I could just call GameStack::quit when this happens.

Quote:
You already implemented a method to push/pop states. Why, then, reimplement both functionalities in changeState, when you could simply make two successive calls to popState and pushState?

Do you mean GameState, instead of calling changeState, should call popState then pushState, or that changeState should call popState then pushState?

Quote:
Don't force the programmer to implement all of the virtual functions in GameState. As you noticed, it results in empty functions, which is useless to have or write. Have the base functions do nothing instead.

So, I should keep the base functions declared as virtual, just remove their "pure virtual"-ness ( foo() = 0; to foo() {} )?

Quote:
You should also add onEnable and onDisable functions to GameState, and have these functions be called whenever the game state gains focus (is pushed onto the stack, or the state above it is popped) or loses focus (is removed from the stack, or a state is pushed on top of it).

The tutorial originally had these functions, and I removed them. What would a game state need these for?

Quote:
Who is responsible for destroying objects added to the stack? Note that quit destroys all objects, while popState does not destroy the removed object (and as a consequence, you have a memory leak in your example code).

Shouldn't the documentation for functions be in the header, rather than in the implementation file?

Why use a vector to implement manually a stack, when the SC++L already provides std::stack?

All of these my novice hands overlooked; thanks for pointing them out (especially the memory leak! GameStack is supposed to handle destroying GameStates).

Wuntvor

Nov 30, 2005 at 9:29 AM

Nice, I have done something like this as well, so I thought I'd give some comments as well. As to Enable/Disable methods, I think they actually have a lot of uses. For example, you may not want to keep all resources around at all times, so you could free them up when you lose focus. Or you could use it to hook up to input events when gaining focus and disabling it again when losing focus (not necessary if using your input-mechanism, I know, but if using an event-based system it might be useful).

Also, in my opinion, having GameStack derive from GameState might actually make sense if you see GameStack not simply as a container for GameStates but rather as representing the current GameState. Actually, it sounds as if the problem with both approaches is that the class is in the end doing two things at once: It holds GameStates and it represents the current GameState.
So, in my opinion, it should really be something like Stack->Current->Update() or whatever instead of Stack->Update(), to reflect this. If you feel this is too cumbersome, I'd still derive it from GameState, as it is no more wrong than not deriving. But then, I am not that good at designing classes, so I might be completely wrong about this. :)

meh

Nov 30, 2005 at 10:03 AM

Quote:
Original post by Phineas
Quote:
Don't force the programmer to implement all of the virtual functions in GameState. As you noticed, it results in empty functions, which is useless to have or write. Have the base functions do nothing instead.

So, I should keep the base functions declared as virtual, just remove their "pure virtual"-ness ( foo() = 0; to foo() {} )?

Pretty much, although be careful to make a distinction between the functions that must be implemented versus those that may be implemented.

Quote:
Quote:
You should also add onEnable and onDisable functions to GameState, and have these functions be called whenever the game state gains focus (is pushed onto the stack, or the state above it is popped) or loses focus (is removed from the stack, or a state is pushed on top of it).

The tutorial originally had these functions, and I removed them. What would a game state need these for?

Doing things when you enter or leave a state. Wuntvor mentioned resources and input focus. If you are using this class in multiple places to do different things for example controlling the global game state or implementing a FSM in an enemy character having the extra flexibility can be very useful.

Wuntvor

Nov 30, 2005 at 11:19 AM

Quote:
Original post by Wuntvor
So, in my opinion, it should really be something like Stack->Current->Update() or whatever instead of Stack->Update(), to reflect this. If you feel this is too cumbersome, I'd still derive it from GameState, as it is no more wrong than not deriving. But then, I am not that good at designing classes, so I might be completely wrong about this. :)

Guess I'll quote myself here.. I just wrote a simple implementation of this, and it appears a lot cleaner to me than my previous implementations (when I did have Draw() and Update()-methods directly in my Stack). Also, the more I think about it, the more I think that having those inside the GameStack class is actually not logical at all.

Why would a GameStack have input(), process() and output() methods? Do I want to output() the GameStack to the screen? No, what I actually do want to do is retrieve the current GameState and output() that to the screen. Sure, it may seem more convenient to write Stack->output(), but that should not guide us in making decisions like this, in my opinion.

One more thing I have been thinking about: Are Init() and Exit() methods actually important? It doesn't really sound that useful to me. The GameState may care when it becomes active and when it stops being so, but why would it care about being inserted or removed into a GameStack? Actually, I'd argue that GameState shouldn't know at all about GameStacks but should rather be independent from it.
If Init/Exit is included so that resources can be managed, I'd argue that these should be loaded at construction of the object (or in the Enter event) and freed at destruction (or in the Leave event). Otherwise, it may be initialized several times (if it is inserted again after having been popped) which isn't very intuitive at all.

Okay, I'll stop ranting now!

Phineas

Author

Phineas

Nov 30, 2005 at 3:53 PM

Quote:
Original post by Wuntvor
...

Why would a GameStack have input(), process() and output() methods? Do I want to output() the GameStack to the screen? No, what I actually do want to do is retrieve the current GameState and output() that to the screen. Sure, it may seem more convenient to write Stack->output(), but that should not guide us in making decisions like this, in my opinion.

One more thing I have been thinking about: Are Init() and Exit() methods actually important? It doesn't really sound that useful to me. The GameState may care when it becomes active and when it stops being so, but why would it care about being inserted or removed into a GameStack? Actually, I'd argue that GameState shouldn't know at all about GameStacks but should rather be independent from it.

...

Wuntvor, I've implemented your suggestion about removing input, process, and output from GameStack; doing so increased the flexibility of GameState-derived classes. I've also removed init() and exit(), as you make a good point that those are actually a constructor and destructor in disguise.

sanguineraven

Dec 1, 2005 at 1:47 PM

I am still at the same stage as the OP here (writing simple 2d games) and using a stack-based game state manager. I too am using a vector, for the reason that I might still need to access one of the states lower on the 'stack' as opposed to just the current one, thus am not using an STL stack.

Just Chris

Dec 1, 2005 at 3:23 PM

I'm currently designing the code layout for an RPG of mine and want to know what kind of advantages do stacked game state systems have over switch-case systems? Will the latter method eat too much CPU?

See, I tried to keep things as simple as possible in my RPG. I have a Game class, which carries out two important functions: initialized the game and its global variables, and then it goes to awaiting the game state choice. It stays in this mode in a while loop, until the player decides to quit.

Currently I have four game states: Menu (which can double as 'Pause'), Battle, Shop, and Plot. There is no dungeon crawling; it's a tactical RPG. And the Plot is empty for now, it will just trigger scripted events so that's not important for me now. The game's in debug/testing mode so the user can choose any of these options at will, which takes the input to a switch/case statement.

As you can see it's not as elegant as the game stack approach, but I'm only choosing among 4 different game states here. Depending on what state you're in, the program simply applies functions from various other classes (like a Shop class, Status class, etc). Most of these involve many while loops, which keep the game in its current state, and if the loop is broken out of, the player is free to go do something else. Is this good way to handle events? Currently I have a shop that works, and a simple battle simulator (which receives no input from the player), and have had no problems.

So is it a good idea to attempt to break down even a complex game such as this into a few states?

Simagery

Dec 1, 2005 at 3:58 PM

Quote:
So is it a good idea to attempt to break down even a complex game such as this into a few states?

It's always a good idea to break things down into small pieces. It gives you a lot of flexibility, whether you end up using it or not. I've never been unhappy with having flexibility.

Quote:
Why use a vector to implement manually a stack, when the SC++L already provides std::stack?

Part of me would tend toward the std::stack on first impulse, but I have found in many situations that I may have a need for seeing past the top of the stack, something not possible with std::stack. Of course, it's an implementation detail, so it doesn't hurt to initially go with std::stack until you find the need for something more flexible (assuming your original design doesn't predict the need).

Quote:
Wouldn't it make sense to have GameStack inherit from GameState?

My gut says "no" as the is-a test doesn't apply, but then the "better" test does apply: substituitability. Is it possible you'd want a GameState to be a whole GameStack of its own? Very possible. The design decision would then be should one not inherent and force the GameStack to simply be an implementation detail of the GameState in question, or do we build it into the design?

It kinda depends on what the goals of the design are. If you're implementing a Finite State Machine and want to support hierarchical FSMs, then this may make sense... but probably only internally, in the implementation.

As far as the "interface" of the system is concerned, a GameStack is not a GameState and they do serve different purposes, even if the implementation of one may benefit the other.

@Phineas: Good work! I'd love to see more stuff like this at GameDev.Net. These are the kind of discussions and info-exchange that's really beneficial to the community. Rating++!

oliii

271

oliii

Dec 3, 2005 at 6:28 AM

Quote:
Original post by Simagery
Quote:
Wouldn't it make sense to have GameStack inherit from GameState?

My gut says "no" as the is-a test doesn't apply, but then the "better" test does apply: substituitability. Is it possible you'd want a GameState to be a whole GameStack of its own? Very possible. The design decision would then be should one not inherent and force the GameStack to simply be an implementation detail of the GameState in question, or do we build it into the design?

It kinda depends on what the goals of the design are. If you're implementing a Finite State Machine and want to support hierarchical FSMs, then this may make sense... but probably only internally, in the implementation.

As far as the "interface" of the system is concerned, a GameStack is not a GameState and they do serve different purposes, even if the implementation of one may benefit the other.

I'd advocate the use of composition in that case, rather than inheritance. If you want a state to have a state machine, put a state machine object in there. It's less confusing imho :)

osmanb

Dec 3, 2005 at 10:05 AM

Yeah. My gut reaction to that scenario is that the stack should remain distinct. But you could create a derived type of state (GameMetaState or something) that contains a stack. Clearly, not all states are composed of multiple other states. And a stack by itself isn't really a state either. But there is a type-of state that contains several sub-states.

The code for that particular state would end up very similar to some of the earlier stack code, but I think the fine distinctions are important, and the clear design would simplify later decisions about where to place logic.

Seriema

Dec 4, 2005 at 11:25 AM

Some comments about the code:
¤ The comment /* Must be implemented */ is missleading, since you decided to use virtual and not pure virtual functions. :P
¤ The function GameStack* GameState::stack() const { return m_stack; }, should return const GameStack* since the function itself is marked as const. And how do you set it in the first place? I'd use a param in the ctor for that.

Some comments based on my own state stack:
¤ I didn't have active() and quit() in the statestack, just a isEmpty(), when the last state is removed then the user has exited and the stack/game should be shut down. Usually I put it in the main while() loop; while( !states.empty() )
¤ Never needed to access the statestack holding a state, thus I didn't have a GameState::stack().
¤ I also had a StateFactory (although I combined it with the stack because I'm lazy :P and called the creation: StateManager). So the pushState() function doesn't take a GameState* but a std::string filename. Data-driven design ^^ The filename holds the data for a state, and the first info is what kind of state it is (menu, scene, etc), the filename is passed to the factory which constructs the state and gives it to the stack.
¤ The AP said he returns false from handleEvents() when he wants the state to quit. I used a system like that for a while, but got stuck on "how do one go to the next state, without inserting a reference to the statestack inside the state?" The solution came with bidirectional communication, a internal event system. The state would simply post an event of what it wanted (push/pop/change) and the stack would pick that up and do it.

About the pause/resume discussion. If you don't have those, how do you stop all sounds?? :O If I go from game to pause I don't want a explosion sound to finish, I want it to pause. And moving between states (to/from battle mode in a RPG) doesn't free the resources of the underlying state (the world scene) but the world music/sounds should give way to the battle theme. Well that's the biggest reason I ever implemented those virtual functions in my states.

Phineas

Author

Phineas

Dec 4, 2005 at 5:06 PM

Quote:
Original post by Seriema
The solution came with bidirectional communication, a internal event system. The state would simply post an event of what it wanted (push/pop/change) and the stack would pick that up and do it.

I'd like to eliminate the need for GameState::stack(). How do you implement an internal event system that does this?

Quote:
I didn't have active() and quit() in the statestack, just a isEmpty(), when the last state is removed then the user has exited and the stack/game should be shut down. Usually I put it in the main while() loop; while( !states.empty() )

The quit() function is used by GameStates ( via stack() ) to quit the game entirely. Yes, this is counterintuitive to the stack method, but what if we wanted to give the user the option of quitting the program while the playing the game?

Also, I originally used "while( !game.empty() )" in the main loop, but consider the following hypothetical main driver:

int main(){	GameStack game;	game.pushState( new MenuState );	while ( !game.empty() )	{		game.current()->input();		game.current()->process();		game.current()->output();	}	return 0;}

If the current state is the only state and it pops itself off of the stack in input(), a segfault occurs on the next line as game.current() is no longer defined.

My solution was GameStack::quit(). The last state calls quit(), setting the active flag to false. The program exits, and the destructor then pops the last state off of the stack. Is this the best way to handle this?

Seriema

Dec 4, 2005 at 5:32 PM

Quote:
Original post by Phineas
Quote:
Original post by Seriema
The solution came with bidirectional communication, a internal event system. The state would simply post an event of what it wanted (push/pop/change) and the stack would pick that up and do it.
I'd like to eliminate the need for GameState::stack(). How do you implement an internal event system that does this?

What I meant was "internal for the engine", not dependent on user input or files or other external sources.. heh If you truly want internal, the only way I see is the state having a stack* but you don't have to wrap it in a public function - make it protected.

Quote:
Original post by Phineas
Quote:
I didn't have active() and quit() in the statestack, just a isEmpty(), when the last state is removed then the user has exited and the stack/game should be shut down. Usually I put it in the main while() loop; while( !states.empty() )
The quit() function is used by GameStates ( via stack() ) to quit the game entirely. Yes, this is counterintuitive to the stack method, but what if we wanted to give the user the option of quitting the program while the playing the game?

If you think about what a state stack really means, you'll notice that it only allows for hierarchialy created "state trees". I.e. you can't go from a leaf way down in the tree to the root, without passing all the intermediate level nodes. So that actually forces to player to "quit" several times, which may or may not be a problem. Usually players want to feel in controll so sometimes we hack it to make them happy. I would ses quit() as one of those hacks. If you feel you want it, keep it.

Quote:
Original post by Phineas
Also, I originally used "while( !game.empty() )" in the main loop, but consider the following hypothetical main driver:

*** Source Snippet Removed ***If the current state is the only state and it pops itself off of the stack in input(), a segfault occurs on the next line as game.current() is no longer defined.

My solution was GameStack::quit(). The last state calls quit(), setting the active flag to false. The program exits, and the destructor then pops the last state off of the stack. Is this the best way to handle this?

And that my friend, is exactly why you put the actual state switching at the end of the loop. I had a function called step() where all statestack state-switching occurs, and I would call at the end of the loop.

Several of my problems got solved thanks to our event system. So I'm not really sure how to do everything clean without it ^^ In your case I'd probably keep it as it is, but removing the public GameState::stack() and GameStack::active() - replacing the later with a update() or such that returns a bool (true if it wants to continue?).

Phineas

Author

Phineas

Dec 4, 2005 at 6:32 PM

Quote:
Original post by Seriema
And that my friend, is exactly why you put the actual state switching at the end of the loop. I had a function called step() where all statestack state-switching occurs, and I would call at the end of the loop.

Should step() be a member of GameStack or GameState? If GameStack, then any calls by a state to pop or push should be put in a list until step() is called. If GameState, then the state needs an internal variable the signifies whether to push or pop, and to what state. Do I understand you in either case?

I'm finding this discourse helpful; I would have never thought to simply move the state switching outside of input/process/output and to the end of the main loop.

Seriema

Dec 5, 2005 at 7:58 AM

Yes, the step() would be in the stack. Although it could technicly be in state too, see below why.

Since I had an event system the handleEvents() call was the last thing in my loop, even the GameStack would handleEvents() since the current state (or technicly, anything) could've fired a push or pop event. Meaning, if there was a stack event it would internally call step() with that event and push/pop accordingly. Here it would also react to a quit event, calling quit() (hehe yeah, I actually did this "hack" for testing purposes ;)).

In your case you could use a internal event system. I.e. the list you mentioned. The state could technicly tell the stack to push/pop wherever it wants to, but it won't happen untill the end of the loop inside the step() call. Although for clarity I would try to keep those called centered, like only in the states' update() function - otherwise input() might say push("foo") while update() says push("bar"), it's gonna get confusing. So maybe you want to keep state switch requests in one function, i.e. let gamestate have a step() too? But then again, that would keep it separate from the logic that actually triggered the state switch and would you would need for yet another internal (to the gamestate) state request list. So keeping it as a "documented rule" to only do that in update() might be just fine ^^

There's also another way. Something one of our coders did for the stack, before we had the event system, he made it so that step() would always call pop(). So if a state wanted to "stay alive" it would have to push() itself onto the stack (again). If it wanted to move to a substate it would push() itself then push() that substate, twice, because the next thing that will happen is a pop(). If the state wanted to be pop()ed, it just didn't push() itself. This might get confusing so one might want to wrap those into changeState(to,from) and keepState(current). To be honest, I didn't really like this method at first but it just might suit your needs perfectly.

Promit

Mod

1,082

Promit

Dec 5, 2005 at 8:24 AM

Why exactly is there a stack of states, rather than a single current state?

Seriema

Dec 5, 2005 at 9:55 AM

Promit: It's a simple way to get hierchial state switching to work, and solves a common "problem" very easily. The problem of returning to the last state. If your in the main menu, choose options, you want to return to main menu after that - just pop. You don't have to set up bidirectional state switches all over, i.e. "in stateMainmenu, when clicking options go to stateOptions" and "in stateOptions when clicking exit go to stateMainmenu" - you get that last part for free. You only have to concentrate on "going down the state tree", it simplifies alot but also puts restrictions on the design. I.e. as noted before, you can't jump from one part of the tree to another - you have to traverse it.

AP: haha I tried that too!! With the statestack that would always pop() at the end of the loop, so the gamestate always needed to return "next state", even if it was itself.
But in your example you said "null meaning to either remain on current state or resume previous", how do you know which one? =/

Seriema

Dec 5, 2005 at 6:28 PM

ah yes, see it now. A bit confusing though, I think I actually prefer letting the state know what statemanager owns it and manipulate it. Or maybe some event like system such as passing a struct? Oh well :)

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.