# Using a stack for the gamestate

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

## Recommended Posts

[This is more meant as a design discussion, and not really a question. I want some feedback on my design] I was thinking a little about the design of my next game(A simple Asteroids clone, in 3D) about how the manage the gamestates. Since in a game like tetris you can get away with a flag, in a bigger game, using flags will make things messy, very messy. So I remember a convo I once overheard about using a stack for this. All the gamestates are derived from an abstract base class called GameState. GameState has a few functions like Update(), Render() and a few callbacks. The main GameStateStack class, controls these states, and calls Update()/Render() on the top class in the stack, and allows the top object to pop itself off the stack, or push new states onto the stack(Such as when a user selects "New Game", a PlayGameState object is created and shoved onto the stack). This creates a very robust system, that's reusable over various games, and makes it easy to encapsulate various functionality. I'm using C#, so here is some code to illustrate the system: GameStack
	public class GameStack
{
System.Collections.Stack stack = new Stack();

public GameStack(GameState initialState)
{
stack.Push(initialState);
}

public void Update(float timeDelta)
{
if (stack.Count > 0)
{
// Get our top state
GameState state = (GameState) stack.Peek();

// And update it
state.Update(timeDelta);
}
}

public void Render()
{
if (stack.Count > 0)
{
// Get our top state
GameState state = (GameState) stack.Peek();

// And render it
state.Update(timeDelta);
}
}

public void Push(GameState newState)
{
// Hook the dispose event
newState.Disposing += new StateDisposingEvent(OnStateDisposing);

// Push it onto the stack
stack.Push(newState);
}

public void Pop()
{
// Pop the the object, and store it
GameState state = (GameState)stack.Pop();

// Make sure to release all resources
state.Dispose();
}

private void OnStateDisposing(object sender)
{
// Is the object disposing while still on top? If so, remove it
if (stack.Peek() == sender)
{
stack.Pop();
}
}
}


The GameState
	public abstract class GameState : IDisposable
{
protected GameStack stack = null; // We need to know in which stack we are
protected Device device;

public event StateDisposingEvent Disposing; // In case we're disposing while on top of the stack

public GameState(GameStack stack, Device device)
{
this.stack = stack;
this.device = device;
}

public abstract void Update(float timeDelta);
public abstract void Render();

#region IDisposable Members

// Child classes need to be able to trigger the disposing
protected void TriggerDisposing()
{
if (Disposing != null)
Disposing(this);
}

public void Dispose()
{
TriggerDisposing();
}

#endregion
}


Now, would you guys consider this a robust system, and/or what could be improved to the system? I assumed the top state is always the state that will send the dispose event. I could change the system a bit so that if a lower state wants to be popped, all other states ABOVE it, will be popped aswell(Such as a state running multi-threaded and all the sudden decised to dispose itself). Toolmaker

##### Share on other sites
I personally use a very similar system, however it's not stack-based and is slightly more complex in certain aspects.

I have an abstract base class for game states, from which specific states are derived (just like you do). However, I store these in a map (I use C++ BTW) which relates states to strings (which are the state's IDs or names).

Instead of updating the most recently pushed state, I store the string ID of the current state and execute it's corresponding value in the map. Your stack-based method is probably more efficient here since mine has to perform a look-up into the map.

Other than this, there aren't any other non-superficial differences between my system and yours. Mine actually is tied into a messaging system also, but that's irrelevant to this discussion.

This system has always worked fine for me. It's definately more clean than a big huge switch statement. I'm sure there's other methods which can be employed to make this even more elegant, but for a non-massive game project, this method should be perfectly sufficient.

##### Share on other sites
Hello,

http://tonyandpaige.com/tutorials/game1.html

Regards,
Oscar

##### Share on other sites
The main drawback here is that it requires game states to be 'stackable'. This will be fine in a simple game (eg. your Asteroids clone), but when things start to get more complicated this may not be desirable.

The first example that comes to mind is when dealing with saved game. Say the user loads a previously saved game. At the moment the user enters the game the stack would look something like this:

^ PlayGameState

Lets say the user now presses escape to go back to the load menu, what do you do? Do you pop the PlayGameState off the stack? That would make it impossible to resume the current game. So, you add another LoadMenu state onto the stack. The user then picks a different saved game, and after a couple of iterations of this you end up with something like:

^ PlayGameState
| PlayGameState
| PlayGameState

##### Share on other sites
I use a state machine for moving between states, as well as a stack for temporary states. So, there's a current state, and some possible overlays. You can almost get away with just one layer of overlay ("menu", say), but for some game designs, such as an RPG with close-up fight scenes, you need a two-deep stack: main game -> fight scene -> menu.

My state class has five functions: enter, exit, suspend (when something pushes on top), resume (when popped back to be topmost) and step.

The "state manager" is built in as static functions in the abstract base class, because it's so simple. When you setState() to a new state (rather than pushState()), all states in the current stack are torn town and exited before the new state is entered. Thus, if you're in main game -> combat scene -> menu, and choose "load game", that will setState() on a "main game" state, which will tear down the combat scene and menu, and you're left with just a main game state at the bottom of the stack.

##### Share on other sites
I am using a "stack", but it is basically a linked list. All nodes are derived from my Screen class, and the base screen holds a child screen. If the screen has no child, it is the current state. Otherwise, all of the calls to the screen get passed through. The benifit of this is that any of the derived screens can override this behaviour, either to perform its own computations based on events, or provide a more complicated state structure.

In the load menu scenario they screens could simply pop down a few levels, since they already have to have the ability to return values to lower levels. It shouldn't be any different then a child form in normal windows programming.

##### Share on other sites
Quote:

I don't completely agree with you there, because that's a matter of bad stack management. Perhaps my class needs a Count property where as loading a game would look like:

while (stack.Size > 1) // More than our initial gamestate    stack.Pop();stack.Push(playState);

This will place the gamestate on top of just the main menu, which is exactly the kind of behaviour you want.

Toolmaker

##### Share on other sites
Maybe the Load state could pop itself from the stack?

##### Share on other sites
That's exactly the idea

##### Share on other sites
i have created a very similar design. except there is no stack. each game state has the standard render update etc methods. but there is also a GameState* changeState() method. which, when the game state is ready to change, this method will return the next game state to be used (whatever it may be, the manager doesnt care). if this method returns a non-null value, it calls the clean up method for the current state, deletes it, and sets the current state to the one that was returned. if you want the states to pause / run again without recreating, you can add a temp game state map and add the state to that before deleting.

##### Share on other sites
I experimented with the idea of holding gamestates in a stack and possibly having multiple gamestates active at the same time.

The top gamestate would be updated and would then be able to update the next game state (if it wished to).

Same with rendering (the top render state decides if the state below it gets rendered etc, then they are rnedered from the bottom up).

It produced some interesting results, but it was difficult to maintain which seems to have been, on reflection, caused by the fact that the game state system was also tasked with performing several responsibilities - part gui, part flow control etc.

I still think it has potential, it just needs to be properly designed and implemented (when I was experiementing with it I was just adding code and features ad hoc to see how it turned out).

EDIT:

As an example, I had a pause state which would have the state beneath it render, but not update. It would also absorb any input.

##### Share on other sites
In my system I have gamestates and a Kernel/Task system (actually a gamestate is updated via the Kernel as well but with some special rules). This keeps me from wanting multiple gamestates active at once (like Nitage's suggestion) which I have found isn't always the best solution.

Also, the link that ogracian posted had a fairly decent idea as far as a state based system that allows popping (which I think is important to avoid the problems joanusdmentia brings up).

In addition what I always prefer to do is to have my base State class resemble the following:
class State{public:    State();    virtual ~State();    virtual void update();    virtual void render();    virtual void onPause();    virtual void onResume();};typedef shared_ptr<State> StatePtr;...template<class StateT>StateManager::pushState(){    stateStack_.push(new StateT);}

I like not having to manage the actual instances of my states. Of course Toolmaker's question was about C# and I'm not sure how well this transfers to C# (resource cleanup isn't as much of a problem so many of the benefits are lost I'd assume).

##### Share on other sites
I too use a stack-based state system. Unlike the other state systems posted in this discussion, my system does not use a base state class from which other states are derived. Instead, I use a class which contains delegates (for people who aren't familiar with .Net, delegates are essentially function pointers and can point to multiple methods) to the appropriate methods to be called (Draw, Update, Input, etc...). The advantage of this system is that, if desired, you can peek the current state on the stack, clone it, and then override the particular method calls.

For example, my gui system has a message box class, which when shown, clones the current state, redirects the input to the message box, ADDS the message box's drawing code (such that both the box's code is called after that of the previous state), removes any update calls, and pushes the newly-created state onto the stack. When the box closes, it simply pops its state off the stack, returning to whatever was being shown underneath.

EDIT: I like Nitage's system alot too. It seems to offer all the functionality of mine plus it's a little bit simpler. I'll have to consider something like that.

[Edited by - Holy Fuzz on August 10, 2005 4:43:35 PM]

##### Share on other sites
Niteage's system is pretty similar to what I had in thought, except he allows multiple gamestates to be active, something I consider bad.

The problem with multiple gamestates being active, is that you have NO idea of the outcome, as the various states could interfere with eachother.

The idea of using delegates is only implemented for the disposing, because it basicly just prevents a dead-state from being active.

The stack allows states to push new states and pop themselfs. Even in the case of a LoadGame state, it would first call stack.Pop(); and then call stack.Push(playState);

Also, preventing the stack from having references to any DirectX/Game Engine related code will make it more reusable. One small modification is to make the GameState itself a stack, so a gamestate can contain substates.

AOE had a system with trading/diplomacy/load/saving while you were playing, that would pause the game and show the menu full-screen. This would be a perfect example on it's usage. And in the case of a multi-player game, you could just update the sub-states, aswell as the main state(But for instance, not render)

Toolmaker

##### Share on other sites

Becauses tasks can be activated and deactivated at any time, even in the middle of iterating the task list, there's a bit of complexity involved. But it's not too difficult to solve. My solution was to maintain a copy of the active task list. The original list isn't sorted. Anytime a task is activated or deactivated I set a dirty flag which I check at the top of the game loop. When the dirty flas is set, I update and sort the copy. I haven't run in to any problems with this system so far.

##### Share on other sites
How would you handle multiplayer games?

If you're the server (and a client playing), when you pause the game, the server shouldn't neccessarily stop. Do you keep updating states below it, just not rendering them?

I find your stack based approach interesting.

##### Share on other sites
What's the point?
To me, all posible GameStates are:
• Game
• Meny
• InGame meny
• Game w/ console
• Meny w/ console
• Paused game
This translates to a FSM that could look something like this.
The meny can (and should) contain a stack of previous meny-states. The current game-class, that is controlled in the game-state, should have a hierchal(sp?) structure(ie SingleplayerGame, ClientGame, ServerGame etc). (I have focused only at sp-games so far, so I am unsure of the lower parts of mp-games, but I am sure I would to it with a thread or two.)

I plan on using this design in my next game. My current game is basicly lots of unstructured code(the game state is a integer w/ *cough* switchs *cough* ;) ).

##### Share on other sites
Quote:
 Original post by sirGustavWhat's the point?To me, all posible GameStates are:GameMenyInGame menyGame w/ consoleMeny w/ consolePaused gameThis translates to a FSM that could look something like this.The meny can (and should) contain a stack of previous meny-states. The current game-class, that is controlled in the game-state, should have a hierchal(sp?) structure(ie SingleplayerGame, ClientGame, ServerGame etc). (I have focused only at sp-games so far, so I am unsure of the lower parts of mp-games, but I am sure I would to it with a thread or two.)I plan on using this design in my next game. My current game is basicly lots of unstructured code(the game state is a integer w/ *cough* switchs *cough* ;) ).

That doesn't look very extensible - just because you can't currently envisage any other possible gamestates doesn't mean you won't need one in the future.

Redesigning now to provide easy extensibility will be much less effort than refactoring your code later.

##### Share on other sites
Why use a "stack" or a state manager when using states. The point of the Finite State Machine is that the individual states know which states can possibly come next that includes the states that it came from. So you don't need a separate data structure to contain that information. I believe xSKOTTIEx had the right idea. A separate manager is like putting more gas on the flames.
Quote:
 xSKOTTIExi have created a very similar design. except there is no stack. each game state has the standard render update etc methods. but there is also a GameState* changeState() method. which, when the game state is ready to change, this method will return the next game state to be used (whatever it may be, the manager doesnt care). if this method returns a non-null value, it calls the clean up method for the current state, deletes it, and sets the current state to the one that was returned. if you want the states to pause / run again without recreating, you can add a temp game state map and add the state to that before deleting.
The only problem I see with xSKOTIEx's method is that when the individual GameState wants to change states it would call ChangeState which he stated above would return GameState* with the new implementation but that means that the AbstractGame object or whatever is holding the current state has to be polling or somehow know that the state has been changed. You could give each gamestate a reference to the Game class or engine class that actually has the current state and that class would have the method void ChangeState( GameState* newGameState) and that would be called with the new or old instance of the state to be run.

Another problem comes to mind if you want to keep old states that you might have to go back to say with a GUI system where you move through a set of screens. So like Main Screen-> Option Screen -> Font Option Screen and you wanted to keep the state of those system intact at the time the user moved to the next state. The Font Option State would then have a reference to the previous Option State and if the user presses done on the Font Option Screen then the next state would be the Reference to the Option State object. Furthermore, the Option State Object would still have its Reference to Main Screen and the state. Of course it would be very beneficial if you used smart pointers if implementing this in C/C++. But I think that that eliminates the need for a "stack" and implementing a system of popping and pushing elements off and on much like a Kernal task system which is more of what is being discussed rather than an actual state machine.

I dunno I could be wrong its just my observation here.

##### Share on other sites
Quote:
Original post by Nitage
Quote:
 Original post by sirGustavWhat's the point?To me, all posible GameStates are...

That doesn't look very extensible - just because you can't currently envisage any other possible gamestates doesn't mean you won't need one in the future.

Redesigning now to provide easy extensibility will be much less effort than refactoring your code later.

Take a look at this design. IMHO that shows a pretty easily expandable FSM(p2-p3), besides there is a difference (IMHO) between designing for the future, and implementing code that might come in handy in the future.
If I wanted to code for the future, I could throw in a stack, a hash-table(for some indexing) and some cool tree(for some unknown reason), but what's the point if I don't need it?
If all this mashine does is delegate it's duties to other classes I can't see any design that can't be applied to this one without too much hassle.

##### Share on other sites
I think Aldacron provided an even better solution to storing game states. By providing a TaskManager and Tasks that can run simultaniously you can both solve problems with the requirement of multiple tasks running at the same time and have an extensible system.

I personally consider it a better system(I'm not just here to defend my design :P), and I should implement it a bit to test some things around.

I consider a task/state management system one of the crucial parts of a game engine. Without a proper designed system for this, you quickly end up in shit. Which is the whole reason, I ditched my 2D asteroids clone, because I lacked a proper gamestate system.

Right now, it's time to implement a prototype system for TaskManagement and Tasks, and compare both systems. And then I can finally work on other problems.

Toolmaker

##### Share on other sites
The point of a stack-based system is that any given state does not need to know what state came before it. For example, in one of my games I have a popup options menu, that is both accesible from the main menu and from within the game. When I want to let the user access the menu, I simply push its state onto the stack. When the user exits from the menu, it pops itself off the stack, returning to whatever state showed the menu in the first place. I would argue that this system is much easier to use and much more elegant than a FSM where you have to pass the previous state around all over the place.

In addition, you could impliment a system whereby the top state can call code from the state directly beneath it. In the case of my popup options menu, the menu still draws the state "beneath" it, so that behind the options menu you can see either the main menu or the game, depending on what showed the menu in the first place. In the case of a multiplayer game where you don't want the options menu to pause the game, it can call the update logic of the state beneath it in addition to the rendering code.

##### Share on other sites
Please don't get me wrong - I'm not critizising anyones design... I'm trying to learn and improve my own :)

Quote:
 Original post by Holy FuzzThe point of a stack-based system is that any given state does not need to know what state came before it.

Do a FSM need to?

Quote:
 For example, in one of my games I have a popup options menu, that is both accesible from the main menu and from within the game. When I want to let the user access the menu, I simply push its state onto the stack. When the user exits from the menu, it pops itself off the stack, returning to whatever state showed the menu in the first place.

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

Quote:
 I would argue that this system is much easier to use and much more elegant than a FSM where you have to pass the previous state around all over the place.

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

There isn't that much difference in code to me...

Quote:
 In addition, you could impliment a system whereby the top state can call code from the state directly beneath it.

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.

Quote:
 In the case of my popup options menu, the menu still draws the state "beneath" it, so that behind the options menu you can see either the main menu or the game, depending on what showed the menu in the first place. In the case of a multiplayer game where you don't want the options menu to pause the game, it can call the update logic of the state beneath it in addition to the rendering code.

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

##### Share on other sites
This is not really a suggestion for what to do, but a description of things I've done. Things that are a bit different from everyone else it seems, as usual :/

I don't use a stack, and I don't really have a seperate state machine for gamestates. In my current design, the actual game, or menus, or similar dialogs are just renderable classes. Renderables are stuffed into a tree, and where they exist in the rendering process determines which is 'active'. Usually this results in a stack-like behavior, but not always.

Opening a menu will simply occlude what's being displayed below. Deleting/closing the menu returns whatever is below to the forefront [or at least to the menu's position in rendering].

I've two different methods I've tried to use for dealing with... er, what's being discussed here as state transitions. The first is simple explicit side effects to creation. For example, creating a menu object might need to check if the game is running and pause it when opening. Similarly, the created menu would then include extra functors to re-start the game at close.

Kinda messy, kinda difficult to track, but good enough for really simple games where you can enumerate the various possible states in your head.

The other method is something I stole from my textinput class design. I made a class which groups things. It was meant to make sure that only one textinput was active at a time. It also works fairly well with major game states, as well as 'selected unit', and menu selections. It does a lot of the things the other method does, but with more code re-use.

It's not terribly flexible though, and the programmer doesn't have enough control [imo] of how some of the transitions occur.

##### Share on other sites
I've been thinking on it for a while now, and both designs are actually quite good. Let's consider the stack idea:

A main stack is always updating it's top state. Allows menu's to be re-used along the way, and it doesn't require the top state to know what is below it.

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.

Thus, my MainGame state catches the keypress 'i', checks if the menu is already open and if not, creates a new menu and pushes it into the local stack. With some slight modifications you can set a specific stack to update only top or all states.

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.

The pro of using a TaskManager is that you can seperate out task, and give them a higher priority. However, the con is that for instance with menu's, it's much harder to see where each menu belongs at that moment. With a stack, you could print out the stack, and know exactly what's going on where.

I think both options are VERY useable, and whichever you use is probably very personal.

Toolmaker