A Generic FSM with Visual Editor

• Download source code - 60.9 KB
• Download editor - 70.4 KB

Introduction

bitfsm is a generic FSM (Finite State Machine) implementation. It is coded as a C++ template class and some helper structures. bitfsm is wrapped in C++/CLI so it is friendly to native C++ coders and .NET ones. There is also a generic visual editor for this library with which developers can edit FSM rules by just dragging and dropping some status blocks and command lines. In this article, I will explain the basic designing concepts, the invoked methods, and an introduction to the editor.

Background

Once upon a time, when I was a young boy, the computer was so funny and mystical to me! It’s interesting it’s still funny to me now, but less mysterious. Abstraction is the tool to solve programming problems, and thus a correctly abstracted model makes solving complicated problems easy.

FSM is a classical abstraction of computing model. Many, while not all, problems such as the parser of a compiler or the AI simulation of a game can be equal to this model.

An FSM contains a finite set of states and transition rules. An FSM can be in one state at a certain time and it may transfer to another state or keep it up depending on the rules once it receives a transition command.

Basic designing concepts

The library core is implemented as a C++ template class which allows you to customize it as you wish. A bitfsm could contain a variable number (an integer greater than zero) of transition commands indicated by a template parameter _Nc. bitfsm uses a RuleStep array with size _Ns to denote states, a Status structure to store the current state, and also a command buffer which holds all the transition commands it received. Each RuleStep element in the array uses a Step structure vector to denote the transition rules. Each Step structure contains a Bitset<_Nc> to denote a set of transition commands and an index indicates which is the next state if that set of transition commands is received. Transition commands are stackable in a Bitset<_Nc>; a boolean variable in a Step structure indicates whether transition commands use a logical AND compositing relation or a logical OR.

Using bitfsm

There are no extra binary files to deal with when you use bitfsm, just include the header file and invoke it.

bitfsm uses integers for most internal requirements. But coders always need a more effective data structure for specific purposes. bitfsm allows coders to use any data structure as state and transition command tags. I use std::string in this article. The bitfsm template class accepts two functors to do user defined tag to integer conversion. We should define something to get bitfsm ready to use, like below:

// Conversion functor from std::string to int; for states
struct ObjToStatus {
    int operator ()(const std::string &_obj) {
        if(_obj == "begin") {
            return 0;
        } else if(_obj == "1") {
            return 1;
        } else if(_obj == "2") {
            return 2;
        } else if(_obj == "3") {
            return 3;
        } else if(_obj == "end") {
            return 4;
        }
            return -1;
        }
};
// Conversion functor from std::string to int; for commands
struct ObjToCommand {
    int operator ()(const std::string &_obj) {
        if(_obj == "_cmd0") {
            return 0;
        } else if(_obj == "_cmd1") {
            return 1;
        } else if(_obj == "_cmd2") {
            return 2;
        } else if(_obj == "_cmd3") {
            return 3;
        } else if(_obj == "_cmd4") {
            return 4;
        } else if(_obj == "_cmd5") {
            return 5;
        }
        return -1;
    }
};
// Define a type of bitfsm which accepts std::string
// as customized tag type; and contains 5 states, 6 commands
typedef fsm::FSM<5, 6, std::string, ObjToStatus, ObjToCommand> Fsm;
// Declare an instance
Fsm sbs;

The state transition can take place automatically according to the defined rules when bitfsm receives commands; those commands may be considered as driving input for a bitfsm. We also need to get some feedbacks from bitfsm; bitfsm uses a common listener pattern to complete this work. You can define a state transitioned event callback handler like below:

class MyStepHandler : public Fsm::StepHandler {
public:
    virtual void handleStep(const std::string &_srcTag, const std::string &_tgtTag) {
        printf("Status changed from %s to %s\n", _srcTag.c_str(), _tgtTag.c_str());
    }
};

We must tell it how many states and commands there are in a bitfsm, otherwise it is an empty FSM without logic. We can register states like below:

// Register five states
sbs.registerRuleStepTag("begin");
sbs.registerRuleStepTag("1");
sbs.registerRuleStepTag("2");
sbs.registerRuleStepTag("3");
sbs.registerRuleStepTag("end");

And add some transition rules like below:

Fsm::CommandParams params;
/////
params.reset();
params.add("_cmd0");
sbs.addRuleStep("begin", params, "1");
// "_cmd0" makes bitfsm transiting from "begin" state to "1"

/////
params.reset();
params.add("_cmd1");
sbs.addRuleStep("begin", params, "2");
/////
params.reset();
params.add("_cmd3");
sbs.addRuleStep("1", params, "3");
/////
params.reset();
params.add("_cmd4");
sbs.addRuleStep("2", params, "3");
/////
params.reset();
params.add("_cmd5");
sbs.addRuleStep("3", params, "end");

Now everything is ready. The rest is just setting the beginning state and the terminal state, then passing a command parameter to the walk method to run bitfsm, like below:

bool done = false;
/////
sbs.setCurrentStep("begin"); // Set the beginning state
sbs.setTerminalStep("end"); // Set the terminal state
/////
// Walk…
sbs.walk("_cmd0");
done = sbs.terminated();
// Detect whether the FSM reached the terminal state

/////
sbs.walk("_cmd3");
done = sbs.terminated();
/////
sbs.walk("_cmd5");
done = sbs.terminated();

And also, we can save a set of rules of a bitfsm into a file for information reloading.

sbs.writeRuleSteps("backup.fsm"); // Save logic
sbs.readRuleSteps("backup.fsm"); // Load logic 

A visual editor is helpful for complicated rule editing. bitfsm supplies a .NET wrapper using C++/CLI and a visual bitfsm editor using C#. The editor looks like below:

It is easy to edit states and transition rules by dragging out state blocks and transition lines. This editor also allows us to simulate the FSM running by clicking the command menus. We can build the FSM and ensure the rules are correct very conveniently in this editor.

Conclusion

My developing principle is getting the right abstraction to solve specific problems, and make the abstraction implementation reusable as far as possible. Hope this helps in your work! Any questions, suggestions, and ideas are appreciated. You can get the latest information about bitfsm at http://code.google.com/p/bitfsm/, and get in touch with the author via mailto:hellotony521@gmail.com.