This document is superseded by this document.

Although Finite State Machines are not typical A.I., they form an important tool in the A.I. programmer's toolbox. A Finite State Machine is a program that acts differently depending on its "state". There are a finite number of states the program can be in. But just as important as the states of the program are the transitions between those states. It is possible to specify what code should be executed whenever the program changes from one state to the other.

Simple finite state machines are flat and can be only in a single state at any time. These can usually be implemented by a single switch statement. In some applications, however, you want your program to be in several states simultanuously. This is called concurrency. Next, you may want to structure your state machine in a tree-like fashion, to avoid having to repeat common code in several states. It can greatly simplify the design of the program. This makes a finite state machine hierarchical.

What was implemented:
  • States: Each state can have an update function, an entry function, and an exit function.
  • Hierarchical structure: Each state may contain substates. You might say each state may contain its own state machine.
  • (Simple) Transitions: Each transition can create a bridge between any two states of the state machine. Whenever the transition is fired, the source state is deactivated, the transition code is executed, and the target state is activated. Deactivation entails the execution of the exit code of the source state and its direct superstates. Activation entails the execution of the target state's entry code and that of it direct superstates.
  • Complex transitions: A complex transition has a number of source states and a number of target states. When all source states are active, the transition fires. This means that the source states are deactivated and the target states are activated. Complex transitions can be used to create concurrency.
  • Initial states. I chose not to create special initial states that have no other function than to activate another state. In stead, an existing substate can be made the initial substate. When the superstate is activated, its initial substate is automatically activated as well.
  • History. There are no special history states. A state may have shallow history, which means that when it is activated, the substate that was active when the state was last active will be automatically activated again. It may also have deep history, which means that when it is activated, the previous activation pattern of all substates and subsubstates will be restored.
What was not implemented:

  • Final states. I see no use for them currently. The FSM's I picture are always active. They don't end.
  • Internal transitions.
  • Handling of conflicting transitions. If multiple transitions could all fire, the first one added to the model will fire. Not the most low-level. Nor is it possible to specify priorities.

  • My starting point is the UML 1.1 specification for statechart diagrams. However I diverted somewhat. I did not create special initial and history states. And, more importantly, I did not model concurrent substates explicitly. I used complex transitions to implement concurrency. It was easier to implement and it seems more intuitive to me. I made simple transitions a special case of complex transitions.
  • I chose not to implement state machines in a recursive manner. That is, a state machine within a state machine. Even though it seems the most straightforward implementation, it becomes a problem when you start defining transitions between states of different state machines. For a number of reasons it is much easier to just have a single state machine with a number of states and transitions, and to allow states to have substates.
  • Concurrency can be implemented in two ways. The first way is by explicitly defining concurrent substates that have explicit initial and final states. The other is by complex transitions that fork and join the control flow. I chose the latter because it is a specific use of complex transitions, which I needed anyway.
  • The easiest way to create complex state machines is to require a special class for every state the programmer needs. In C++ this is an enormous code overhead. Add to this the well-known implementation of a state machine as a switch statement. This is how I reached my design where the programmer needs to create only one class for his state machine, but needs to create a switch statement in each of the interface functions.
  • On updating states, the active top-level states are updated in the order in which they were added to the model. When a top-level state is updated, its active substates, and subsubstates are updated as well, in that order (top-down).
  • A state machine should always have a single state as its top-level composite state. This state is present when the FSM is created and is called Root. So even the application programmer adds no (sub)states, the FSM still has a state. All states have Root as their super(super((...))state.
  • If a state has a deep history, it overrides any other history settings of substates. If a substate only has a shallow history, this will be overridden.
  • I chose to combine simple and complex transitions. Simple transitions are activated when the source state is active and the guard condition holds. Complex transitions may contain multiple source and target states and are (by specification) automatically fired when the source states are active. In my implementation, a "transition" can have any number of source and target states. If all source states are active and the guard condition holds (the transition "should fire"), it fires. At that time the source states are deactivated and the target states are activated.
  • It could be a good idea to let the programmer create separate functions for all entry, exit, guard and transition code. The programmer needs to give the address of the function to the model. The functions are methods in a CFSMModel subclass. This saves having to check all 'switch' statements all the time, which could take time if there are a lot of states and transitions.
Sample use

class CMicrowave: public CFSMModel
    bool LightSwitchedOn;

    CFSMState *Activate;
    CFSMState *Mode;
    CFSMState *ModeDisabled;

    CFSMTransition *ModeDisabled_ModeOperational;
    CFSMTransition *ModeOperational_ModeDisabled;
    CFSMTransition *ModeOperationalSetTime_ModeOperationalIdle;

    CFSMTransition *Activate_ModeDisplayLight;

        // create states
        Activate = AddState("Activate");
        Mode = AddState("Mode");

        // create substates
        ModeDisabled = AddState("ModeDisabled", Mode);

        // create transitions
        ModeDisabled_ModeOperational = AddTransition
            (ModeDisabled, ModeOperational, "close");
        ModeOperational_ModeDisabled = AddTransition
            (ModeOperational, ModeDisabled, "open");

        // create complex transitions
        Activate_ModeDisplayLight = AddTransition();

        // initialization
        LightSwitchedOn = false;
        // top level
        // lower levels

        // history states
    virtual void UpdateState(CFSMState *State)
        printf("State \"%s\" Updates.\n", State->GetName().GetBuffer());
    virtual void EnterState(CFSMState *State)
        printf("State \"%s\" Entered.\n", State->GetName().GetBuffer());
    virtual void ExitState(CFSMState *State)
        printf("State \"%s\" Exited.\n", State->GetName().GetBuffer());
    virtual bool ShouldFire(CFSMTransition *Transition)
        return true;
    virtual void Fire(CFSMTransition *Transition)
        if (Transition == LightOff_LightOn) LightSwitchedOn = true;
        else if (Transition == LightOn_LightOff) LightSwitchedOn = false;

        printf("Transition \"%s\" Fires.\n",

void FSM(void)
    CMicrowave Microwave;

    // first start the microwave at its initial state

    // update many times (may be placed in an infinite loop)

    // maybe stop and deactivate all states

    // print the current state of the FSM
    printf("%s", Microwave.ToString().GetBuffer());