QP/C: 5. Elaborating State Machines of Active Objects

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.

Prev: 4. Designing an Event-Driven Application
Next: 6. Defining Event Signals and Event Parameters

I hope that the analysis of the sequence diagram in Figure 4-1 makes it clear that actions performed by an active object depend as much on the events it receives, as on the internal mode of the object. For example, the Missile active object handles the TIME_TICK event very differently when the Missile is in flight (Figure 4-1(12)) compared to the time when it is not (Figure 4-1(3)). The best known mechanism of handling such modal behavior is through state machines because a state machine makes the behavior explicitly dependent on both the event and the state of an object. In Chapter 2 of Practical UML Statecharts in C/C++, Second Edition I introduce UML state machine concepts more thoroughly. In this section, I give a cursory explanation of the state machines associated with each object in the "Fly 'n' Shoot" game.

5.1 The Missile Active Object

I start with the Missile state machine shown in Figure 5-1, because it turns out to be the simplest one. The explanation section immediately following the diagram illuminates the interesting points.

Note:: A UML state diagram like Figure 5-1 preserves the general form of the traditional state transition diagrams, where states are represented as nodes and transitions as arcs connecting the nodes. In the UML notation the state nodes are represented as rectangles with rounded corners. The name of the state appears in bold type in the name compartment at the top of the state. Optionally, right below the name, a state can have an internal transition compartment separated from the name by a horizontal line. The internal transition compartment can contain entry actions (actions following the reserved symbol "entry"), exit actions (actions following the reserved symbol "exit"), and other internal transitions (e.g., those triggered by TIME_TICK in Figure 5-1(3)). State transitions are represented as arrows originating at the boundary of the source state and pointing to the boundary of the target state. At a minimum, a transition must be labeled with the triggering event. Optionally, the trigger can be followed by event parameters, a guard, and a list of actions.

Figure 5-1 Missile state machine diagram.

(1) The state transition originating at the black ball is called the initial transition. Such transition designates the first active state after the state machine object is created. An initial transition can have associated actions, which in the UML notation are enlisted after the forward slash "/". In this particular case, the Missile state machine starts in the "armed" state and the actions executed upon the initialization consist of subscribing to the event TIME_TICK. Subscribing to an event means that the framework will deliver the specified event to the Missile active object every time the event is published to the framework. Chapter 7 of Practical UML Statecharts in C/C++, Second Edition describes the implementation of the publish-subscribe event delivery in QF.

(2) The arrow labeled with the MISSILE_FIRE(x, y) event denotes a state transition, that is, change of state from "armed" to "flying". The MISSILE_FIRE(x, y) event is generated by the Ship object when the Player triggers the Missile (see the sequence diagram in Figure 4-1). In the MISSILE_FIRE event, Ship provides Missile with the initial coordinates in the event parameters (x, y).

Note:: The UML intentionally does not specify the notation for actions. In practice, the actions are often written in the programming language used for coding the particular state machine. In all state diagrams in this book, I assume the C programming language. Furthermore, in the C expressions I refer to the data members associated with the state machine object through the me-> prefix and to the event parameters through the e-> prefix. For example, the action me->x = e->x; means that the internal data member x of the Missile active object is assigned the value of the event parameter x.

(3) The event name TIME_TICK enlisted in the compartment below the state name denotes an internal transition. Internal transitions are simple reactions to events performed without a change of state. An internal transition, as well as a regular transition, can have a guard condition, enclosed in square brackets. Guard condition is a Boolean expression evaluated at runtime. If the guard evaluates to TRUE, the transition is taken. Otherwise, the transition is not taken and no actions enlisted after the forward slash "/" are executed. In this particular case, the guard condition checks whether the x-coordinate propagated by the Missile speed is still visible on the screen. If so, the actions are executed. These actions include propagation of the Missile position by one step and posting the MISSILE_IMG event with the current Missile position and the MISSILE_BMP bitmap number to the Tunnel active object. Direct event posting to an active object is accomplished by the QF function QActive_postFIFO(), which I discuss in Chapter 7 of Practical UML Statecharts in C/C++, Second Edition.

(4) The same event TIME_TICK with the [else] guard denotes a regular state transition with the guard condition complementary to the other occurrence of the TIME_TICK event in the same state. In this case, the TIME_TICK transition to "armed" is taken if the Missile object flies out of the screen.

(5) The event HIT_MINE(score) triggers another transition to the "armed" state. The action associated with this transition posts the DESTROYED_MINE event with the parameter e->score to the Ship object, to report destroying the mine.

(6) The event HIT_WALL triggers a transition to the "exploding" state, with the purpose of animating the explosion bitmaps on the display.

(7) The label "entry" denotes the entry action to be executed unconditionally upon the entry to the "exploding" state. This action consists of clearing explosion counter (me->exp_ctr) member of the Missile object.

(8) The TIME_TICK internal transition is guarded by the condition that the explosion does not scroll off the screen, and that the explosion counter is lower than 16. The actions executed include propagation of the explosion position and posting the EXPLOSION_IMG event to the Tunnel active object. Please note that the bitmap of the explosion changes as the explosion counter gets bigger.

(6) The TIME_TICK regular transition with the complementary guard changes the state back to the "armed" state. This transition is taken after the animation of the explosion completes.

5.2 The Ship Active Object

The state machine of the Ship active object is shown in Figure 5-2. This state machine introduces the profound concept of hierarchical state nesting. The power of state nesting derives from the fact that it is designed to eliminate repetitions that otherwise would have to occur.

One of the main responsibilities of the Ship active object is to maintain the current position of the Ship. On the original LM3S811 board, this position is determined by the potentiometer wheel (see Figure 2-2). The PLAYER_SHIP_MOVE(x, y) event is generated whenever the wheel position changes, as shown in the sequence diagram (Figure 4-1). The Ship object must always keep track of the wheel position, which means that all states of the Ship state machine must handle the PLAYER_SHIP_MOVE(x, y) event.

In the traditional finite state machine (FSM) formalism, you would need to repeat the Ship position update from the PLAYER_SHIP_MOVE(x, y) event in every state. But such repetitions would bloat the state machine and, more importantly, would represent multiple points of maintenance both in the diagram and the code. Such repetitions go against the DRY principle (Don't Repeat Yourself), which is vital for flexible and maintainable code.

Hierarchical state nesting remedies the problem. Consider the state "active" that surrounds all other states in Figure 5-2. The high-level "active" state is called the superstate and is abstract in that the state machine cannot be in this state directly, but only in one of the states nested within, which are called the substates of "active". The UML semantics associated with state nesting prescribes that any event is first handled in the context of the currently active substate. If the substate cannot handle the event, the state machine attempts to handle the event in the context of the next-level superstate. Of course, state nesting in UML is not limited to just one level and the simple rule of processing events applies recursively to any level of nesting.

Specifically to the Ship state machine diagram shown in Figure 5-2, suppose that the event PLAYER_SHIP_MOVE(x, y) arrives when the state machine is in the "parked" state. The "parked" state does not handle the PLAYER_SHIP_MOVE(x, y) event. In the traditional finite state machine this would be the end of story�the PLAYER_SHIP_MOVE(x, y) event would be silently discarded. However, the state machine in Figure 5-2 has another layer of the "active" superstate. Per the semantics of state nesting, this higher-level superstate handles the PLAYER_SHIP_MOVE(x, y) event, which is exactly what's needed. The same exact argumentation applies for any other substate of the "active" superstate, such as "flying" or "exploding", because none of these substates handle the PLAYER_SHIP_MOVE(x, y) event. Instead, the "active" superstate handles the event in one single place, without repetitions.

Figure 5-2 Ship state machine diagram.

(1) Upon the initial transition, the Ship state machine enters the "active" superstate and subscribes to events TIME_TICK and PLAYER_TRIGGER.

(2) At each level of nesting a superstate can have a private initial transition that designates the active substate after the superstate is entered directly. Here the initial transition of state "active" designates the substate "parked" as the initial active substate.

(3) The "active" superstate handles the PLAYER_SHIP_MOVE(x, y) event as an internal transition in which it updates the internal data members me->x and me->y from the event parameters e->x and e->y, respectively.

(4) The TAKE_OFF event triggers transition to "flying". This event is generated by the Tunnel object when the Player starts the game (see the description of the game in Section 2. Let's Play).

(5) The entry actions to "flying" include clearing the me->score data member and posting the event SCORE with the event parameter me->score to the Tunnel active object.

(6) The TIME_TICK internal transition causes posting the event SHIP_IMG with current Ship position and the SHIP_BMP bitmap number to the Tunnel active object. Additionally, the score is incremented for surviving another time tick. Finally, when the score is "round" (divisible by 10) it is also posted to the Tunnel active object. This decimation of the SCORE event is performed just to reduce the bandwidth of the communication, because the Tunnel active object only needs to give an approximation of the running score tally to the user.

(7) The PLAYER_TRIIGGER internal transition causes posting the event MISSILE_FIRE with current Ship position to the Missile active object. The parameters (me->x, me->y) provide the Missile with the initial position from the Ship.

(8) The DESTROYED_MINE(score) internal transition causes update of the score kept by the Ship. The score is not posted to the Table at this point, because the next TIME_TICK will send the "rounded" score, which is good enough for giving the Player the score approximation.

(9) The HIT_WALL event triggers transition to "exploding"

(10) The HIT_MINE(type) event also triggers transition to "exploding"

(11) The "exploding" state of the Ship state machine is very similar to the "exploding" state of Missile (see Figure 5-1(7-9)).

(12) The TIME_TICK[else] transition is taken when the Ship finishes exploding. Upon this transition, the Ship object posts the event GAME_OVER(me->score) to the Tunnel active object to terminate the game and display the final score to the Player.

5.3 The Tunnel Active Object

The Tunnel active object has the most complex state machine, which is shown in Figure 5-3. Unlike the previous state diagrams, the diagram in Figure 5-3 shows only the high-level of abstraction and omits a lot of details such as most entry/exit actions, internal transitions, guard conditions, or actions on transitions. Such a "zoomed out" view is always legal in the UML, because UML allows you to choose the level of detail that you want to include in your diagram.

The Tunnel state machine uses state hierarchy more extensively than the Ship state machine in Figure 5-2. The explanation section immediately following Figure 5-3 illuminates the new uses of state nesting as well as the new elements not explained yet in the other state diagrams.

Figure 5-3 Tunnel state machine diagram.

(1) An initial transition can target a substate at any level of state hierarchy, not necessarily just the next-lower level. Here the top-most initial transition goes down two levels to the substate "demo".

(2) The superstate "active" handles the PLAYER_QUIT event as a transition to the final state (see explanation of element (3)). Please note that the PLAYER_QUIT transition applies to all substates directly or transitively nested in the "active" superstate. Because a state transition always involves execution of all exit actions from the states, the high-level PLAYER_QUIT transition guarantees the proper cleanup that is specific to the current state context, whichever substate happens to be active at the time when the PLAYER_QUIT event arrives.

(3) The final state is indicated in the UML notation as the bull's-eye symbol and typically indicates destruction of the state machine object. In this case, the PLAYER_QUIT event indicates termination of the game.

(4) The MINE_DISABLED(mine_id) event is handled at the high level of the "active" state, which means that this internal transition applies to the whole sub-machine nested inside the "active" superstate. (See also the discussion of Mine object in the next section.)

(5) The entry action to the "demo" state starts the screen time event (timer) me->screenTimeEvt to expire in 20 seconds. Time events are allocated by the application, but they are managed by the QF framework. QF provides functions to arm a time event, such as QTimeEvt_postIn() for one-shot timeout, and QTimeEvt_postEvery() for periodic time events. Arming a time event is in effect telling the QF framework, for instance, "Give me a nudge in 20 seconds". QF then posts the time event (the event me->screenTimeEvt in this case) to the active object after the requested number of clock ticks. Chapters 6 and 7 of Practical UML Statecharts in C/C++, Second Edition talk about time events in detail.

(6) The exit action from the "demo" state disarms the me->screenTimeEvt time event. This cleanup is necessary when the state can be exited by a different event than the time event, such as the PLAYER_TRIGGER transition.

(7) The SCREEN_TIMEOUT transition to "screen_saver" is triggered by the expiration of the me->screenTimeEvt time event. The signal SCREEN_TIMEOUT is assigned to this time event upon initialization and cannot be changed later.

(8) The transition triggered by PLAYER_TRIGGER applies equally to the two substates of the "screen_saver" superstate.

5.4 The Mine Components

Mines are also modeled as hierarchical state machines, but are not active objects. Instead, Mines are components of the Tunnel active object and share its event queue and priority level. The Tunnel active object communicates with the Mine components synchronously by directly dispatching events to them via the function QHsm_dispatch(). Mines communicate with Tunnel and all other active objects asynchronously by posting events to their event queues via the function QActive_postFIFO().

Note:: Active objects exchange events asynchronously, meaning that the sender of the event merely posts the event to the event queue of the recipient active object without waiting for the completion of the event processing. In contrast, synchronous event processing corresponds to a function call (e.g., QHsm_dispatch()), which processes the event in the caller's thread of execution.

Figure 5-4 The Table active object manages two types of Mines.

As shown in Figure 5-4, Tunnel maintains the data member mines[], which is an array of pointers to hierarchical state machines (QHsm *). Each of these pointers can point either to a Mine1 object, a Mine2 object, or NULL, if the entry is unused. Please note that Tunnel "knows" the Mines only as generic state machines (pointers to the QHsm structure defined in QP). Tunnel dispatches events to Mines uniformly, without differentiating between different types of Mines. Still, each Mine state machine handles the events it its specific way. For example, Mine type 2 checks for collision with the Missile differently than with the Ship while Mine type 1 handles both identically.

Note:: The last point is actually very interesting. Dispatching the same event to different Mine objects results in different behavior, specific to the type of the Mine, which in OOP is known as polymorphism. I'll have more to say about this in Chapter 3 of Practical UML Statecharts in C/C++, Second Edition.

Each Mine object is fairly autonomous. The Mine maintains its own position and is responsible for informing the Tunnel object whenever the Mine gets destroyed or scrolls out of the display. This information is vital for the Tunnel object so that it can keep track of the unused Mines.

Figure 5-5 shows a hierarchical state machine of Mine2 state machine. Mine1 is very similar, except that it uses the same bitmap for testing collisions with the Missile and the Ship.

Figure 5-5 Mine2 state machine diagram.

(1) The Mine starts in the "unused" state.

(2) The Tunnel object plants a Mine by dispatching the MINE_PLANT(x, y) event to the Mine. The Tunnel provides the (x, y) coordinates as the original position of the Mine.

(3) When the Mine scrolls off the display the state machine transitions to "unused".

(4) When the Mine hits the Ship the state machine transitions to "unused".

(5) When the Mine scrolls finishes exploding the state machine transitions to "unused".

(6) When the Mine is recycled by the Tunnel object the state machine transitions to "unused".

(7) The exit action in the "unused" state posts the MINE_DISABLDED(mine_id) event to the Tunnel active object. Through this event, the Mine informs the Tunnel that it's becoming disabled, so that Tunnel can update its mines[] array (see also Figure 5-4(4)). The mine_id parameter of the event becomes the index into the mines[] array. Please note that generating the MINE_DISABLDED(mine_id) event in the exit action from "used" is much safer and more maintainable than repeating this action in each individual transition (3), (4), (5), and (6).

Prev: 4. Designing an Event-Driven Application
Next: 6. Defining Event Signals and Event Parameters