USING STATE STACKS
INTRODUCTION
A polished game gives the player much more than just the ingame interface. There are menus, pause screens, game-over sceens, high-score boards and many other elements. To make life easier for yourself as a programmer, you would need an easy-to-use, extensible system for keeping track of, and switching between, the game's various states. This is to allow the user to browse a hierarchy of menus or to bring up menus ingame, without you having to worry about manually tracking the states the user went through to get to their current position or making sure that the states are freed when they are no longer needed. This is where state stacks come in.
The state stack allows you to "stack" as many different states on top of each other as you want. It will always run the state that is at the top of the stack but allows you to quickly and easily move between states, and is especially useful when you want to move back down the stack (pressing back on a menu for example). This is very usefull when dealing with hierarchical menus.
This is an implementation of the GOF State pattern. [GOF]
STACKS
Stacks work by "stacking" one piece of data on top of another. You can only add or remove items from the very top of the stack, in what is known as FILO or First In Last Out.
Here you can see how objects are added, termed "pushed", on to the stack. First A is placed on the stack, then B on top of A and then C on top of B.
Removing items can only take place from the top of the stack. First you remove, termed "pop", C, then B, then A. The items cannot be removed in any other order, only the topmost object is accessible.
You can read more about ADT's (Abstract Data Types), such as the stack, in [CLRS].
HOW IT WORKS
The state stack system is composed of two key parts: the interface class and a class to store the stack itself and to control the addition/removal/execution of states.
The interface class contains several virtual functions that represent various events which the client can choose to handle. In this implementation all state logic takes place in the Update function but in more advanced programs you would probably split the update function down into two function, one for logic and one for rendering.. Lets see the class now.
class CStateInterface { public: virtual ~CStateInterface(); virtual void EnterState(); virtual void ExitState(); virtual void Update() = 0;};This class just provides an interface for the states to use; it doesn't have much built in functionallity, relying on the client classes to define its behaviour. EnterState() is called when the state reaches the top of the stack - whether that be from it being placed on the stack or by the states above it being removed. ExitState() is called when the state leaves the top of the stack - whether that be from it being removed or another state being put on top of it. Both ExitState() and EnterState() do nothing unless they are overridden by the client class. The Update() function is where most of the state specific logic is held. This is called in the programs main loop through the stack class. Update() has to be overridden by the client class.
You can view the source for all these function in the sample code which you can download at the bottom of the article.
Now that you have the interface class you can write the class which controls the stack and state execution. This class has to do several things. It has to be able to push and pop states to and from stack, retrieve the state currently at the top of the stack, execute the current state and remove dead states - always calling the correct events as it goes.
The stack itself is based on the std::stack container. It provides us with a simple way of pushing and popping items to and from the stack. I'm going to assume you know how to use the stack class. [MSDN] You could use std::vector or std::deque directly, but I decided to use the std::stack wrapper for clarity.
class CStateStack {private: typedef std::stack StateContainer; StateContainer m_StateStack; StateContainer m_DeadStates;public: ~CStateStack(); void Execute(); void PushState(CStateInterface* NewState); void PopState(); CStateInterface* GetCurrentState(); size_t GetStackSize(); private: void PurgeStack(StateContainer& Stack);};Okay, well this is the class. Most of it is self-explanatory, but I'll run through each of the functions so you know exactly how they work.
typedef std::stack StateContainer;Here the type StateContainer is defined as a stack of CStateInterface pointers. This makes the rest of the code clearer, and is a convenience typedef.
StateContainer m_StateStack; StateContainer m_DeadStates;These two stacks store the current states. m_StateStack stores all the currently alive states and the state at the top is the current state. m_DeadStates stores the states awaiting deletion by the Execute() function after being popped from m_StateStack. This allows a state to pop itself without being immediately deleted, which can cause all kinds of problems.
CStateStack::~CStateStack() { if (!m_StateStack.empty()) { m_StateStack.top()->ExitState(); PurgeStack(m_StateStack); } PurgeStack(m_DeadStates);}The destructor's only job is to make sure that all the memory that needs to be freed is actually freed. It calls the PurgeStack() function for both the active and dead stacks, and the ExitState function of the current state, if one exists. If the application has shut down correctly then there shouldn't be any states left in either of the stacks, but this is just a precaution.
void CStateStack::Execute() { PurgeStack(m_DeadStates);}Execute() removes any dead states by calling PurgeStack() for the dead states stack.
void CStateStack::PushState(CStateInterface* NewState) { if (!m_StateStack.empty()) { m_StateStack.top()->ExitState(); } m_StateStack.push(NewState); NewState->EnterState();}PushState() is quite straightforward. It pushes the state onto the top of the stack and calls its EnterState() function. If there was already a state in the stack, it call its ExitState() function.
void CStateStack::PopState() { if (m_StateStack.empty()) { return; } m_StateStack.top()->ExitState(); m_DeadStates.push(m_StateStack.back()); m_StateStack.pop(); if (!m_StateStack.empty()) { m_StateStack.top()->EnterState(); }}PopState() firstly checks to make sure that there is a state to pop. It them calls the current state's ExitState() function, removes the current state from the top of the state stack and adds it to the dead states stack. The EnterState() function is then called for the new current state, if it exists.
CStateInterface* CStateStack::GetCurrentState() { return m_StateStack.top();}GetCurrentState() returns the state that is curently on top of the stack. If you are using this function, make sure that you first check that GetStackSize() does not return 0. This is to ensure that there is actually a state on the stack.
size_t CStateStack::GetStackSize() { return m_StateStack.size();}GetStackSize() returns the number of states currently in the stack.
void CStateStack::PurgeStack(StateContainer& Stack) { while (!Stack.empty()) { delete Stack.top(); Stack.pop(); }}PurgeStack() deletes and removes the contents of a stack. It is used by Execute() and the destructor to clean up unwanted states.
APPLICATION
That's all you need to get a state stack up and running, but how do you use it? The first thing that has to be done is to split your game down into separate states, such as main menu, load screen, etc. Once you have that done, you push the first state onto the stack. Then you keep running the stack's Execute() funtion until there is no state left in the stack.
I'm going to build a very simple console menu system on our state stack.
To create a state you simply inherit a new class from the CStateInterface class and override the Update() function. You don't have to use the EnterState() and ExitState() functions, but they will come in very useful in more complicated apps.
Let's make two states, a main menu, and an intructions screen. For simplicity's sake, I'm going to use cin >> to an int. Be careful not to enter anything but a number if you're running this program because it'll get caught in an infinite loop.
class CMainMenu : public CStateInterface {public: void Update() { std::cout << std::endl << std::endl; std::cout << "Main Menu" << std::endl; std::cout << "1. Instructions" << std::endl; std::cout << "2. Exit" << std::endl; std::cout << "Your selection: "; int Selection; std::cin >> Selection; if (Selection == 1) { g_StateStack.PushState(new CInstructions); } else if (Selection == 2) { g_StateStack.PopState(); } }};As you can see, making a state is quite straightforward. CMainMenu inherits CStateInterface and overrides Update(). Most of the i/o stuff can be ignored, the important stuff is at the bottom of the function. When the user selects 1 to go to the instructions state, all it takes to go from the main menu to the instructions is to push the instructions state on to the top of the stack. If the user selects 2, the state pops itself from the stack. Once that happens there will be no states left and the program will exit.
The instructions state works similarly to the CMainMenu except its only option is to return back to the main menu. The source for that state is in the sample code which can be downloaded at the bottom of the page.
The loop that runs the state stack is equally simple.
CStateStack g_StateStack;int main(int argc, char *argv[]){ g_StateStack.PushState(new CMainMenu); while (g_StateStack.GetStackSize()) { g_StateStack.GetCurrentState()->Update(); g_StateStack.Execute(); } return 0;}This should be quite clear by now. The CMainMenu is pushed on to the top of the stack. Then the while loop runs untill the stack is empty, calling the current state's Update function and then the stack's Execute function. Though it could be baked into the stack class the Update function is kept independent. This allows you to perform any necessary logic before you call the Update() function (or the Render function if you add it), and sparates state logic from the stack class, allowing you to add paramaters without having to change the state class.
IMPROVEMENTS
This implementation is just the bare bones, so much can be added to make your state stack more useful for you. For example, you could pass a time delta to each update function for time based animations. You could also add extra events to handle key presses or mouse clicks.
One other improvement, though it would require a lot of work, would be to allow the user to precache states (i.e. to load states into memory and then to push them onto the stack whenever they're needed). You could also allow people to "store" states in the dead states stack for quickly reloading a state which had been popped. Perhaps you could allow for five states in the dead states stack which can then be repopped onto the live state stack for quick movements up and down a hierchical tree structure.
Some other improvements might be:
. Extending the CStateInterface to allow for building GUIs by allowing child elements (or substates) to be added, which are drawn and updated in front of the main state.
. To remove the global stack object you could give each state a pointer to the stack.
. Use a different container for the dead states, such as the std::map, to be able to easily reload states from the dead stack as described above.
CONCLUSION
It is quite clear that the state stack is a very useful way of moving between the different areas of your program. The sample app is not meant to show off the capabilities of the state stack (it barely does it justice at all), it is only meant to show you how state stacks can be implemented from beginning to end. There is a lot more that can be done with them.
For a suitably pretentious ending I think I'll quote the illustrious Neo, "Where we go from there is a choice I leave to you".
Get Source Here
REFERENCES
[GOF] Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides: Design Patterns: Elements of Reusable Object Oriented Software 1995 Addison Wesley
[CLRS] Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, Second Edition 2001 The MIT Press
[MSDN] http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vcstdlib/html/vclrfstackstack.asp
