Jump to content

  • Log In with Google      Sign In   
  • Create Account


Using a stack for the gamestate


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
34 replies to this topic

#1 Toolmaker   Members   -  Reputation: 935

Like
0Likes
Like

Posted 09 August 2005 - 02:58 PM

[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

Toolmaker salutes mother Tiberia[My website] - [My Dune II Remake Dev Blog]/* -Earth is 98% full. Please delete anybody you can.*/

Sponsor:

#2 nilkn   Members   -  Reputation: 960

Like
0Likes
Like

Posted 09 August 2005 - 03:09 PM

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.

#3 ogracian   Members   -  Reputation: 180

Like
0Likes
Like

Posted 09 August 2005 - 03:14 PM

Hello,

I guess the following link would help you about it.

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

Regards,
Oscar

#4 joanusdmentia   Members   -  Reputation: 1060

Like
0Likes
Like

Posted 09 August 2005 - 03:25 PM

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
| LoadMenu
| MainMenu

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
| LoadMenu
| PlayGameState
| LoadMenu
| PlayGameState
| LoadMenu
| MainMenu

#5 hplus0603   Moderators   -  Reputation: 5104

Like
1Likes
Like

Posted 09 August 2005 - 03:33 PM

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.


#6 intrest86   Members   -  Reputation: 742

Like
0Likes
Like

Posted 09 August 2005 - 04:21 PM

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.

#7 Toolmaker   Members   -  Reputation: 935

Like
0Likes
Like

Posted 09 August 2005 - 11:06 PM

Quote:
Original post by joanusdmentia
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
| LoadMenu
| MainMenu

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
| LoadMenu
| PlayGameState
| LoadMenu
| PlayGameState
| LoadMenu
| MainMenu


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:

^ LoadMenu
| MainMenu

In LoadMenu, you could just do:

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

Toolmaker salutes mother Tiberia[My website] - [My Dune II Remake Dev Blog]/* -Earth is 98% full. Please delete anybody you can.*/

#8 Nitage   Members   -  Reputation: 810

Like
0Likes
Like

Posted 09 August 2005 - 11:15 PM

Maybe the Load state could pop itself from the stack?

#9 Toolmaker   Members   -  Reputation: 935

Like
0Likes
Like

Posted 10 August 2005 - 01:25 AM

That's exactly the idea

#10 xSKOTTIEx   Members   -  Reputation: 174

Like
0Likes
Like

Posted 10 August 2005 - 02:11 AM

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.

#11 Nitage   Members   -  Reputation: 810

Like
0Likes
Like

Posted 10 August 2005 - 02:32 AM

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.

#12 cozman   Members   -  Reputation: 583

Like
0Likes
Like

Posted 10 August 2005 - 08:44 AM

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

#13 Walt Destler   Members   -  Reputation: 186

Like
0Likes
Like

Posted 10 August 2005 - 09:43 AM

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]

#14 Toolmaker   Members   -  Reputation: 935

Like
0Likes
Like

Posted 10 August 2005 - 01:37 PM

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

Toolmaker salutes mother Tiberia[My website] - [My Dune II Remake Dev Blog]/* -Earth is 98% full. Please delete anybody you can.*/

#15 Aldacron   GDNet+   -  Reputation: 3111

Like
0Likes
Like

Posted 10 August 2005 - 08:02 PM

I use a system of Tasks, where a game state is just another task. Tasks are registered by name with a TaskManager. Each task has a lifecycle: init, activate, deactivate, shutdown. A task is initialized by the task manager when it is registered. At any time, a task can be activated/deactivated by name through the task manager. Activated tasks are added to the task manager's active task list. Because multiple tasks can be active at any given time, each task has a priority and the list is sorted accordingly. The task manager implements the game loop, and each frame it iterates the task list, calling a tick method on each task. When a task is deactivated, it is removed from the active task list. A task is shutdown when it is deregistered from the task manager.

Tasks can be anything. If you wanted to break the game state into layers, you could do so by using different tasks. As an example, when the LoadMenu exits and starts the game, pressing escape later could add the LoadMenu onto the task list behind the game task, and it would be displayed with the game in the background rahter than changing screens entirely. Background threads can also be used as tasks - the first tick starts the thread and each successive tick checks if it is finished.

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.

#16 GroZZleR   Members   -  Reputation: 820

Like
0Likes
Like

Posted 10 August 2005 - 09:00 PM

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.

#17 madeso   Members   -  Reputation: 554

Like
0Likes
Like

Posted 11 August 2005 - 12:44 AM

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* ;) ).

#18 Nitage   Members   -  Reputation: 810

Like
0Likes
Like

Posted 11 August 2005 - 12:57 AM

Quote:
Original post by sirGustav
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* ;) ).


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.

#19 5MinuteGaming   Members   -  Reputation: 274

Like
0Likes
Like

Posted 11 August 2005 - 02:05 AM

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



#20 madeso   Members   -  Reputation: 554

Like
0Likes
Like

Posted 11 August 2005 - 02:06 AM

Quote:
Original post by Nitage
Quote:
Original post by sirGustav
What'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.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS