It’s nice to have some time, now and then, to tackle ideas purely because they are interesting. I’ve had state machines on my mind for a decent bit of time, and have been working on an open-source statechart engine I call hsm-statechart. I’m also looking for new paid work, and it just so happens one of the groups I’d most like to work with uses Lua for scripting, so I figure now’s as good a time as any to (re)learn it.

As a practical task, getting lua and hsm-statechart working together seems worthwhile. Lua excels at gluing different bits of an application together and, coincidentally enough, that’s also what statecharts are meant for. The combo seems like it would be a powerful one.

There are any number of simple lua finite state machines, and even SMC can target lua. But, only Miros and rFSM seem to provide hierarchical statecharts. They are both pure lua. The former ( Miros ) is a port of Samek’s engine, while the latter ( rFSM ) looks to be its own unique implementation. I haven’t evaluated either in depth, but both seem useful. It’s Edward Pereira, though, who seems to have what’s closest to my mind: a relatively easy to read textual statechart in Lua.

What follows is the approach I’m taking, it’s a sketch of a design and an explanation. It’s the sort of thing I normally do scribbling in my notebook ( and, in fact it started the day that way ), but if it’s interesting or useful to even just one other person out there in game dev land, so much the better – so here goes. The advantages of this implementation are hopefully going to be readability, and interoperability with C. It might be interesting to compare speed, but I don’t think that’s a killer feature unless Lua LCA finding is really slow, and transitions are triggering fast and furious.

Lua and C states Link to heading

Since hsm-statechart is written in C, to start, we need to look at how states descriptions might cross the C-Lua boundary, and later: we’ll need to look at where the statemachines that run those state descriptions might live. Regarding the first part, there are three basic cases to consider:

  1. a statechart is described fully in Lua,
  2. a C state contains a Lua state,
  3. a Lua state contains a C state.

To handle just the first case, it would be easiest to just port hsm-statechart completely to Lua, or even just use rFSM – but to handle the other two cases, we need something more.

To start with what exactly does “containment” mean? For hsm-statechart, it’s the not quite detectable condition of having one state descriptor reference another descriptor as its parent; that parent contains the child; the other direction – parent to child(ren) – is not tracked. That might be more detail than strictly necessary. The key is simply: Lua states need to use the same internal structures the C states do, and the hsm-statechart engine needs to be agnostic – completely unaware, in fact – of where the state came from.

Statechart Representation Link to heading

What this indicates is that it actually doesn’t matter much to the C code what the Lua representation looks like, so long as it can be translated from Lua into a normal state description. The hsm-statechart implementation already provides a way for run-time code to construct statecharts: its called hsmBuilder, so it’s really just a question of how to leverage it

HsmBuilder is inspired by OpenGL, and so looking at luaGL provides us one possible route: replicate the interface directly into lua. That makes perfect sense, and seems to be the sort of approach that rFSM takes. But, while the hsmBuilder interface is decent, it still doesn’t look as much like a textual statechart as one might hope. Lua’s flexibility, its tables, and implicit types are promising tools – so let’s instead imagine some sort of compact table-based description of states. We would then just need some small bit of C code to read the state table, and use hsmBuilder to create the real states.

After some pondering here’s what i came up with. ( Noting that I came up with this before I looked at the other lua implementations, so now I’ll need to go back and compare and contrast a bit )

 chart = {
     -- manual specification of initial state
     initial = “state1”,
     -- declaration of a new state
     state1 = {
        -- events are key:state_name pairs
        event1= “state2”,
     },
     -- states are always key:table pairs
     state2 = {
       -- optional enter and exit functions
       -- entry= function() end,
       -- exit= function() end,
       initial= “state21”,
       state21= {
          -- events can also be key:function pairs
          event2= function()
             if guardPassed() then
               -- transition with a guard
               return “state2”  
             elseif someOtherTest() then
               -- handled but no transition
               return true 
             end
             -- nil means not handled
          end
       } 
     }
  }

Some things to notice:

  • States are tables. Since, we can nest tables in tables, we can nest states in states.

  • In lua, the order of elements in a table is undefined. If we iterate over the pairs of `chart` state2 might be returned before state1, that means we need to explicitly say which state is the first state ( ie. `initial=”state1”`)

  • In lua table declarations: the left side of an equal side looks like a variable but it’s actually a string. { inital = “state1” } is really just shorthand for { [“initial”]= “state1” }. This makes all the states and events in the above chart string based keys. ( And means we can have spaces and dots in our event names – the latter re: action script – if we want them. ) The exception to this is the `chart` itself which is a variable containing a table, not a key, nor a string, in a table. More on that in a bit.

  • Anytime we see { name = {} } we know the name refers to a new state. We know this because that’s how we’ve defined it :)

  • All other key:value pairs indicate an event of some sort. For events, there are two different possibilities.

  • We can specify a state name to transition to when the event triggers. ( ex. event1= “state2” ); or, we can specify an event handler function:

  • For functions, we have a couple of possible return types:

  • we can return a state name to transition to ( just like the simple case did );

  • we can return “true” to indicate the event was handled, no transition is needed;

  • or, we can just end the function – which is the same as returning nil. `nil` indicates the event remains unhandled.

  • Finally, notice again that `chart` is neither a key nor a string. It’s a variable. This means there’s no way to refer to the chart inside the chart itself. The only way to have a true top state is a somewhat ugly looking: chart_variable = { topstate= { } } ( We could make the code realize that no “initial=topstate” declaration is needed if the table only has one state. )

Those few rules are simple enough to write code against. All we need is a C function that takes a lua table of this format, and call the appropriate builder functions.

The Lua State Builder Link to heading

Let’s look at some pseudo code for our C based builder.

 hsm_state BuildLuaState(  string * state_name, lua_data * table )
{
   // tell hsm builder to start a new state 
   int state_id= hsmBegin( state_name );

   // hsm builder requires the initial state to be defined first 
   // look up the name of the initial state, pass on the name:value pair
   // if this were real, there'd be error handling 
   const char * initial_state = table[“initial”];
   BuildLuaSateHelper( initial_state, table [ initial_state ] );
 
   for ( key,value in table ) {
       // just pseudo code: but skip the initial state cause we handled it already
       if (key != “initial”) {
          BuildLuaStateHelper( key, value );
       }
   }

   // don’t forget to finish building the state
   hsmEnd();

   // return the state we just made
   return hsmResolve( state_id );
}

void BuildLuaStateHelper( string * key, lua_data * value ) 
{  
     if (value is table ) {
        // according to our rules, states are always tables
        const char * stateName= key;
        // for pseduo-code recursion is fine
        BuildLuaState( key, table ); 
     }
     else {
        // not a table? then its an event:
        const char * eventName= key;
        
        // enter and exit are special:
        if (eventName == "enter") {
            hsmOnEnterUD( RunLuaFunction, (void*) value );
        }
        else 
        if (eventName == "exit") {
            hsmOnExitUD( RunLuaFunction, (void*) value );
        }
        else  {
           // tell hsm builder to declare an event handler.
           // it'll call StringMatch whenever an event is triggered
           // and pass eventName to compare against the actual event. 
           hsmOnEventUD( StringMatch, eventName );
       
           if (value is string) {
             // look up the target state handle 
             // this works even if the state hasn’t been declared yet. 
             int target= hsmState( value );
          
             // tell hsm builder: if that string match passed transition
             hsmGoto( target );
           }
           else
           if (value is function) {
              // in this case, when that string match passes, 
              // we’ll run the lua function
              hsmRunUD( RunLuaFunction, (void*) value );
           }
        }
     }
   } 
}

If extracting the eventName from lua requires copying the string, then the StringMatch related code might need additional work to mange that eventName copy. Perhaps, in that case a CRC would work better. Baring that potential wrinkle, StringMatch will just look something like:

 // status: state of the statemachine when the event is fired
// user_data: the eventName (from the table) we're looking for
hsm_bool StringMatch( hsm_status status, void * user_data ) 
{
   return strcmp( status->event->name, (char*) user_data )==0;
}

At this point, we’re pretty much done coding, the only truly interesting part left to the code is: RunLuaFunction(). It’s just a standard hsm-statechart event handler, and rules already say what it should do… but sketching it out will help verify what the code needs.

 hsm_state RunLuaFunction ( hsm_status status, void * _value ) 
{
      hsm_state ret=0; // unhandled by default
      
      lua_function* value= (lua_function*) _value;
      lua_data * result= lua_call( value, status );
      if (result is string) {
           const char *target_state= result;
           // even though we have finished building, 
           // the builder still has its mapping table:
           // we can search by name to find a state
           ret= hsmResolveState( target_state );
      }
      else 
      if (result is boolean) && (result is true ) {
           ret= HsmStateHandled();
      }
     return ret;
}

Signals Across the Boundary Link to heading

Beyond where states are defined, there was the initial question of who owns the statemachine. Since the states are being fully driven by the hsm-statechart engine, it makes sense to keep the machine in the C code, but providing Lua ways to create a machine, and use its interface.

Looking through the interface, though, raises an interesting question: how to define the event payloads in a way that both lua and C can use meaningfully. For instance, if there is a “mouse click event”, or a “xbox controller button event” – the payload might consist of which button was pressed, and where the mouse, or where the sticks, were positioned at that time.

If the C side code initiates the event, there could be a Lua event callback which wants to peek at its event data. The reverse is true as well: if Lua generates the event, there might be C code wanting to evaluate the associated lua event data.

The statechart code was designed to keep the definition of events up to user code - so user code, ultimately, is going to have to handle the translation. The interface needs to keep it simple, but there’s going to have to be two functions in total: “Translate C event to Lua event”, and “Translate Lua event to C”

It’s probably simplest to make these functions callbacks global – used for all events across all statemachines in the app – and only worry about finding someway to target particular machines, or particular lua “environments” if that were to really prove necessary.

Lua State Instance Data Link to heading

The design wouldn’t be complete without looking at per-state instance data generated by lua. State instance data isn’t quite as important in lua as it is in C – Lua’s garbage collection and weak tables would allow us to store our data somewhere “globally” easily enough – still, might as well.

In hsm-statechart, a state’s enter function can return custom, opaque, data back to the machine. The machine then automatically passes that data back to the state whenever an event is processed. This allows us to simulate “state instance data” for states that want it without hurting those that don’t

To provide instance data for lua states, we just need to extend the BuildLuaState handling of “entry”. We will want a C callback similar to RunLuaFunction, but it will have to pass back to the machine whatever data object the lua function returns. The C callback will probably have to adjust the lua data’s ref count ( however that actually works i need to figure out ) so that the garbage collector doesn’t reclaim the data before the state has exit’ed.

Regardless of whether the lua description specifies an “exit” event, anytime `entry` is listed, we’ll probably need to register an exit on the C side to clean up whatever lua memory we were keeping out of the garbage.