Event Driven FSMs
Posted in Code on October 11th, 2009 by PyrokaIn AI this week we had to implement our own Finite State Machine, in the seminar before hand we talked about it and decided that the best approch, is a buffered event driven FSM, where FSMs listen for events that are generated, this gives us the advantages of event driven FSMs (Any class can interact, by the event, with any other class without even knowing if that other class exists etc) without the draw-backs (code being executed at a non-determinate time and order)
I decided to have a crack at implementing one myself, I’m not saying this is the best method for doing so, but it is a method.
What do we need? Well, we need an Event class, I’ll also use an EventType class to distinguish between instances of Events and types of Events, since FSMs will listen for events of a certain type, I’ll use an EventFactory to create the Events and EventTypes and an EventOccurance class to hold event occurrences. That’s good enough to be getting on with, so if you’re sitting comfortably, I’ll begin.
Firstly, registering a FSM (or sub-class) to listen for an EventType, for this, we’ll need to store a pointer to the FSM and a pointer to a member function on the said FSM, the first is easy, the second, not so.
Pointers to member functions can be problematic, we either can make the function static (which is a restraint I didn’t want to push on myself) or we need to know the type of class the function is a member on, the problem being we can’t cast, so a pointer to a function of the FSM class, has a different syntax to one on a DoorFSM class.
So how to store a list of these? Well for that we turn to Functors (anyone who knows functors or is afraid of templates, look away now)
I created a TemplateFunctor class, which has a ctor that takes a pointer to a class, and a function pointer to a function that’s a member of said class, the code looks like this:
template<class T, class U>
class TemplateFunctor
: public Functor
{
public:
TemplateFunctor(T* pObject, void(T::*pFunction)(U*))
{
m_pObject = pObject;
m_pFunction = pFunction;
}
virtual void operator()(void* pArg)
{
(*m_pObject.*m_pFunction)((U*)pArg);
}
private:
T* m_pObject;
void (T::*m_pFunction)(U*);
};
As you can see, this templated class has two arguments, T is the type of class the member function belongs to, U is the type of the object passed as a parameter to the callback function, the overloaded function call operator just calls the function. The eagle-eyed of you will spot that it inherits from a bass class called Functor, this is so we can store a list of them, since every instance of this class could potentially have a different T value and thus, in reality be a different class type, we need a common parent so we can store pointers to them.
Ok, now we can store the information we need to register listeners, where will we keep this list? Well for me that’s on the EventType class, which is basically a black-magic way of doing RTTI (Runtime type identification), for this, we’ll need an EventFactory class, which you can see here:
class Empty{};
template<typename T, class P = Empty>
class EventFactory :
public P {
public:
virtual EventType* Type()
{
return TYPE;
}
EventFactory() : P()
{
}
~EventFactory()
{
}
static EventType* TYPE;
};
template </typename><typename T, class P> EventType* EventFactory<t , P>::TYPE = new EventType();
Ok, this template class also takes two parameters, T is the type of Event, P is that event types parent, which for most new classes will be Event, but defaults to the aptly named Empty.
The black magic here is the TYPE variable, which is public for good reason, it allows you to do DoorOpenEvent::TYPE to return a pointer to that classes type, the Type() method is virtual to allow an instance of a subclass of Event (DoorOpenEvent) to get a pointer to the right EventType (if you have an instance of DoorOpenEvent called pEvent, calling pEvent::TYPE would return the EventType for Event)
So why are we even creating an Event class to subclass from? I use it for the Dispatch method, which calls the Dispatch method on the EventType (By calling Type()->Dispatch()) but saves on some typing, you may also want to add other methods and state for all events to contain.
The function to register a listener is a templated function, and just creates a new TemplateFunctor with a pointer to a class and member function.
The Dispatch() method, this is pretty simple, all FSMs have an AddEventOccurance() method that takes an EventOccurance object, this is just a storage class that holds a pointer to the EventType of the event that occurred (so you can have a callback method that handles more than one type of event, and check which type of event it was by comparing that pointer to pointers returned by the TYPE variable of an Event subclass) a priority variable (just an int) and a void pointer for any other data (It’s assumed that the callback function will know what to cast that to to be useful). So all we need to do is iterate over all registered listeners, and add a new EventOccurence to them.
EventOccurances overload the less-than operator, this is used by the priority queue to sort it so that the highest priority event will be at the top.