Implementing a finite state machine

[ResidentBiscuit]

How would you go about implementing a state machine? I've been tossing some ideas around in my head, but can't settle on a decent one. The most promising one I've been thinking of is just having a vector of states. But then I'm not sure how I would actually keep them separate.

I have a state diagram drawn up, but just can't think of how to actually implement this.

[kbw]

You could define the states in an enum, define a set of valid state transitions in a multimap. The state class would maintain your current state and transitions to the next state, using the multimap to maintain valid transitions.

[ResidentBiscuit]

Sticking the states in an enum was another idea I had. Could you explain how a multimap could be used here? I imagine you mean it would function as a lookup table?

[kbw]

The idea is there is a set of valid state transitions. For example, you may allow state transitions: a->b, b->c, b->d, ... These would be held in a multimap and would be used to enforce correct state transitions.

[AbstractionAnon]

There are a number of different possible state table designs.
Most common are four "columns" in a state table.
-State
-Event
-Action
-Next State
State and Event form a unique key. Action can be an index to a switch statement, or even a function pointer. State and Next State are the same enumerated type. When an event (again an enumerated type) occurs, the current state value and event number row is found in the table. That row indicates the action to be performed and the Next State value is set into the current state variable.

Here's a finite state machine implemented as a template. It does a linear search of the state table, so it's not the most efficient, but it is something that can be implemented easily by simply defining the appropriate enums and providing the overloaded DoAction method.

//  A <STATETABLE> is an array of STATEROWS. 
//
//  Where <TS> , <TE>, <TA> are enumerations for the states, events, and action
//  specific to the state machine.
//
//  DoAction is pure virtual and should be implemented in a derived class. 
//
template <typename TS, typename TE, typename TA>   
class STATETABLE  
{   
public:
  typedef struct __staterow
    { TS  state;
      TE  event;
      TA  action;
      TS  next_state;
     } STATEROW;

private:
    const STATEROW *  m_rows;         //  Pointer to array of rows terminated by -1
       
protected:
    //  Terminate due to overloaded action not found
    void ST_Error (TA action)
    {	Abort ("ST=%s Action=%d not handled", m_name, (short) action);
    }
	
    //  Terminate due to missing state table row 
    void ST_Error (TS state, TE event)
    {	Abort ("ST=%s Row not found S=%d E=%d", m_name, state, event);
    }
	             
    //	Return pointer to matching current state and event
    const SR * FindRow (TS state, TE event)
    {   const STATEROW *	row;
               
        row = m_rows;
        while (row->state != -1)
        {   if (row->state == state && row->event == event)
                return row; 
             row++;
       }
        ST_Error (state, event);
        return NULL;		// Not reached
    }    

    //  Returns another event, or 0 if state machine should exit	
    virtual TE DoAction (TA act) = 0;          // pure virtual
	
	
    //	State Machine 
    //	Called with event
    //	Loops until an action returns an EXIT (0) event
    void state_machine (TS & state, TE event)
    {	const STATEROW *  row;

    	while (event) 
	{   row = FindRow (state, event);
                     state = row->next_state;
	     event = DoAction (row->action);
	}
    }
		    
public:
    STATETABLE (const STATEROW * rows)
    {   m_rows = rows;   
    }
	
    virtual ~STATETABLE (void)
    {}
}; 

[Cubbi]

How would you go about implementing a state machine?

I just use a library -- http://www.boost.org/doc/libs/release/libs/statechart/doc/index.html

There is also http://www.boost.org/doc/libs/release/libs/msm/doc/HTML/index.html but I haven't had a chance to work with it yet.

[ResidentBiscuit]

Well, looks as if grabbing a library is the fastest way to get this going.

[cpp for all]

Have you tried my library?
It does exactly what you're looking for. It is very easy to implement your own state machine + very easy to maintain.
Have a look at:
http://www.codeproject.com/Articles/406116/Generic-Finite-State-Machine-FSM

and tell me what you think :)

Good luck