I want to tackle one important category of options missing from his list ( and from other people's ), what I'll call here a "State Descriptor". It's a pretty simple idea, but a powerful way of describing states.
To get at what a "State Descriptor" means, let's first separate the idea of *identifying* a state from the actual *processing* code which handles the incoming events for that state.
This separation is implicit when we talk about states, but this separation vanishes during implementation. Let's take a look...
Samek lists four different implementations, they are: nested switch statements, state tables, the Gang of Four's state pattern, and his QEP implementation; he also briefly touches on using pointers to functions for transitions.
I don't want to cover what's done better in his book than I could here, so instead, I'll just break them apart and refactor along the lines of identification vs. processing, and go from there. Even if you haven't read his book, you'll quickly understand what I'm talking about.
For "state identification", the methods he describes boil down into "enums", "classes", and "functions". For "event processing", the methods he describes boil down into "procedural code" and "tables".
( If there's some piece of you that's shouting "what about identifying a state by string?", "why can't i process events with data?", then you're already seeing why looking at a statechart in terms of its component parts is valuable. )
(Some) Methods to Identify States
Enum:
Going back, once again, to the main menu example, it's easy to imagine how we might identify the states described there via an enum:enum AllGuiStates {
InvalidState,
MainMenu,
NewGame,
ContinueGame,
LoadSaves,
SelectGame,
ConfirmChoice,
AllGuiStates_Count
};
The current state of the statemachine is likewise very simple; all it takes is:
AllGuiStates currentState;
Samek pairs this method of identification with table based event processing, citing examples which create two dimensional arrays: all states in one dimension, and all events in the other dimension. At it's most horrific maybe something like:
// in this table every state is in its own row
// buttons events appear button_0, button_1, ... etc,
// left to right within that row
AllGuiStates TransitionTable[AllGuiStates_Count][AllEvents_Count] =
{
/* Main Menu State */
NewGame, ContinueGame, Options, ....
/* New Game State */
// ...etc.
};
Obviously, macros and other tricks can make this look nicer, but the the important part for this discussion is that while the example shows an enum indexing a table -- that's mixing identification with processing. These are really two separate concepts. We can index that table via a variety of means -- string look-up if we wanted -- or, we could use enums to identify states but we could use nested switch statements to process the events.
Classes:
The most common example of using classes for handling states is the state pattern ( it's kind of amazing that the Design Patterns book is so popular, its essentially block copied to wikipedia ). Under the state pattern, we'd have an abstract "GuiState" class from which we derive each state as a separate concrete class.abstract class GuiState { // ... }; class MainMenu : GuiState { // ... };class NewGame : GuiState { // ... };class ContinueGame : GuiState { // ... };
The current state would be represented as, just:
GuiState * currentState;
When we talk about the *processing*, under the state pattern, there are choices along a spectrum. Going from most verbose to least, we can have:
- Methods for each and every possible event;
- Methods per event category;
- One generic "handle event" method.
If this were a touch enabled menuing system, maybe the most verbose case would look something like:
abstract class GuiState {
void touchesBegan( withEvent* );
void touchesMoved( withEvent* );
void touchesEnded( withEvent* );
void touchesCancelled( withEvent* );
};If you're familiar with iOS development, you probably notice that I just described the iOS UIResponder interface... ( they're tricky that way... design patterns crop up everywhere! ).
And, if you're familiar with how many languages implement virtual functions then you won't be surprised when I say -- the GuiState i just described is (often) just a compiler generated table under the hood. So, even though we don't see the mechanics as we did with the array, we do in fact have similar processing. ( I'm cheating a bit here, Objective-C has smalltalk roots, not Simula like C++, but essentially it's all table-like under the hood. )
At the other end of the spectrum, the single generic method might look like:
abstract class GuiState {
void handleEvent( withEvent* );
};
In this case, inside handle event, the code would *procedurally* unpack the event to determine whether it was touchesBegan, touchesEnded, or what have you, and then take the appropriate action. We identify states with a class, but we process the state in a procedural manner.
The state pattern, in this light, provides a particular pairing of *identification* with *processing* depending on how fine grained you want your interface to be. The representation as a class does not imply a particular method of processing until you fully flush things out.
Functions:
The technique used by Samek's QEP has almost the same sort of processing as the single method version of the state pattern. His technique simply uses a single "free" function to represent a state; one function per state. For example:void MainMenu(withEvent*);
void NewGame(withEvent*);
void ContinueGame(withEvent*);
And he identifies the currentState with function pointer:
typedef void(*state_function_t)( context*, event*);
state_function_t currentState;
He's identifying the state with a function, but the processing he uses internally is procedural. At some level, this is just a C translation of the single method state pattern.
General Lessons
What's probably obvious at this point is that, in each case, we have to use the "state identifier" to get to the "event processing" code.At its core: all we need for any state machine is some handle to identify our current state, and then some way to get at the event processing for that state. The code that does the processing could use a table, it could use procedural code to sniff out the event table, it could be purely data driven if we want. The hook and the processing techniques are separate -- even if they are never presented that way.
For the sake of argument, let's say for the moment that event processing and transitions are "application defined" -- there's a lot of details to implementing a full statechart system, I'm just wanting look at unwinding the states and processing. As long as we allow some way to find the processing code, we can identify states however we want.
State Descriptors
So what *if* we separated identification can processing? What *if* our identifier didn't just provide us a pointer to the some transition processing, but what if it provided something more?We could easily imagine how nice it would be to have a string name to help us during debugging. Maybe we could have store a mini-transition table containing just the the events a single state handles. Maybe we could provide the state's parent for quick event bubbling. Or even the depth of the state in the chart for quick lowest common ancestor determination during transitions.
Once we fully break apart *identification* from *processing* -- making "processing" just one part of a description of a state, we can do lots of powerful things.
Here's the (approximate) description I use:
// not pointing to the transitions, but to a full description. state_info_t * currentState; // processing function definition, // similar to before but returning a description // (ie. our next state ) typedef state_info_t (*state_function_t)( context*, event* ); // here's the description struct state_info {state_function_t process; // an example processing functionint depth; // depth allows fast lca struct state_info* parent; // parent allows quick event bubbling const char * name; // a name for debugging }; typedef struct state_info state_info_t;
In C or C++, descriptors could easily be generated easily though macros, a rough example:
#define HSM_STATE( parent, me ) \ state_info me##State= { \me, \parent##State.depth+1, \ &parent##State, \ #me, \ };
In other languages, you could use containment of inner-classes, introspection, or other techniques to generate the needed fields.
An example implementation of the Main Menu code using a procedural processing function, might look like:
// pre-decl of the state processing function, ex. in a .h
state_info_t* MainMenu( context *, event *evt );
// declaration of the state descriptor
HSM_STATE( Game, MainMenu );
// a procedural state processing function
state_info_t* MainMenu( context *, event *evt )
{
state_info_t* next_state= 0;
switch (evt->type){
case ENTRY:
display_menu();
break;
case BUTTON_EVENT:
switch (((button_event*)event)->which_button) {
case 0:
next_state= &NewGameState;
break;
// other buttons ...
};
break;
// other events...
};
return next_state;
}
But, if you don't like switch statements, you could use null terminated arrays, builders, introspection, etc. to generate "sparse transition tables". A partial implementation might be something like:
TableData MainMenuTable[] = { { ENTRY, display_menu }, { BUTTON_EVENT_0, handle_button }, //... { 0 } };#define HSM_TABLE( parent, me ) \ state_info_table me##State= { \&me##Table, \parent##State.depth+1, \ &parent##State, \ #me, \ }; HSM_TABLE( Game, MainMenu );state_info_t* HandleEvent( event* evt, state_info_t * currentState ) {state_info_t* next_state=currentState;for (TableData* row= currentState->table; row->event_type; ++data) { if (row->event_type== evt->type) { next_state= row->action(...); break; } } }
There are lots of possibilities once you break through what in retrospect seems like an obvious boundary, but that few ( any? ) implementations actually leverage.
0 comments:
Post a Comment