Subscribe to 10 GOTO 10        RSS Feed
-----

Beginner Series: Finite State Machine

Icon 6 Comments
Lets take a common little riddle and encode it into a little game.

The Fox, then Chicken, and Grain
Imagine you are a farmer trying to get home with your pet fox, your chicken, and a bag of grain. You come upon a river you need to cross and there is a small boat just big enough for you and ONE other item. However, if you were to ever leave the fox with the chicken the fox would gobble up the chicken, if you left the chicken and grain together the chicken would get into the grain. So how do you use this boat to cross the river?

Now the current "state" can be viewed as the positions of the players. For example the puzzle begins in the state of all players on the one side of the river (lets say the left side). So the initial state can be represented by (mFCG|) where m is the man, F is the fox, C is the chicken, G is the grain. If the man crosses with the fox then the state becomes: (CG|mF) with the chicken eating the grain on the left bank and the man and fox on the right bank.

Since we have 4 players each with two possible states so there is a neat little combinatorics question of how many states are possible? Well in binary a nibble has 4 bit each with 2 possible states and so there are 16 possible states for a nibble and likewise there are 16 possible states for our man, fox, chicken, grain problem. This set of all possible states is called a "state space" and ours can be listed as:

(mFCG|)
(mFC|G)
(mFG|C)
(mF|CG)
(mCG|F)
(mC|FG)
(mG|FC)
(m|FCG)
(FCG|m)
(FC|mG)
(FG|mC)
(F|mCG)
(CG|mF)
(C|mFG)
(G|mFC)
(|mFCG)


In out state space I have colored some that represent a "loosing state" -- Orange means the
chicken ate the grain, and Red means the fox ate the chicken -- I assume that the fox eats faster than the chicken. So we can consolidate those states making for a total of either 11 states or as I would do it 12 states:

(mFCG|)
(mFC|G)
(mFG|C)
(mCG|F)
(mC|FG)
(FG|mC)
(F|mCG)
(C|mFG)
(G|mFC)
(|mFCG)
(Fox eats Chicken)
(Chicken eats Grain)


Now the neat thing about this state space is that there is a clear process that changes from one state to another: Crossing the river in the boat. Either the man alone, or with one other item. Given this we can arrange these states into something called a "state diagram" showing the possible transitions:

Attached Image

I took a few short cuts and did not include all of the transitions to the "error states" (it gets really messy when I include those) but the diagram clearly shows all of the valid moves of the puzzle. For example from the starting position if I moved the chicken, returned and them moved the fox I would be in state #8 (Gm|FC).

So we can now use this diagram to easily see which sets of moves successfully navigate the states to wind up in the winning state. With this knowledge we can construct an if-then or switch-case based program to navigate the various states:
#include <iostream>
#include <string>
#include <cctype>

using namespace std;

//Give a name to our states
enum MFCG_STATES {
    LOSE_FC        = -3,
    LOSE_CG        = -2,
    ERROR_INVALID   = -1,
    MFCG_BEGIN      = 0,
    FG_MC           = 1,
    MFG_C           = 2,
    F_MCG           = 3,
    MFC_G           = 4,
    C_MFG           = 5,
    MC_FG           = 6,
    WIN_MFCG        = 7,
    G_MFC           = 8,
    MCG_F           = 9,    
};

// A class to encapsulate our FSM
class MFCG_Game {
    MFCG_STATES state;
    string moves; //used to get a string representation of the moves
    static const char* GameStates[];  //Used to get a string interpretation of our current state
    public:
    
    MFCG_Game() : state(MFCG_BEGIN), moves("") { }    
    string getStateString() const;
    string getMoves() const { return moves; }
    MFCG_STATES changeState(char ch);
    bool isWin() const  { return state == WIN_MFCG; }
    bool isLose() const { return state == LOSE_CG || state == LOSE_FC;  }
    bool isInPlay() const { return state != LOSE_CG && state != LOSE_FC && state != ERROR_INVALID; }
    bool isInvalid() const { return state == ERROR_INVALID; }
    bool loseChicken() const { return state == LOSE_FC; }
    bool loseGrain() const { return state == LOSE_CG; }
};

int main() {
    MFCG_Game game, backupGame;
    while (true) {
        char chIn;
        backupGame = game; // save a copy of our current game to back out to
        cout << "Hello, the current state is: \n" 
             << game.getStateString() << "\n\n"
             << "Your Move is (M,F,C,G): ";
        cin >> chIn;
        game.changeState(chIn);
        if (game.isWin()) {
            cout << "\nYou DID it: " << game.getMoves() << endl;
            break;
        } else if (game.isLose()) {
            cout << "Your ";
            if (game.loseChicken()) {
                cout << "Chicken ";
            } else {
                cout << "Grain ";
            }
            cout << "was lost!\nGame Over:  " << game.getMoves() << endl;
            break;
        } else if (game.isInvalid()) {
            cout << "\n  Invalid move: try again  \n"<< endl;
            game = backupGame; // restore backup and allow the user to try again.
        }    
    }
         

    return 0;
}

const char* MFCG_Game::GameStates[]= {
    "Fox Eats Chicken",
    "Chicken Eats Grain",
    "ERROR: Invalid Move",
    "(M)an, (F)ox, (C)hicken, and (G)rain left bank",
    "Fox and gain on left bank, the (M)an and (C)hicken right",
    "(M)an, (F)ox, (G)rain on left bank; Chicken on right bank.",
    "Fox on left bank; (M)an, (C)hicken (G)rain on right bank.",
    "(M)an, (F)ox, (C)hicken on left bank; Grain on right bank.",
    "Chicken on left bank; (M)an, (F)ox, (G)rain on right bank.",
    "(M)an, (C)hicken on left bank; Fox, Grain on right bank.",
    "(M)an, (F)ox, (C)hicken (G)rain on right bank.",
    "Grain on left bank; (M)an, (F)ox, (C)hicken on right bank.",
    "(M)an, (C)hicken (G)rain on left bank; Fox on right bank.",
};

string MFCG_Game::getStateString() const {
    return string(GameStates[state+3]);
}

MFCG_STATES MFCG_Game::changeState(char ch) {
    ch = toupper(ch);
    switch(state) {
        case MFCG_BEGIN: {
            switch(ch) {
                case 'M': {
                    state = LOSE_FC;
                    break;
                }
                case 'F': {
                    state = LOSE_CG;
                    break;
                }
                case 'C': {
                    state = FG_MC;
                    break;
                }
                case 'G': {
                    state = LOSE_FC;
                    break;
                }
                default: {
                    state = ERROR_INVALID;
                }
            }
            break;
        }
        case FG_MC: {
            switch(ch) {
                case 'M': {
                    state = MFG_C;
                    break;
                }
                case 'F': {
                    state = ERROR_INVALID;
                    break;
                }
                case 'C': {
                    state = MFCG_BEGIN;
                    break;
                }
                case 'G': {
                    state = ERROR_INVALID;
                    break;
                }
                default: {
                    state = ERROR_INVALID;
                }
            }
            break;
        }
        case MFG_C: {
            switch(ch) {
                case 'M': {
                    state = FG_MC;
                    break;
                }
                case 'F': {
                    state = G_MFC;
                    break;
                }
                case 'C': {
                    state = ERROR_INVALID;
                    break;
                }
                case 'G': {
                    state = F_MCG;
                    break;
                }
                default: {
                    state = ERROR_INVALID;
                }
            }
            break;
        }
        case F_MCG: {
            switch(ch) {
                case 'M': {
                    state = LOSE_CG;
                    break;
                }
                case 'F': {
                    state = ERROR_INVALID;
                    break;
                }
                case 'C': {
                    state = MFC_G;
                    break;
                }
                case 'G': {
                    state = MFG_C;
                    break;
                }
                default: {
                    state = ERROR_INVALID;
                }
            }
            break;
        }
        case MFC_G: {
            switch(ch) {
                case 'M': {
                    state = LOSE_FC;
                    break;
                }
                case 'F': {
                    state = C_MFG;
                    break;
                }
                case 'C': {
                    state = F_MCG;
                    break;
                }
                case 'G': {
                    state = ERROR_INVALID;
                    break;
                }
                default: {
                    state = ERROR_INVALID;
                }
            }
            break;
        }
        case C_MFG: {
            switch(ch) {
                case 'M': {
                    state = MC_FG;
                    break;
                }
                case 'F': {
                    state = MFC_G;
                    break;
                }
                case 'C': {
                    state = ERROR_INVALID;
                    break;
                }
                case 'G': {
                    state = MCG_F;
                    break;
                }
                default: {
                    state = ERROR_INVALID;
                }
            }
            break;
        }
        case MC_FG: {
            switch(ch) {
                case 'M': {
                    state = C_MFG;
                    break;
                }
                case 'F': {
                    state = ERROR_INVALID;
                    break;
                }
                case 'C': {
                    state = WIN_MFCG;
                    break;
                }
                case 'G': {
                    state = ERROR_INVALID;
                    break;
                }
                default: {
                    state = ERROR_INVALID;
                }
            }
            break;
        }
        case WIN_MFCG: {
            switch(ch) {
                case 'M': {
                    state = LOSE_FC;
                    break;
                }
                case 'F': {
                    state = LOSE_CG;
                    break;
                }
                case 'C': {
                    state = MC_FG;
                    break;
                }
                case 'G': {
                    state = LOSE_FC;
                    break;
                }
                default: {
                    state = ERROR_INVALID;
                }
            }
            break;
        }
        case G_MFC: {
            switch(ch) {
                case 'M': {
                    state = LOSE_FC;
                    break;
                }
                case 'F': {
                    state = MFG_C;
                    break;
                }
                case 'C': {
                    state = MCG_F;
                    break;
                }
                case 'G': {
                    state = ERROR_INVALID;
                    break;
                }
                default: {
                    state = ERROR_INVALID;
                }
            }
            break;
        }
        case MCG_F: {
            switch(ch) {
                case 'M': {
                    state = LOSE_CG;
                    break;
                }
                case 'F': {
                    state = ERROR_INVALID;
                    break;
                }
                case 'C': {
                    state = G_MFC;
                    break;
                }
                case 'G': {
                    state = C_MFG;
                    break;
                }
                default: {
                    state = ERROR_INVALID;
                }
            }
            break;
        }
        default: {
            state = ERROR_INVALID;
        }
    }
    moves += ch;
    return state;   
}


HOWEVER -- writing this long switch-case or if-else-if blocks can be a little cumbersome. To aid in keeping everything strait I generated a little table:

State       M          F              C              G
MFCG_BEGIN  LOSE_FC    LOSE_CG        FG_MC          LOSE_FC
FG_MC       MFG_C      ERROR_INVALID  MFCG_BEGIN     ERROR_INVALID
MFG_C       FG_MC      G_MFC          ERROR_INVALID  F_MCG
F_MCG       LOSE_CG    ERROR_INVALID  MFC_G          MFG_C
MFC_G       LOSE_FC    C_MFG          F_MCG          ERROR_INVALID
C_MFG       MC_FG      MFC_G          ERROR_INVALID  MCG_F
MC_FG       C_MFG      ERROR_INVALID  WIN_MFCG       ERROR_INVALID
WIN_MFCG    LOSE_FC    LOSE_CG        MC_FG          LOSE_FC
G_MFC       LOSE_FC    MFG_C          MCG_F          ERROR_INVALID
MCG_F       LOSE_CG    ERROR_INVALID  G_MFC          C_MFG


From this I can actually generate the code from RegEx! In Programmer's notepad that would be done by taking off the top line and running this RegEx on "ReplaceAll"

Find What:
^(\S*)\s*(\S*)\s*(\S*)\s*(\S*)\s*(\S*)$

Replace With:
case \1: {\n\tswitch(ch) {\n\t\tcase 'M': {\n\t\t\tstate = \2;\n\t\t\tbreak;\n\t\t}\n\t\tcase 'F': {\n\t\t\tstate = \3;\n\t\t\tbreak;\n\t\t}\n\t\tcase 'C': {\n\t\t\tstate = \4;\n\t\t\tbreak;\n\t\t}\n\t\tcase 'G': {\n\t\t\tstate = \5;\n\t\t\tbreak;\n\t\t}\n\t\tdefault: {\n\t\t\tstate = ERROR_INVALID;\n\t\t}\n\t}\n\tbreak;\n}


This is how I generated the code shown above. This is interesting but not everyone thinks about using regex to save some typing AND converting that table to if-else or switch-case blocks can be quite a pain. We could break things up into functions for each state and that would make the logic a little clearer but there is a better way:

Looking at the table I already showed you can use a program to "generate" the code needed to implement it. So would it be possible to just skip a step and use the table directly in the code? YES!

#include <iostream>
#include <string>
#include <cctype>

using namespace std;

enum MFCG_STATES {
    LOSE_FC        = -3,
    LOSE_CG        = -2,
    ERROR_INVALID   = -1,
    MFCG_BEGIN      = 0,
    FG_MC           = 1,
    MFG_C           = 2,
    F_MCG           = 3,
    MFC_G           = 4,
    C_MFG           = 5,
    MC_FG           = 6,
    WIN_MFCG        = 7,
    G_MFC           = 8,
    MCG_F           = 9,    
};

const MFCG_STATES StateTable[][4] = {
    {LOSE_FC,      LOSE_CG,        FG_MC,          LOSE_FC},       //MFCG_BEGIN
    {MFG_C,        ERROR_INVALID,  MFCG_BEGIN,     ERROR_INVALID}, //FG_MC
    {FG_MC,        G_MFC,          ERROR_INVALID,  F_MCG},         //MFG_C
    {LOSE_CG,      ERROR_INVALID,  MFC_G,          MFG_C},         //F_MCG
    {LOSE_FC,      C_MFG,          F_MCG,          ERROR_INVALID}, //MFC_G
    {MC_FG,        MFC_G,          ERROR_INVALID,  MCG_F},         //C_MFG
    {C_MFG,        ERROR_INVALID,  WIN_MFCG,       ERROR_INVALID}, //MC_FG
    {LOSE_FC,      LOSE_CG,        MC_FG,          LOSE_FC},       //WIN_MFCG
    {LOSE_FC,      MFG_C,          MCG_F,          ERROR_INVALID}, //G_MFC
    {LOSE_CG,      ERROR_INVALID,  G_MFC,          C_MFG},         //MCG_F
};


class MFCG_Game {
    MFCG_STATES state;
    string moves;
    static const char* GameStates[];
    static const MFCG_STATES StateTable[][4];
    public:
    
    MFCG_Game() : state(MFCG_BEGIN), moves("") { }    
    string getStateString() const;
    string getMoves() const { return moves; }
    MFCG_STATES changeState(char ch);
    bool isWin() const  { return state == WIN_MFCG; }
    bool isLose() const { return state == LOSE_CG || state == LOSE_FC;  }
    bool isInPlay() const { return state != LOSE_CG && state != LOSE_FC && state != ERROR_INVALID; }
    bool isInvalid() const { return state == ERROR_INVALID; }
    bool loseChicken() const { return state == LOSE_FC; }
    bool loseGrain() const { return state == LOSE_CG; }
};

int main() {
    MFCG_Game game, backupGame;
    while (true) {
        char chIn;
        backupGame = game; // save a copy of our current game to back out to
        cout << "Hello, the current state is: \n" 
             << game.getStateString() << "\n\n"
             << "Your Move is (M,F,C,G): ";
        cin >> chIn;
        game.changeState(chIn);
        if (game.isWin()) {
            cout << "\nYou DID it: " << game.getMoves() << endl;
            break;
        } else if (game.isLose()) {
            cout << "Your ";
            if (game.loseChicken()) {
                cout << "Chicken ";
            } else {
                cout << "Grain ";
            }
            cout << "was lost!\nGame Over:  " << game.getMoves() << endl;
            break;
        } else if (game.isInvalid()) {
            cout << "\n  Invalid move: try again  \n"<< endl;
            game = backupGame; // restore backup and allow the user to try again.
        }    
    }
         

    return 0;
}

const char* MFCG_Game::GameStates[]= {
    "Fox Eats Chicken",
    "Chicken Eats Grain",
    "ERROR: Invalid Move",
    "(M)an, (F)ox, (C)hicken, and (G)rain left bank",
    "Fox and gain on left bank, the (M)an and (C)hicken right",
    "(M)an, (F)ox, (G)rain on left bank; Chicken on right bank.",
    "Fox on left bank; (M)an, (C)hicken (G)rain on right bank.",
    "(M)an, (F)ox, (C)hicken on left bank; Grain on right bank.",
    "Chicken on left bank; (M)an, (F)ox, (G)rain on right bank.",
    "(M)an, (C)hicken on left bank; Fox, Grain on right bank.",
    "(M)an, (F)ox, (C)hicken (G)rain on right bank.",
    "Grain on left bank; (M)an, (F)ox, (C)hicken on right bank.",
    "(M)an, (C)hicken (G)rain on left bank; Fox on right bank.",
};

const MFCG_STATES MFCG_Game::StateTable[][4] = {
    //M            F               C               G                 Current State
    {LOSE_FC,      LOSE_CG,        FG_MC,          LOSE_FC},       //MFCG_BEGIN
    {MFG_C,        ERROR_INVALID,  MFCG_BEGIN,     ERROR_INVALID}, //FG_MC
    {FG_MC,        G_MFC,          ERROR_INVALID,  F_MCG},         //MFG_C
    {LOSE_CG,      ERROR_INVALID,  MFC_G,          MFG_C},         //F_MCG
    {LOSE_FC,      C_MFG,          F_MCG,          ERROR_INVALID}, //MFC_G
    {MC_FG,        MFC_G,          ERROR_INVALID,  MCG_F},         //C_MFG
    {C_MFG,        ERROR_INVALID,  WIN_MFCG,       ERROR_INVALID}, //MC_FG
    {LOSE_FC,      LOSE_CG,        MC_FG,          LOSE_FC},       //WIN_MFCG
    {LOSE_FC,      MFG_C,          MCG_F,          ERROR_INVALID}, //G_MFC
    {LOSE_CG,      ERROR_INVALID,  G_MFC,          C_MFG},         //MCG_F
};

string MFCG_Game::getStateString() const {
    return string(GameStates[state+3]);
}

MFCG_STATES MFCG_Game::changeState(char ch) {
    ch = toupper(ch);
    //convert between chars and indexes to our array:
    int index = -1;
    if (ch == 'M') { index = 0; }
    if (ch == 'F') { index = 1; }
    if (ch == 'C') { index = 2; }
    if (ch == 'G') { index = 3; }
    if (state >= 0 && index >= 0) {
        state = StateTable[state][index];
    } else {
        state = ERROR_INVALID;
    }
    moves += ch;
    return state;   
}




Now the code is much more compact and the logic is really mostly tied up in this StateTable. Basically this ended up being a lookup table for states!

So what is a Finite State Machine? Well it is a finite set of states (state space) and a set of transition rules that clearly delineate how to move from one state to another. If you think about it MANY processes and objects are easily modeled as FSMs!

Lets take for instance a simple widget vending machine. Lets say that a widget costs 35 cents. The machine can take coins: nickels, dimes, quarters. The "state" is the current sum of the coins entered + "vend" and "return coin".

So we can make a table:
State      Nickel      Dime        Quarter
0           5           10          25
5           10          15          30
10          15          20          Vend
15          20          25          Return
20          25          30          Return
25          30          Vend        Return
30          Vend        Return      Return
Vend        *0          *0          *0  
Return      *           *           * 


In this FSM we really want our vending machine to preform some action in the special states of Vend and Return and our state is a sum of coins so maybe this one would work better as code rather than implemented purely as a table.

FSM are used to model NPCs in games, they are used to model parsers for computer languages and file formats, they are used to model devices such as ATMs, elevators, vending machines, DVD players. FSM are used for fast searches. Anything that can be described as a defined set of states (state space) and a defined set of transitions between those states can be represented with a FSM!

In theory of computation classes and deeper CS classes the theory of FSM and other finite automata can get quite intimidating but FSMs themselves are really very simple.

Challenges:

Please put all answers in spoiler tags:[spoiler] answer here [spoiler]

#1. Write a FSM for a vending machine:
Beginner: bubble gum, costs 35 cents, if over reject all coins.
Intermediate: Soda machine with 3 sodas of different prices. Give change.

#2. What is the size of the state space:
A game of checkers?
Estimate a game of chess (without promotion)?
A Rubics cube?

Can FSM's be used to model the games mentioned above? Would this be a good way to implement them?

#3. Describe how one might use a FSM to model behavior of a NPC in a game.

6 Comments On This Entry

Page 1 of 1

iniaes Icon

05 April 2011 - 07:15 PM
I see what you did there :)

A fantastic and very enlightening tutorial (I even recognise some of the code statements even though I don't know any C languages).
0

NickDMax Icon

05 April 2011 - 09:11 PM
Yes, thank you very much for the idea! I have been looking for a way to talk about finite state machines. The main point was the technique less than the syntax of the language. I was initially going to respond to your post with an example in Liberty BASIC but its not exactly a free platform and so I decided to stick with what I know rather than download and play around in something that I would only be able to use for a little while.
0

iniaes Icon

06 April 2011 - 05:33 AM
that's fair enough, I can see what you are getting at though, and I have been looking at doing something similar, but algebraically, where each bank is a constant, and the farmer and cargoes are represented numerically in the logic. I'm glad that my idea game you the inspiration to write this, it is a really interesting topic, and now knowing about this way of doing things, it is something else | can try and do as an other version of the logic for my games. I do not know if i can implement the code in a similar way using LB but that is all part of th learning process :)
0

diego_pmc Icon

07 April 2011 - 12:24 PM
Question #2
Spoiler


Question #3
Spoiler
1

KYA Icon

09 April 2011 - 09:10 AM
Great post nick!
1

NickDMax Icon

09 April 2011 - 01:54 PM
@diego_pmc -- thank you very much for your answers. I really enjoyed thinking about these questions. Here are my thoughts on the ones you commented on:
Spoiler
1
Page 1 of 1

April 2014

S M T W T F S
  12345
6789101112
13141516171819
20 212223242526
27282930   

Recent Entries

Search My Blog

0 user(s) viewing

0 Guests
0 member(s)
0 anonymous member(s)