QP/C Reference Manual » QP/C Tutorial

7. Coding Hierarchical State Machines

This QP/C Tutorial is adapted from Chapter 1 of Practical UML Statecharts in C/C++, Second Edition
by Miro Samek, the founder and president of Quantum Leaps, LLC.

qp_tutorial.jpg

Prev: 6. Defining Event Signals and Event Parameters
Next: 8. Using the Built-in Real-Time Kernels and Third-Party RTOSes

Contrary to widespread misconceptions, you don't need big design automation tools to translate hierarchical state machines (UML statecharts) into efficient and highly maintainable C or C++. This section explains how to hand-code the Ship state machine from Figure 5-2 with the help of the QF real-time framework and the QEP hierarchical processor, which is also part of the QP event-driven platform. Once you know how to code this state machine, you know how to code them all.

The source code for the Ship state machine is found in the file ship.c located either in the DOS version or the Cortex-M3 version of the "Fly 'n' Shoot" game. I break the explanation of this file into three steps.

7.1 Step 1: Defining the Ship Structure

In the first step you define the Ship data structure. Just like in case of events, you use inheritance to derive the Ship structure from the framework structure QActive (see the sidebar Encapsulation and Single Inheritance in C). Creating this inheritance relationship ties the Ship structure to the QF framework. The main responsibility of the QActive base structure is to store the information about the current active state of the state machine, as well as the event queue and priority level of the Ship active object. In fact, QActive itself derives from a simpler QEP structure QHsm that represents just the current active state of a hierarchical state machine. On top of that information, almost every state machine must also store other "extended-state" information. For example, the Ship object is responsible for maintaining the Ship position as well as the score accumulated in the game. You supply this additional information by means of data members enlisted after the base structure member super, as shown in Listing 7-1.

Listing 7-1 Deriving the Ship structure in file ship.c. 

 (1) #include "qp_port.h"                                         /* the QP port */
 (2) #include "bsp.h"                                   /* Board Support Package */
 (3) #include "game.h"                                       /* this application */

     /* local objects -----------------------------------------------------------*/
 (4) typedef struct ShipTag {
 (5)     QActive super;                        /* derive from the QActive struct */
 (6)     uint8_t x;          /* x-coordinate of the Ship position on the display */
 (7)     uint8_t y;          /* y-coordinate of the Ship position on the display */
 (8)     uint8_t exp_ctr;       /* explosion counter, used to animate explosions */
 (9)     uint16_t score;                            /* running score of the game */
(10) } Ship;                          /* the typedef-ed name for the Ship struct */

                                                   /* state handler functions... */
(11) static QState Ship_active   (Ship *me, QEvent const *e);
(12) static QState Ship_parked   (Ship *me, QEvent const *e);
(13) static QState Ship_flying   (Ship *me, QEvent const *e);
(14) static QState Ship_exploding(Ship *me, QEvent const *e);

(15) static QState Ship_initial  (Ship *me, QEvent const *e);

(16) static Ship l_ship;          /* the sole instance of the Ship active object */

     /* global objects ----------------------------------------------------------*/
(17) QActive * const AO_ship = (QActive *)&l_ship;  /* opaque pointer to Ship AO */

Note:
I like to keep active objects, and indeed all state machine objects (such as Mines), strictly encapsulated. Therefore, I don't put the state machine structure definitions in header files but rather define them right in the implementation file, such as ship.c. That way, I can be sure that the internal data members of the Ship structure are not known to any other parts of the application.
Note:
I use a simple naming convention to strengthen the association between the structures and the functions designed to operate on these structures. First, I name the functions by combining the typedef'ed structure name with the name of the operation (e.g., Ship_active). Second, I always place the pointer to the structure as the first argument of the associated function and I always name this argument me (e.g., Ship_active(Ship *me, ...)).

7.2 Step 2: Initializing the State Machine

The state machine initialization is divided into the following two steps for increased flexibility and better control of the initialization timeline:

  1. The state machine "constructor"; and
  2. The top-most initial transition.

The state machine "constructor", such as Ship_ctor(), intentionally does not execute the top-most initial transition defined in the initial pseudostate because at that time some vital objects can be missing and critical hardware might not be properly initialized yet3. Instead, the state machine "constructor" merely puts the state machine in the initial pseudostate. Later, the user code must trigger the top-most initial transition explicitly, which happens actually inside the function QActive_start() (see Listing 3-11(18-20)). Listing 7-2 shows the instantiation (the "constructor" function) and initialization (the initial pseudostate) of the Ship active object.

Listing 7-2 Instantiation and Initialization of the Ship active object in ship.c. 

 (1) void Ship_ctor(void) {                                     /* instantiation */
 (2)     Ship *me = &l_ship;
 (3)     QActive_ctor(&me->super, (QStateHandler)&Ship_initial);
 (4)     me->x = GAME_SHIP_X;
 (5)     me->y = GAME_SHIP_Y;
     }
     /*..........................................................................*/
 (6) QState Ship_initial(Ship *me, QEvent const *e) {          /* initialization */
 (7)     QActive_subscribe((QActive *)me, TIME_TICK_SIG);
 (8)     QActive_subscribe((QActive *)me, PLAYER_TRIGGER_SIG);

 (9)     return Q_TRAN(&Ship_active);             /* top-most initial transition */
     }

Note:
The macro Q_TRAN() must always follow the return statement.

7.3 Step 3: Defining State Handler Functions

In the last step, you actually code the Ship state machine by implementing one state at a time as a state handler function. To determine what elements belong the any given state handler function, you follow around the state's boundary in the diagram (Figure 5-2). You need to implement all transitions originating at the boundary, any entry and exit actions defined in the state, as well as all internal transitions enlisted directly in the state. Additionally, if there is an initial transition embedded directly in the state, you need to implement it as well.

Take for example the state "flying" shown in Figure 5-2. This state has an entry action and two transitions originating at its boundary: HIT_WALL and HIT_MINE(type), as well as three internal transitions TIME_TICK, PLAYER_TRIGGER, and DESTROYED_MINE(score). The "flying" state nests inside the "active" superstate. Listing 7-3 shows two state handler functions of the Ship state machine from Figure 5-2. The state handler functions correspond to the states "active" and "flying", respectively. The explanation section immediately following the listing highlights the important implementation techniques.

Listing 7-3 State handler functions for states "active" and "flying" in ship.c. 

 (1) QState Ship_active(Ship *me, QEvent const *e) {
 (2)     switch (e->sig) {
 (3)         case Q_INIT_SIG: {                     /* nested initial transition */
 (4)             /* any actions associated with the initial transition */
 (5)             return Q_TRAN(&Ship_parked);
             }
 (6)         case PLAYER_SHIP_MOVE_SIG: {
 (7)             me->x = ((ObjectPosEvt const *)e)->x;
 (8)             me->y = ((ObjectPosEvt const *)e)->y;
 (9)             return Q_HANDLED();
             }
         }
(10)     return Q_SUPER(&QHsm_top);                     /* return the superstate */
     }
     /*..........................................................................*/
     QState Ship_flying(Ship *me, QEvent const *e) {
         switch (e->sig) {
(11)         case Q_ENTRY_SIG: {
(12)             ScoreEvt *sev;

                 me->score = 0;                               /* reset the score */
(13)             sev = Q_NEW(ScoreEvt, SCORE_SIG);
(14)             sev->score = me->score;
(15)             QActive_postFIFO(AO_Tunnel, (QEvent *)sev);
(16)             return Q_HANDLED();
             }
             case TIME_TICK_SIG: {
                 /* tell the Tunnel to draw the Ship and test for hits */
                 ObjectImageEvt *oie = Q_NEW(ObjectImageEvt, SHIP_IMG_SIG);
                 oie->x   = me->x;
                 oie->y   = me->y;
                 oie->bmp = SHIP_BMP;
                 QActive_postFIFO(AO_Tunnel, (QEvent *)oie);

                 ++me->score;  /* increment the score for surviving another tick */

                 if ((me->score % 10) == 0) {           /* is the score "round"? */
                     ScoreEvt *sev = Q_NEW(ScoreEvt, SCORE_SIG);
                     sev->score = me->score;
                     QActive_postFIFO(AO_Tunnel, (QEvent *)sev);
                 }
                 return Q_HANDLED();
             }
             case PLAYER_TRIGGER_SIG: {                   /* trigger the Missile */
                 ObjectPosEvt *ope = Q_NEW(ObjectPosEvt, MISSILE_FIRE_SIG);
                 ope->x = me->x;
                 ope->y = me->y + SHIP_HEIGHT - 1;
                 QActive_postFIFO(AO_Missile, (QEvent *)ope);
                 return Q_HANDLED();
             }
             case DESTROYED_MINE_SIG: {
                 me->score += ((ScoreEvt const *)e)->score;
                 /* the score will be sent to the Tunnel by the next TIME_TICK */
                 return Q_HANDLED();
             }
(17)         case HIT_WALL_SIG:
(18)         case HIT_MINE_SIG: {
(19)             /* any actions associated with the transition */
(20)             return Q_TRAN(&Ship_exploding);
             }
         }
(21)     return Q_SUPER(&Ship_active);                  /* return the superstate */
     }

Note:
The initial transition must necessarily target a direct or transitive substate of a given state. An initial transition cannot target a peer state or go up in state hierarchy to higher-level states, which in the UML would represent a "malformed" state machine.
Note:
The association between the event signal and event structure (event parameters) is established at the time the event is generated. All recipients of that event must know about this association to perform the cast to the correct event structure.
Note:
In C and C++, a pointer-to-function QHsm_top() can be written either as QHsm_top, or &QHsm_top. Even though the notation QHsm_top is more succinct, I prefer adding the ampersand explicitly, to leave absolutely no doubt that I mean a pointer-to-function &QHsm_top.
When implementing state handler functions you need to keep in mind that the QEP event processor is in charge here rather than your code. QEP will invoke a state handler function for various reasons: for hierarchical event processing, for execution of entry and exit actions, for triggering initial transitions, or even just to elicit the superstate of a given state handler. Therefore, you should not assume that a state handler would be invoked only for processing signals enlisted in the case statements. You should avoid any code outside the switch statement, especially code that would have side effects.

Prev: 6. Defining Event Signals and Event Parameters
Next: 8. Using the Built-in Real-Time Kernels and Third-Party RTOSes

logo_ql_TM.jpg
Copyright © 2002-2008 Quantum Leaps, LLC. All Rights Reserved.
http://www.quantum-leaps.com
Generated on Thu Jul 3 09:45:52 2008 for QP/C by  doxygen 1.5.4