Earlier, I posted about State Descriptors. Now I want to show why using state descriptors to track the depth of each state in a statechart can be so useful. Namely: it enables fast, low overhead, LCA - lowest common ancestor - searches.

Since no one can be more bored of the main menu example than I, here’s part of the state machine I use for exploration and combat in Dawn of Sorcery. I’ll show you what the LCA means in terms of this state machine, and why it’s necessary, and then I’ll show how having the depth on hand via descriptors can make the LCA search trivial.

Combat in Dawn of Sorcery

The Combat Statechart Link to heading 

 **Play:**
  - init >> Explore. 
  - spawned\_combat >> Fight.  
  **Explore:**
    - entry / show\_world();
    - exit / hide\_world();
  **Fight:**
    - init >> RunTime.
    - entry / display\_combat\_ui(); 
    - exit / hide\_combat\_ui();
    - ability\_done >> RunTime.
    **RunTime:**
    - entry / start\_timer(); 
    - turn\_started \[ is players\_turn \] >> PlayerTurn.
    - turn\_started >> AITurn.
    **AITurn:**
    - entry / run\_ai\_turn();
    **PlayerTurn:**
    - init >> AbilitySelect.
    - entry / show\_player\_ui();
    - exit / hide\_player\_ui(); 
      **AbilitySelect:**
      - entry / enable\_player\_ui();
      - exit / disable\_player\_ui();
      - ability\_selected >> RunAbility;
      **RunAbility:** 
      - entry / run\_ability();

It’s not necessary to understand the chart completely, but here’s a quick overview:

  1. In Play you can be in either Explore or Fight mode.
  2. the first thing Fight does, besides display the ui, is “RunTime”
  3. RunTime starts a timer, which eventually results in either the a player or an AI taking a turn, this is communicated via the turn_started event.
  4. AITurn always runs the action run_ai_turn()
  5. PlayerTurn first shows the player ui, then after moving into AbilitySelect allows the player to select an ability ( ex. attack, or heal ) by clicking on the UI.
  6. RunAbility runs the selected player ability.

In Dawn, an ability does a variety of things as it runs. For instance, it shows an animation, it calculates and applies damages, it displays the damage results on screen, etc. This process may several seconds as the player watches combat unfold.

An important point for this chart, then, is that both RunAbility and AITurn “hang out” until the ability has finished running; until it has generated an “ability_done” event. As shown in the chart above, Fight hears that event, and moves back into RunTime.

How does the machine do this, and what does any of this have to do with LCA?

First, realize because it’s a hierarchical machine, when we are in the RunAbility state we are not in just one state, but several. According to the chart, we are actually in: Play, Fight, PlayerTurn, *and* RunAbility all at the same time.

When events like _ability_don_e are triggered, the statemachine starts at the inner most state ( in this case RunAbility ) and checks to see if the event is handled by that state. If it’s not, the statemachine checks with the parent state ( PlayerTurn ), then that state’s parent state, and so one. Since Fight handles ability_done, we only have to go up a few levels.

The advantage of this “bubbling of events” is that, since Fight is an ancestor of both PlayerTurn and AITurn, we only have to specify the handler once. We don’t have duplicate the behavior of ability_done for AI and Player code. This, really, is the purpose of hierarchical statemachines: we can share behavior between states.

In this case, Fight happens to be a special kind of ancestor: it’s the lowest common ancestor of both AITurn and RunAbility. That is to say, walking up the hierarchy from AITurn and RunAbility – it’s the first state that the two have in common. We can see this by laying their full list of states side by side:

**Play**, **Fight**, **PlayerTurn**, **RunAbility**
**Play, Fight, AITurn**

They both share “Play” and “Fight” as ancestors, but “Fight” is the “inner most” or “lowest” ancestor they have in common.

Transitions Link to heading

As mentioned earlier, when Fight hears ability_done it initiates a transition to RunTime so that a new character, either the player or an AI, can take a turn. A transition from one state to another generally(*) only wants to exit the states the chart is not going to be in once all the new states are entered.

Here are the hierarchies of RunAbility and RunTime side by side.

**Play**, **Fight**, **PlayerTurn**, **RunAbility**
**Play, Fight, RunTime**

This indicates when we transition from RunAbility to RunTime, we want to exit the individual states “RunAbility” and “PlayerTurn”, and then we want to enter “RunTime”. We do not want to exit “Fight”, nor do we want to exit “Play”, because we are still going to be in those states when all is said and done.

If you examine the actions associated with the various states in question this makes sense. PlayerTurn exit will hide_player_ui() which is good because its no longer the player’s turn. If we had exited Fight, however – which we’re not doing, we would have run hide_combat_ui(), which we don’t want because we’re still in combat.

Note while in this case, the state listening for the event is also the LCA of the transition: this is somewhat of a coincidence. The chart could easily have placed the ability_done handler all the way up in Play. If it had done so, that wouldn’t have changed the LCA of RunAbility and RunTime. Phrased a different way, if Play had the handler for ability_done, we still would only have wanted to exit up to, but not including, Fight.

Fast LCA transitions Link to heading

Finding the LCA at run-time, and only exiting the states we want to, can be a tad tricky – especially if we want to be efficient about it. In essence, we need to evaluate two branches in a tree – the source and the destination states – we need to seek out and compare parents, cache paths, and more. You can find lots of papers via google and wikipedia about the issue, and its complexity.

We, however, have an advantage. We have the state descriptor. As shown before, the descriptor identifies the current processing state of the statemachine.

// a sample state descriptor
struct state_info {
   state_function_t process;  // pointer to an event processing function
   int depth;                 // depth of the state
   state_info* parent;        // pointer to immediate parent
   const char * name;         // a name for debugging
};

Using a state descriptor, we can record the depth of every state at the time the state is declared. We start with 0 at the outermost state, and we assign every direct child of any given parent the depth of its parent depth +1. In this case, Play is the outermost state, so it gets a depth of 0. Explore and Fight are its direct children, so they both have a depth of 1, and so on.

The states involved in our example transition, along with their depths, are simply:

**source state      => 0:Play**, **1:Fight**, **2:PlayerTurn**, 3:**RunAbility**
**destination state => 0:Play, 1:Fight, 2:RunTime**

This arrangement suggests a simple algorithm:

  • Start with our source and destination states. In this case, RunAbility and RunTime respectively. The former has a depth of 3, the latter a 2.

  • Peel back the source and destination states until they are at the same depth. In this case RunAbility is deeper than RunTime, so peel it back. That is: move the source side of things up from RunAbility to PlayerTurn. Now both the source and destination sides have a depth of 2.

  • Peel back the two sides together until both sides are referring to the same state. In this case, if we move the source side up from PlayerTurn, we reach Fight; if we move the destination side up from RunTime, we reach also reach Fight. We are done, we’ve found that Fight is the least common ancestor.

Here it is in code:

// assumes src & dst are valid, 
// and that cant become NULL in a valid chart.
state_info_t* find_lca( state_info_t* src, state_info_t* dst )
{
    if (src!=dst) {
        // bring src up to the same level as dst
        while(src->depth > dst->depth) {
            src= src->parent;
        }
        // or, if dst was deeper, bring it up to src's level
        while(dst->depth > src->depth) {
            dst= dst->parent;
        }
        // now: keep going up till we are at the same node
        while(src != dst) {
            src= src->parent;
            dst= dst->parent;
        }
    }
    // we've got our LCA 
    // ( both src & dst are the same )
    return src;
}

It takes only a little bit more work to adapt this “find_lca” into a complete state transition algorithm, one that “exits” src as it moves up, and also records the path of “dst” as it goes up so we know what states to enter after the lowest common ancestor is found.

Here’s a good post that looks this style of LCA a bit more: http://www.leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-ii.html.

Footnotes Link to heading

(*) In UML statecharts there is actually a difference between “external” and “internal” transitions which dictate whether the LCA is exited, and then immediately re-entered, when a transition occurs. In my opinion, this is mainly for “completeness” sake. I believe you can generally achieve the results you want in systems that support only one or the other type of transition by simply having more (or less) levels of hierarchy.