Introduction

A finite state machine is a highly useful tool for programmers in general and for video game programmers in particular. If you’re not familiar with the notion, think about the Finite State Machine (FSM) as a GameBoy, and the States as different cartridges or games.

The GameBoy can only have one game running at any time (or no game at all, in which case it’s not very useful). Obviously, all cartridges share some characteristics (shape, connection pins, etc.…) that allow the GameBoy to interact with any game without knowing or caring what it actually does, just plug it in and it works.

There is one last, important, characteristic that defines this system. Each “game” or state has the rules to decide when to change to another different game (this kind of fucks up the metaphor, but I could not find any better).

So, code-wise, this would be a system as follows:

The FSM has one state active, which it updates every cycle. At any moment, the FSM can be told to change to a different state. All states inherit from the State class, and have a common interface so the FSM doesn’t need to know what they do internally, just call the appropriate functions.

FSM

A classic FSM pseudo-code has a structure as follows:

Code Snippet
 class FSM
{
    // Current state the FSM uses
    State* currentState;
 
    // Calls the Update function of 
    // the currentState
    Update();
 
    // Calls exit of the currentState
    // sets newState as currentState
    // call enter of currentState
    ChangeState(State * newState);
};
 

State

And a base state pseudo-code has the following structure:

Code Snippet
 class State
{
    // Pointer to the parent FSM
    FSM* fsmReference;
 
    // Called when the state is initialized
    // by the FSM
    public virtual void Enter();
 
    // Called when the state is ended by the
    // FSM
    public virtual void Exit();
 
    // Called every update cycle by the FSM
    protected virtual void Update();
}
 

Actual states are not instantiated, only derived states (in our example ShootEnemy, Defend, etc. )

Making it Useful

This basic FSM has several problems or shortcomings that limit it’s use, so let’s have a look at some of them.

Changing State at the Proper Time

Problem

The main flaw the basic FSM pattern has is the fact that at any moment, the current state can request the FSM to change to a different state. When this happens, the following steps take place:

CurrentState->Exit();
CurrentState = NewState;
CurrentState->Enter() // This is the new state

If the fsmReference->ChangeState() call was in the middle of the the Update function, this can leave the state in an undefined state, and propagate errors later on.

Solution

We shall make a request mechanism in the FSM, instead of changing the state, we will request the FSM to change to a state, and the FSM after the state update will change to a different state. For this we replace the ChangeState function for a RequestoReplaceState, and a DoStateReplacement.

Check this pseudo-code for a clearer idea:

Code Snippet
 class FSM // With delay state change
{
private:
    // Current state the FSM uses
    State* currentState;
 
    // Temporal pointer to the new state
    State* newState;
 
    // Flag indicating wheter to change state
    bool requestedStateChange;
 
    // Calls the Update function of 
    // the currentState
    void Update();
 
    // If a requested state pending, 
    // change to new state
    void DoStateReplacement();
 
    // Calls exit of the currentState
    // sets newState as currentState
    // call enter of currentState
    void RequestReplaceState(State * newState);
};
 
void FSM::Update() 
{
    if(requestedStateChange)
    {
        DoStateReplacement();
    }
    else if(this.currentState != null)
    {
        currentState->Update();
    }
}
 
void FSM::RequestReplaceState(SinState newState)
{
    nextState = newState;
    requestedStateChange = true;
}
 
void FSM::DoStateReplacement()
{
    if(nextState == null)
    { return; }
    
    requestedStateChange = false;
 
    if(currentState != null)
    { currentState->Exit();    }
    
    currentState = this.nextState;
    nextState = null;
    
    currentState->Enter();
}
 

Push & Pop

Problem

Now we have a FSM that won’t inadvertently introduce subtle ninja bugs when we’re not looking, and can replace the current state for another. But we want to add to the FSM the ability of when we change to a state, to push the current state back into memory, to be popped later on. This might be useful for example in this scenario:

Guard.state = patrolling –> Hears sound
- Guard.state = goSeeDisturbance , PushBack( patrolling )
- Guard –> Doesn’t find anything in sound source. Pop ( goSeeDisturbance )
Guard.state = patrolling

Instead of destroying the patrolling state and then having to create it again, we just push it back, store it, and once the temporal state (goSeeDisturbance) is over, we resume patrolling.

Solution

To properly do this we need to add a pause functionality to our states. Notice a very important detail that is that the Pause / Update / Resume functions, overloaded in the base classes, are no longer called by the FSM but instead we have Manager functions (ManagerUpdate, ManagerPause, ManagerResume) that are called by the FMS, while derived classes (from State) just override the same version without the “Manager” part. This allows us to add some extra functionality to all Update / Pause / Resume calls of all derived classes. With this, we can implement pause / resume, by letting the user specify what is going to happen in his state when it pauses / resumes, while doing the maintenance work (setting flags and safety checks) in the manager version. Check the code for a clearer idea:

Code Snippet
 class State
{
    // Pointer to the parent FSM
    FSM* fsmReference;
 
    // Indicates whether the state is paused
    bool isPaused;
 
    // Overriden in base clases to put pause
    // logic
    protected virtual void Pause();
 
    // Overriden in base clases to put 
    // resume logic
    protected virtual void Resume();
 
    // Called when the state is initialized
    // by the FSM
    public virtual void Enter();
 
    // Called when the state is ended by the
    // FSM
    public virtual void Exit();
 
    // NOT CALLED BY FSM ANYMORE
    protected virtual void Update();
 
    // Called by the FSM every update 
    // cycle
    public void ManagerUpdate();
    
    // CAlled by FSM on pause
    public void ManagerPause();
 
    // Called by FSM on resume
    public void ManagerResume();    
}
 
 
void State::ManagerUpdate()
{
    if(!this.isPaused) 
    { this.Update(); }
}
    
void State::ManagerPause()
{
    this.isPaused = true;
    this.Pause();
}
    
void State::ManagerResume()
{
    this.isPaused = false;
    this.Resume();
}
 

And add a push & pop mechanism to the FSM, very similar to the replace mechanism, but we store the pushed state in a variable, to restore it later. This is only an example, so it’s not very useful. For it to be useful we would need a list of pushed states, because that would allow us to push and pop as much as we wanted.

Code Snippet
 class FSM
{
    // Current state the FSM uses
    State* currentState;
 
    // Calls the Update function of 
    // the currentState
    Update();
 
    // Calls exit of the currentState
    // sets newState as currentState
    // call enter of currentState
    ChangeState(State * newState);
 
    
    // Stores a pushed state. 
    // Make this->a list to store a pile of states.
    private State pushedState = null;
    
    
    // Indicates whether a new state push 
    // has been requested.
    private bool requestedStatePush
    
    
    // Indicates whether a new state pop has 
    // been requested.
    private bool requestedStatePop;
 
    void DoStatePop();
 
    void RequestStatePop();
 
    void DoStatePush();
 
    void RequestPushState(State newState);
};
 
void FSM::Update() 
{
    if(this->requestedStateChange)
    {
        this->DoStateReplacement();
    }
    else if(this->requestedStatePush)
    {
        this->DoStatePush();
    }
    else if(this->requestedStatePop)
    {
        this->DoStatePop();
    }
    else if(this->currentState != null)
    {
        this->currentState.ManagerUpdate();
    }
}
 
void FSM::RequestPushState(State newState)
{
    this->nextState = newState;
    this->requestedStatePush = true;
}
 
void FSM::DoStatePush()
{
    if(this->nextState == null)
    {
        Log.Write("ERROR! Attempting state push in null state");
        return;
    }
 
    if(this->currentState == null)
    {
        Log.Write("ERROR! Attempting state push back null state");
        return;
    }
    
    this->requestedStatePush = false;
    this->pushedState = this->currentState;
    
    this->pushedState.ManagerPause();
    
    this->currentState = this->nextState;
    this->nextState = null;
    
    this->currentState.SetWasPushed(true);
    this->currentState.Enter();
}
 
void FSM::RequestStatePop()
{
    this->requestedStatePop = true;
}
 
void FSM::DoStatePop()
{
    if(this->pushedState == null)
    {
        Log.Write("ERROR! Attempting state pop null state");
        return;
    }
    
    if(this->currentState != null)
    {
        this->currentState.Exit();
    }
    
    this->requestedStatePop = false;
    this->currentState = this->pushedState;
    this->pushedState = null;
    
    assert this->currentState != null;
    this->currentState.ManagerResume();
}
 

Timed Update

Last improvement we can add is a timed update, by simply passing a “update time” to each state constructor and making the State::ManagerUpdate keep track of it:

Code Snippet
 public void ManagerUpdate()
{
    if(!this->isPaused) 
    { 
        if(this->updatePeriod == 0 || 
                CurrentTime() - this->lastUpdateTime >= 
                this->updatePeriod)
        {
            this->Update();
            this->lastUpdateTime = CurrentTime();
        }
    }
}
 

The Code

It’s not “by example” if it doesn’t have an example, so here is a complete example in Java.

Finite State Machine

Code Snippet
 /**
 * State machine behavior to provided 
 * different decision states.
 * 
 * Supports push/pop and replace 
 * mechanisms. (Stack of only 1 stored state.)
 * 
 * Supports safe-state switch via request.
 * @author Ying
 *
 */
public class FSM
{    
    /**
     * Reference to current state.
     */
    private SinState currentState = null;
    
    /**
     * Reference to next state requested.
     */
    private SinState nextState = null;
    
    /**
     * Indicates whether a new 
     * state replace has been requested.
     */
    private boolean requestedStateChange = false;
    
    /**
     * Stores a pushed state. 
     * Make this a list to store a pile of states.
     */
    private SinState pushedState = null;
    
    /**
     * Indicates whether a new state push 
     * has been requested.
     */
    private boolean requestedStatePush = false;
    
    /**
     * Indicates whether a new state pop has 
     * been requested.
     */
    private boolean requestedStatePop = false;
 
    /**
     * Initializes a new instance of the StateMachine 
     * class.
     */
    public FSM() {}
 
    /**
     * Update the FSM, and the current state if any.
     */
    @Override
    public void action() 
    {
        if(this.requestedStateChange)
        {
            this.DoStateReplacement();
        }
        else if(this.requestedStatePush)
        {
            this.DoStatePush();
        }
        else if(this.requestedStatePop)
        {
            this.DoStatePop();
        }
        else if(this.currentState != null)
        {
            this.currentState.ManagerUpdate();
        }
    }
    
    /**
     * Request to change the current state to a new one. 
     * Request will be stored till FSM update.
     * @param newState New state to change to.
     */
    public void RequestReplaceState(SinState newState)
    {
        this.nextState = newState;
        this.requestedStateChange = true;
    }
 
    /**
     * Do the actual state replace.
     */
    private void DoStateReplacement()
    {
        String prev = "Null";
        String next = "Null";
        if(this.nextState == null)
        {
            Log.Write("ERROR! Attempting state replacement to null state");
            return;
        }
        
        next = this.nextState.name;
        this.requestedStateChange = false;
        if(this.currentState != null)
        {
            this.currentState.Exit();
            prev = this.currentState.name;
        }
        
        this.currentState = this.nextState;
        this.nextState = null;
        
        assert this.currentState != null;
        this.currentState.SetWasPushed(false);
        this.currentState.Enter();
        Log.Write("STATE CHANGE: " + prev + " --> " + next);
    }
    
    /**
     * Request to push the current state to 
     * storage and run another one.
     * @param newState New state to run.
     */
    public void RequestPushState(SinState newState)
    {
        this.nextState = newState;
        this.requestedStatePush = true;
    }
    
    /**
     * Do the actual state push.
     */
    private void DoStatePush()
    {
        String prev = "Null";
        String next = "Null";
        if(this.nextState == null)
        {
            Log.Write("ERROR! Attempting state push in null state");
            return;
        }
        
        next = this.nextState.name;
        
        if(this.currentState == null)
        {
            Log.Write("ERROR! Attempting state push back null state");
            return;
        }
        
        prev = this.currentState.name;
        this.requestedStatePush = false;
        this.pushedState = this.currentState;
        
        this.pushedState.ManagerPause();
        
        this.currentState = this.nextState;
        this.nextState = null;
        
        assert this.currentState != null;
        this.currentState.SetWasPushed(true);
        this.currentState.Enter();
        Log.Write("STATE PUSH: " + prev + " --> " 
                + next + " [Pushed state: "+ 
                this.pushedState.name +"]");
    }
    
    /**
     * Request pop of current state and 
     * restoring of the pushed one.
     */
    public void RequestStatePop()
    {
        this.requestedStatePop = true;
    }
    
    /**
     * Does the actual pop.
     */
    private void DoStatePop()
    {
        String prev = "Null";
        String next = "Null";
        if(this.pushedState == null)
        {
            Log.Write("ERROR! Attempting state pop null state");
            return;
        }
        
        next = this.pushedState.name;
        
        if(this.currentState != null)
        {
            this.currentState.Exit();
            prev = this.currentState.name;
        }
        
        this.requestedStatePop = false;
        this.currentState = this.pushedState;
        this.pushedState = null;
        
        assert this.currentState != null;
        this.currentState.ManagerResume();
        Log.Write("STATE POP: " + prev + " --> " + next);
    }
}
 

State

Code Snippet
 /**
 * Base class for states.
 * Supports state pause.
 * @author Ying
 *
 */
public abstract class SinState 
{
    /**
     * Whether the state is paused.
     */
    protected boolean isPaused;
    
    /**
     * Update period of the state.
     */
    protected int updatePeriod;
    
    /**
     * Last update period.
     */
    private long lastUpdateTime;
    
    /**
     * Reference to the FSM
     */
    protected StateMachine FSM;
    
    /**
     * State name.
     */
    public String name;
    
    /**
     * Whether the state was pushed.
     */
    private boolean wasPushed;
    
    /**
     * Initializes an instance of the SinState class.
     * @param updatePeriod The time (in ms) between 
     *  each update. Set 0 for going as fast as possible.
     */
    public SinState(int updatePeriod, StateMachine FSM, String name) 
    {
        this.isPaused = false;
        this.updatePeriod = updatePeriod;
        this.lastUpdateTime = System.currentTimeMillis();
        this.FSM = FSM;
        this.name = name;
    }
    
    // Override functions
    public abstract void Enter();
    public abstract void Exit();
    protected abstract void Update();
    protected abstract void Pause();
    protected abstract void Resume();
 
    // Manager functions
    public void ManagerUpdate()
    {
        if(!this.isPaused) 
        { 
            if(this.updatePeriod == 0 || 
                    System.currentTimeMillis() - this.lastUpdateTime >= 
                    this.updatePeriod)
            {
                this.Update();
                this.lastUpdateTime = System.currentTimeMillis();
            }
        }
    }
    
    public void ManagerPause()
    {
        this.isPaused = true;
        this.Pause();
    }
    
    public void ManagerResume()
    {
        this.isPaused = false;
        this.Resume();
        this.lastUpdateTime = System.currentTimeMillis();
    }
    
    public void SetWasPushed(boolean pushed) 
    { this.wasPushed = pushed; }
    
    public boolean WasPushed() 
    { return this.wasPushed; }
}
 

Conclusion

Finite states machines are a very useful construct for controlling the flow of a game, how your game scene updates in different situations, how your character acts… It’s not a holly grail, all purpose solution, but it works surprisingly well for many scenarios.

Enjoy.

NOTE: This tutorial was done with cocos2d-1.0.1-x-0.9.1 and cocos2d-1.0.1-x-0.11.0, and so may not be 100% accurate for either version, or newer [Had to change version in the middle of development], but will serve as a general guideline for anyone using similar versions.

First Part: Quick and dirty guide to getting cocos2dx working on Android from Windows 7

Introduction

Working from the files we obtained in the first part, in this tutorial we shall cover:

Moving android-generated folder away from the cocos2d-x folder.
Add an extra library ( Chipmunk ).
Not having to use the Classes & Resources folders.

It’s important to use the proper editing tool for the files generated by the “create-android-project.bat”, because regular windows editors add extra symbols like “\r” that will confuse your Cygwin. I recommend Notepad++. A great editor that has the invaluable property of showing hidden symbols by doing: View -> Show symbol -> Show all characters.

Moving The Folder

I generated a new project FOLLOWING THE STEPS IN THE PART ONE OF THE TUTORIAL, let’s call it FVZ, using the following specs:

Package: com.companyname.fvz
Name: FVZ_2_3
Target ID: 13 (Android 2.3.3)

And copied it from the cocos2d-x folder where it’s generated by default, to the folder where my Visual Studio solution held all my code of the project I was working on. To make this work, I had to modify:

android/build_native.sh

GAME_ROOT=/cygdrive/d/All/Proyects/FVZ/Android/FVZ_2_3
( Set the path to where we have copied the project folder, and add the /cygdrive/ in front so Cygwin can use the path ).

android/jni/Android.mk

Modify project path: addprefix $(LOCAL_PATH)/../../../../FvZv2/ to point to the root folder of the cocos2dx instaltion (where you have all the cocos2dx code, ej: cocos2dx, CocosDenshion, tests, tools…

What this does is search for all the Android.mk (makefiles) of the libraries you are going to use. (Notice the addprefix & addsufix functions, to generate the full paths).

# Try to use LOCALPATH, otherwise you’ll have to play a bit with the path till you get it to Cygwin’s liking.

android/jni/helloworld

LOCAL_SRC_FILES: Add RELATIVE path to each code file (cpp / h) in your Visual Studio project folder. The start of my list is, for example:

LOCAL_SRC_FILES := main.cpp \
../../../../../FvZv2/FvZ/Classes/AppDelegate.cpp \
../../../../../FvZv2/FvZ/Classes/AppDelegate.h \
../../../../../FvZv2/FvZ/Classes/HelloWorldScene.cpp …

LOCAL_C_INCLLUDES: Change Classes path to the folder where you keep all your code, and set the paths for the different cocos folders so they point to the required folders.
LOCAL_LDLIBS: Point the $(LOCAL_PATH)/../../libs/$(TARGET_ARCH_ABI)) to the proper location (TARGET_ARCH_ABI is usually armeabi).

andoid/build_native.sh

Change GAME_ROOT so it points to the root of your game folder, in my case:
GAME_ROOT=/cygdrive/d/All/Proyects/FVZ/Android/FVZ_2_1

With all that your project should compile with no problems using Cygwin. As a special note, I made a java script to parse my Classes folder, to generate my LOCAL_SRC_FILES paths, as there where hundreds of files, in nested folders and so on. Sharing it here:

Code Snippet
 import java.io.File;
 
 
public class ListFiles 
{
    static String initialPath = "D:\\All\\Proyects\\FvZ\\FvZv2\\FvZ\\Classes";
 
    public static void main(String[] args) 
    {
        FileTreePrint("");
    }
    
    private static void FileTreePrint(String path)
    {
        String files;
        File folder = new File(initialPath + path);
        File[] listOfFiles = folder.listFiles(); 
 
        for (int i = 0; i < listOfFiles.length; i++) 
        {
            if (listOfFiles[i].isFile()) 
            {
                files = listOfFiles[i].getName();
                System.out.println("../../../../../FvZv2/FvZ/Classes"+ path.replace("\\", "/") + "/" +files+ " \\");
            }
        }
        
        for (int i = 0; i < listOfFiles.length; i++) 
        {
            if (listOfFiles[i].isDirectory()) 
            {
                FileTreePrint(path + "\\" +listOfFiles[i].getName());
            }
        }
    }
}
 

Adding Chipmunk to the Compilation

We need to modify some files, but it’s a straightforward process if we take another library (CocosDenshion) as a guideline.

android/jni/Android.mk

Add “chipmunk \” in the line under CocosDenshion/android.

android/jni/Application.mk

My APP_MODULES looks like:
APP_MODULES := cocos2d cocosdenshion chipmunk game

android/jni/helloworld

LOCAL_C_INCLLUDES: Add the path to the chipmunk folder that holds all the files, in my case:
$(LOCAL_PATH)/../../../../../FvZv2/chipmunk/include/chipmunk \
In LOCAL_LDLIBS add –lchipmunk

Lastly, there is one extra modification to be done, that took me quite a while. In the main java file of the .java files generated for your project (in my case FVZ_2_3.java) we need to search for where it does System.loadLibrary(), and add:

System.loadLibrary("chipmunk");

Automating the Process

The first thing you will notice with this system is that it’s SLOW. We have have to use the command line every time we want to compile, not to mention that this method copies all the resources of the game from the Resources folder to the assets one each time, which can be very time consuming.

So let’s optimize it a bit.

Making the resource load faster

Grab your build_native.sh and clean out all the logic for cleaning the resource folder, leaving it like this:

Code Snippet
 # set params
ANDROID_NDK_ROOT=/cygdrive/c/eclipse/android/android-ndk-r6b
GAME_ROOT=/cygdrive/d/All/Proyects/FVZ/Android/FVZ_2_1
GAME_ANDROID_ROOT=$GAME_ROOT/android
 
# build
$ANDROID_NDK_ROOT/ndk-build -C $GAME_ANDROID_ROOT $*
 

What is going to happen now is that you’re going to have to remember to manually copy each modified asset from your MVS project to the assets folder of the java project. A small price to pay for compiling in 10 seconds instead of 1 minute.

So go ahead and copy all your resources to the assets folder. Once you’re done…

One Click Process

I created a batch file to be called with a simple double click, that calls cygwin and gets the whole compilation process done. After double clicking on it you just need to refresh the java project in eclipse (F5) and hit “run” to have the game showing in your android. Here is the magical .bat:

Code Snippet
 C:\cygwin\bin\bash.exe -l '/cygdrive/d/All/Proyects/FvZ/Android/FVZ_2_1/android/build_native.sh' 
pause
 

Created this Compile.bat thanks to http://forums.techguy.org/windows-xp/424616-calling-unix-scripts-dos-script.html and http://old.nabble.com/Cygwin---batch-file-td15088393.html .

Conclusion

Now you should be able to put your folder wherever you damn well please, add other libraries to it and compile by:

Compiling in MVS by hitting F5 (to check it works)
Compiling in native code by double clicking Compile.bat
Running the game in android by hitting F5 in eclipse, and then “run”.

Tell me if it worked for you!

Magic Scrolls of Code

Monday, February 13, 2012

State Machines By Example: A Useful FSM

Introduction

FSM

State

Making it Useful

Changing State at the Proper Time

Push & Pop

Timed Update

The Code

Finite State Machine

State

Conclusion

Saturday, February 4, 2012

More advanced concepts of getting cocos2dx working on Android from Windows 7

Introduction

Moving The Folder

Adding Chipmunk to the Compilation

Automating the Process

Making the resource load faster

One Click Process

Conclusion