Subscribe to 10 GOTO 10
6 Comments
Posted by
NickDMax 
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:
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:
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:
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:
Replace With:
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!
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:
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.
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:
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.
Categories: Programming Topic
Share This Entry:
6 Comments On This Entry
Page 1 of 1
iniaes
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).
A fantastic and very enlightening tutorial (I even recognise some of the code statements even though I don't know any C languages).
NickDMax
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.
iniaes
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
Page 1 of 1
Tags
My Blog Links
Recent Entries
Recent Comments
Search My Blog
0 user(s) viewing
0 Guests
0 member(s)
0 anonymous member(s)
0 member(s)
0 anonymous member(s)
|
|
| 