Implementing game state without switch statements everywhere?

Question

Executive summary

Are there any good tutorials on Game State FSMs, particularly OOP/OOD-based and not switch-statement-based?

Summary

Is there a practical process for creating a game state engine other than using a switch statement, preferably with examples? Wikipedia's event-driven FSM article only shows a switch statement and the article on FSMs is strictly theory-based with no practical examples.

Background

Currently all my games use a very simplistic game state "engine" that uses switch statements everywhere. It's very messy, violates DRY horribly, and does not scale very well.

Each state is treated as a level and must be checked at all three points throughout the game loop, i.e. Input, Processing, and Render. If a level or screen is added it must be added to all the switch statements.

Practical example of recreation of pac-man for educational purposes (seriously, this was a school project a few years ago):

enum STATE {
    LOADING,
    TITLE,
    LEVEL_ONE,
    LEVEL_TWO,
    // ...
    WIN,
    GAME_OVER,
    CREDITS,
}GAME_STATE;


void Input() {
    // ...

    switch(GAME_STATE) {
        case LOADING:
            break;
        case TITLE:
            break;
        case LEVEL_ONE:
        case LEVEL_TWO:
        // ...
            InputCommon();
            break;
        case WIN:
        case GAME_OVER:
            if(keyboard->KeyDown(KEY_ENTER))
                GAME_STATE = CREDITS;
            break;
        case CREDITS:
            if(keyboard->isKeyPressed())
                quit = true;
            break;
    }
}

void Processing(int dead) {

    // ...

    switch(GAME_STATE) {
        case LOADING:
            break;
        case TITLE:
            break;
        case LEVEL_ONE:
        case LEVEL_TWO:
        // ...
            ProcessLevel();
            if(GAME_STATE == LEVEL_SEVEN) {
                // ...
            }
            break;
        case WIN:
            break;
        case GAME_OVER:
            break;
        case CREDITS:
            break;
    }
}

void Render() {
    // ...

    switch(GAME_STATE) {
        case LOADING:
            break;
        case TITLE:
            sh->Draw(_gw->GetBackBuffer(), sh->Index(0));
            break;
        case LEVEL_ONE:
        case LEVEL_TWO:
        // ...

            // ...
            break;
        case WIN:
            sh->Draw(_gw->GetBackBuffer(), sh->Index(3));
            break;
        case GAME_OVER:
            sh->Draw(_gw->GetBackBuffer(), sh->Index(1));
            break;
        case CREDITS:
            sh->Draw(_gw->GetBackBuffer(), sh->Index(2));
            break;
    }

    //End render process, display to screen.
    _gw->EndRender();

}

Answer 1

If you don't mind a reference to a book, there's an article named "Large-Scale Stack-Based State Machines" in Game Programming Gems 5 which provides a very good implementation of what you seek. I've been using a variation of it for the last few years, and like it a lot. Most of the insights that I got from that article, I've already talked about in this answer, so there's no need to repeat myself.

But since it might not be easy to get your hands on that book, here's a free alternative. The first chapter of the Gamebryo Textbook describes an implementation which is pretty much based on the one presented in Game Programming Gems 5, and you can also find the source code here.

(Update: The links above are no longer valid, and I can't seem to find where they have been relocated. If someone does, please edit this answer)

And finally, despite being in C# and XNA, this sample from Microsoft provides a simple implementation which should be pretty easy to follow and convert to C++.

Answer 2

The first step really is to just move the contents of your switch statements to data files. Level layouts and such should be in map files. Special level logic can be moved to scripts, or at the veryeast moved off into their own functions/classes. You can register these data files or C functions at startup with a level manager, and your switch statements then turn into m_CurrentLevel->update().

Note that a lot of logic really should be common. There's little reason for each level to have its own input handling, since good non-irritating games generally have only one play style. Of course exceptions abound, especially if you implement menus had a game state. Even then, though, abstract things away: have a menu handler that runs for any active menu state, a gameplay handler for game play states, etc.

If in doubt, just think in terms of (good) OOP design.

Answer 3

I would tend to create a Scene object that all the various game states inherit from, and just create a variable called "currentScene" in the Main object. Then instead of a switch statement in the main loop, just call currentScene->Update(); each Scene would know what it specifically needs to do for input handling and rendering. To switch the game's state just switch which Scene is in currentScene.

Answer 4

Have a look at the Boost Statechart library. I recently started using it after many years of trying out slightly different ways of implementing FSMs, and it's definitely my current favourite! There are some oddities that stop it from being perfect (see 'state' class vs. 'simple_state' for example), but it provides some very useful features, and allows you to write state machines that are far more compact and expressive than the equivalent switch-based code.

http://www.boost.org/doc/libs/1_49_0/libs/statechart/doc/tutorial.html

Answer 5

Yes, there is also something called a behavior tree, which is used for AI. If you want to research them, I would suggest starting here:

Introduction to Behavior Trees

Björn Knafla explains in very easy terms what is involved with this system. I'm currently implementing this on my internship. The advantage to a behavior tree is that you're making a decision instead of setting a state.

For instance, let's say you want to build some AI for the ghosts in Pacman. You want them to follow Pacman if they see him and stop following him when they lost sight of him. So, in a behavior tree:

Walking
-- Am I following Pacman?
-- -- Have I lost sight of Pacman?
-- -- -- Stop following Pacman.
-- -- -- <End>
-- (Else)
-- -- Do I see Pacman?
-- -- -- Follow Pacman
-- -- -- <End>

So, first time we walk the tree:

Walking 
Am I following Pacman? -> No
Else
Do I see Pacman? -> Yes
Follow Pacman
End

Next frame:

Walking
Am I following Pacman? -> Yes
Have I lost sight of Pacman? -> No
End

The trick is that the behavior tree gets evaluated every frame, but it only affects behavior. So, in the case of the Ghost AI, it only determines where to walk to, but it doesn't actually walk to anywhere.

Instead, you have a separate piece of code that looks something like this:

if (m_BrainData->target == StateTarget::ePacman)
{
    MoveTowardsPacman();
}
else
{
    MoveRandomly();
}

Why is that so significant? Because now you can blend between states. Now, if you want a Ghost to run a "scared" animation whenever he sees Pacman powered up, you simply evaluate the Ghost's "brain":

if (
   m_BrainData->target == StateTarget::ePacman && 
   m_BrainData->emotion == StateEmotion::ePanic
)
{
    m_AnimationPanic->Render();
    if (m_AnimationPanic->Finished())
    {
         m_BrainData->emotion = StateEmotion::eFleeing;
    }
}
else
{
    m_Animation->Render();
}

And you add the states to the behavior tree:

Walking
-- Am I following Pacman?
-- -- Have I lost sight of Pacman?
-- -- -- Stop following Pacman.
-- -- -- <End>
-- (Else)
-- -- Do I see Pacman?
-- -- -- Is Pacman powered up?
-- -- -- -- Am I not fleeing?
-- -- -- -- -- Panic
-- -- -- -- -- <End>
-- -- -- -- (Else)
-- -- -- -- -- Flee
-- -- -- -- -- <End>
-- -- -- (Else)
-- -- -- -- Follow Pacman
-- -- -- <End>