The companion Website to this book at http://www.quantum-leaps.com/psicc2 contains the self-extracting archive with the complete source code of the QP event-driven platform and all executable examples described in this book; as well as documentation, development tools, resources, and more. You can uncompress the archive into any directory. The installation directory you choose will be referred henceforth as the QP Root Directory <qp>.

Specifically to the “Fly ‘n’ Shoot” example, the companion code contains two versions¹ The accompanying code actually contains many more versions of the “Fly ‘n’ Shoot” game, but they are not relevant at this point. of the game. I provide a DOS version for the standard Windows-based PC (see Figure 1.1) so that you don't need any special embedded board to play the game and experiment with the code.

Figure 1.1. The “Fly ‘n’ Shoot” game running in a DOS window under Windows XP.

I also provide an embedded version for the inexpensive² At the time of this writing the EV-LM3S811 kit was available for $49 (www.luminarymicro.com). ARM Cortex-M3-based Stellaris EV-LM3S811 evaluation kit (see Figure 1.2). Both the PC and Cortex-M3 versions use the exact same source code for all application components and differ only in the Board Support Package (BSP).

Figure 1.2. The “Fly ‘n’ Shoot” game running on the Stellaris EV-LM3S811 evaluation board.

The following description of the “Fly ‘n’ Shoot” game serves the dual purpose of explaining how to play the game and as the problem specification for the purpose of designing and implementing the software later in the chapter. To accomplish these two goals I need to be quite detailed, so please bear with me.

Your objective in the game is to navigate a spaceship through an endless horizontal tunnel with mines. Any collision with the tunnel or the mine destroys the ship. You can move the ship up and down with Up-arrow and Down-arrow keys on the PC (see Figure 1.1) or via the potentiometer wheel on the EV-LM3S811 board (see Figure 1.2). You can also fire a missile to destroy the mines in the tunnel by pressing the Spacebar on the PC or the User button on the EV-LM3S811 board. Score accumulates for survival (at the rate of 30 points per second) and destroying the mines. The game lasts for only one ship.

The game starts in a demo mode, where the tunnel walls scroll at the normal pace from right to left and the “Press Button” text flashes in the middle of the screen. You need to generate the “fire missile” event for the game to begin (press Spacebar on the PC or the User button on the EV-LM3S811 board).

You can have only one missile in flight at a time, so trying to fire a missile while it is already flying has no effect. Hitting the tunnel wall with the missile brings you no points, but you earn extra points for destroying the mines.

The game has two types of mines with different behavior. In the original Luminary Quickstart application both types of mines behave the same, but I wanted to demonstrate how state machines can elegantly handle differently behaving mines.

Mine type 1 is small, but can be destroyed by hitting any of its pixels with the missile. You earn 25 points for destroying a mine type 1. Mine type 2 is bigger but is nastier in that the missile can destroy it only by hitting its center, not any of the “tentacles.” Of course, the ship is vulnerable to the whole mine. You earn 45 points for destroying a mine type 2.

When you crash the ship, by either hitting a wall or a mine, the game ends and displays the flashing “Game Over” text as well as your final score. After 5 seconds of flashing, the “Game Over” screen changes back to the demo screen, where the game waits to be started again.

Additionally the application contains a screen saver because the OLED display of the original EV-LM3S811 board has burn-in characteristics similar to a CRT. The screen saver only becomes active if 20 seconds elapse in the demo mode without starting the game (i.e., the screen saver never appears during game play). The screen saver is a simple random pixel type rather than the “Game of Life” algorithm used in the original Luminary Quickstart application. I've decided to simplify this aspect of the implementation because the more elaborate pixel-mixing algorithm does not contribute any new or interesting behavior.

After a minute of running the screen saver, the display turns blank and only a single random pixel shows on the screen. Again, this is a little different from the original Quickstart application, which instead blanks the screen and starts flashing the User LED. I've changed this behavior because I have a better purpose for the User LED (to visualize the activity of the idle loop).

Before you program the “Fly ‘n’ Shoot” game to the EV-LM3S811 board, you might want to play a little with the original Quickstart application that comes preprogrammed with the EV-LM3S811 kit.

To program the “Fly ‘n’ Shoot” game to the Flash memory of the EV-LM3S811 board, you first connect the EV-LM3S811 board to your PC with the USB cable provided in the kit and make sure that the Power LED is on (see Figure 1.2). Next, you need to launch the IAR Embedded Workbench and open the workspace game-ev-lm3s811.eww located in the <qp>qpcexamplescortex-m3vanillaiargame-ev-lm3s811 directory. At this point your screen should look similar to the screenshot shown in Figure 1.3.

Figure 1.3. Loading the “Fly ‘n’ Shoot” game into the flash of LM3S811 MCU with IAR EWARM IDE.

The game-ev-lm3s811 project is set up to use the LMI FTDI debugger, which is the piece of hardware integrated on the EV-LM3S811 board (see Figure 1.2). You can verify this setup by opening the “Options” dialog box via the Project | Options menu. Within the “Options” dialog box, you need to select the Debugger category in the panel on the left. While you're at it, you could also verify that the Flash loading is enabled by selecting the “Download” tab. The checked “Use flash loader(s)” check box means that the Flash loader application provided by IAR will be first loaded to the RAM of the MCU, and this application will program the Flash with the image of your application.

To start the Flash programming process, select the Project | Debug menu, or simply click the Debug button (see Figure 1.3) in the toolbar. The IAR Workbench should respond by showing the Flash programming progress bar for several seconds, as shown in Figure 1.3. Once the Flash programming completes, the IAR EWARM switches to the IAR C-Spy debugger and the program should stop at the entry to main(). You can start playing the game either by clicking the Go button in the debugger or you can close the debugger and reset the board by pressing the Reset button. Either way, the “Fly ‘n’ Shoot” game is now permanently programmed into the EV-LM3S811 board and will start automatically on every powerup.

The IAR Embedded Workbench environment allows you to experiment with the “Fly ‘n’ Shoot” code very easily. You can edit the files and recompile the application at a click of a button (F7). The only caveat is that the first time after the installation of the IAR toolset you need to build the Luminary Micro driver library for the LM3S811 MCU from the sources. You accomplish this by loading the workspace ek-lm3s811.eww located in the directory <IAR-EWARM>ARMexamplesLuminaryStellarisoardsek-lm3s811, where <IAR-EWARM> stands for the directory name where you've installed the IAR toolset. In the ev-lm3s811.eww workspace, you select the “driverlib - Debug” project from the drop-down list at the top of the Workspace panel and then press F7 to build the library.

Perhaps the best place to start the explanation of the “Fly ‘n’ Shoot” application code is the main() function, located in the file main.c. Unless indicated otherwise in this chapter, you can browse the code in either the DOS version or the EV-LM3S811 version, because the application source code is identical in both. The complete main.c file is shown in Listing 1.1.

The QP event-driven platform is a collection of components, such as the QEP event processor that executes state machines according to the UML semantics and the QF real-time framework that implements the active object computing model. Active objects in QF are encapsulated state machines (each with an event queue, a separate task context, and a unique priority) that communicate with one another asynchronously by sending and receiving events, whereas QF handles all the details of thread-safe event exchange and queuing. Within an active object, the events are processed by the QEP event processor sequentially in a run-to-completion (RTC) fashion, meaning that processing of one event must necessarily complete before processing the next event. (See also Section 6.3.3 in Chapter 6.)

The QF real-time framework supports two event delivery mechanisms: the simple direct event posting to active objects and the more advanced mechanism called publish-subscribe that decouples event producers from the consumers. In the publish-subscribe mechanism, active objects subscribe to events by the framework. Event producers publish the events to the framework. Upon each publication request, the framework delivers the event to all active objects that had subscribed to that event type. One obvious implication of publish-subscribe is that the framework must store the subscriber information, whereas it must be possible to handle multiple subscribers to any given event type. The event delivery mechanisms are described in Chapters 6 and 7.

The utility macro Q_DIM(a) provides the dimension of a one-dimensional array a[] computed as sizeof(a)/sizeof(a[0]), which is a compile-time constant. The use of this macro simplifies the code because it allows me to eliminate many #define constants that otherwise I would need to provide for the dimensions of various arrays. I can simply hard-code the dimension right in the definition of an array, which is the only place that I specify it. I then use the macro Q_DIM() whenever I need this dimension in the code.

I like to keep the code and data of every active object strictly encapsulated within its own C-file. For example, all code and data for the active object Ship are encapsulated in the file ship.c, with the external interface consisting of the function Ship_ctor() and the pointer AO_Ship.

After the call to QF_run() the framework is in full control. The framework executes the application by calling your code, not the other way around. The function QF_run() never returns the control back to main(). In the DOS version of the “Fly ‘n’ Shoot” game, you can terminate the application by pressing the Esc key, in which case QF_run() exits to DOS but not to main(). In an embedded system, such as the Stellaris board, QF_run() runs forever or till the power is removed, whichever comes first.

To proceed further with the explanation of the “Fly ‘n’ Shoot” application, I need to step up to the design level. At this point I need to explain how the application has been decomposed into the active objects and how these objects exchange events to collectively deliver the functionality of the “Fly ‘n’ Shoot” game.

In general, the decomposition of a problem into active objects is not trivial. As usual in any decomposition, your goal is to achieve possibly loose coupling among the active object components (ideally no sharing of any resources), and you also strive for minimizing the communication in terms of the frequency and size of exchanged events.

In the case of the “Fly ‘n’ Shoot” game, I need to first identify all objects with reactive behavior (i.e., with a state machine). I applied the simplest object-oriented technique of identifying objects, which is to pick the frequently used nouns in the problem specification. From Section 1.2, I identified Ship, Missile, Mines, and Tunnel. However, not every state machine in the system needs to be an active object (with a separate task context, an event queue, and a unique priority level), and merging them is a valid option when performance or space is needed. As an example of this idea, I ended up merging the Mines into the Tunnel active object, whereas I preserved the Mines as independent state machine components of the Tunnel active object. By doing so I applied the “Orthogonal Component” design pattern described in Chapter 5.

The next step in the event-driven application design is assigning responsibilities and resources to the identified active objects. The general design strategy for avoiding sharing of resources is to encapsulate each resource inside a dedicated active object and to let that object manage the resource for the rest of the application. That way, instead of sharing the resource directly, the rest of the application shares the dedicated active object via events.

So, for example, I decided to put the Tunnel active object in charge of the display. Other active objects and state machine components, such as Ship, Missile, and Mines, don't draw on the display directly, but rather send events to the Tunnel object with the request to render the Ship, Missile, or Mine bitmaps at the provided (x, y) coordinates of the display.

With some understanding of the responsibilities and resource allocations to active objects I can move on to devising the various scenarios of event exchanges among the objects. Perhaps the best instrument to aid the thinking process at this stage is the UML sequence diagram, such as the diagram depicted in Figure 1.4. This particular sequence diagram shows the most common event exchange scenarios in the “Fly ‘n’ Shoot” game (the primary use cases, if you will). The explanation section immediately following the diagram illuminates the interesting points.

Figure 1.4. The sequence diagram of the “Fly ‘n’ Shoot” game.

Even though the sequence diagram in Figure 1.4 shows merely some selected scenarios of the “Fly ‘n’ Shoot” game, I hope that the explanations give you a big picture of how the application works. More important, you should start getting the general idea about the thinking process that goes into designing an event-driven system with active objects and events.

I hope that the analysis of the sequence diagram in Figure 1.4 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 1.4(12)) compared to the time when it is not (Figure 1.4(3)).

The best-known mechanism for 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. Chapter 2 introduces 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.

The Missile Active Object

I start with the Missile state machine shown in Figure 1.5 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 1.5 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 1.5(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 1.5. 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 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, a 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 1.4). 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.

The Ship Active Object

The state machine of the Ship active object is shown in Figure 1.6. 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.

Figure 1.6. Ship state machine diagram.

One of the main responsibilities of the Ship active object is to maintain the current position of the Ship. On the original EV-LM3S811 board, this position is determined by the potentiometer wheel (see Figure 1.2). The PLAYER_SHIP_MOVE(x, y) event is generated whenever the wheel position changes, as shown in the sequence diagram (Figure 1.4). 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 important, would represent multiple points of maintenance both in the diagram and the code. Such repetitions go against the DRY (Don't Repeat Yourself) principle, which is vital for flexible and maintainable code [Hunt+ 00].

Hierarchical state nesting remedies the problem. Consider the state “active” that surrounds all other states in Figure 1.6. 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 prescribe 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 1.6, 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 the story—the PLAYER_SHIP_MOVE(x, y) event would be silently discarded. However, the state machine in Figure 1.6 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.

• (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 1.2).

• (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 1.5(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.

The Tunnel Active Object

The Tunnel active object has the most complex state machine, which is shown in Figure 1.7. Unlike the previous state diagrams, the diagram in Figure 1.7 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.

Figure 1.7. Tunnel state machine diagram.

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

• (1) An initial transition can target a substate at any level of state hierarchy, not necessarily just the next-lower level. Here the topmost 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 the 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 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.

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.

As shown in Figure 1.8, 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. 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 in its specific way. For example, Mine type 2 checks for collision with the Missile differently than with the Ship, whereas 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.

Figure 1.8. The Table active object manages two types of Mines.

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 1.9 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 1.9. 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 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 “used” 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 1.9(4)). The mine_id parameter of the event becomes the index into the mines[] array. 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).

The key events in the “Fly ‘n’ Shoot” game have been identified in the sequence diagram in Figure 1.4. Other events have been invented during the state machine design stage. In any case, you must have noticed that events consist really of two parts. The part of the event called the signal conveys the type of the occurrence (what happened). For example, the TIME_TICK signal conveys the arrival of a time tick, whereas the PLAYER_SHIP_MOVE signal conveys that the player wants to move the Ship. An event can also contain additional quantitative information about the occurrence in form of event parameters. For example, the PLAYER_SHIP_MOVE signal is accompanied by the parameters (x, y) that contain the quantitative information as to where exactly to move the Ship.

In QP, events are represented as instances of the QEvent structure provided by the framework. Specifically, the QEvent structure contains the member sig, to represent the signal of that event. Event parameters are added in the process of inheritance, as described in the sidebar “Single Inheritance in C.”

Because events are explicitly shared among most of the application components, it is convenient to declare them in the separate header file game.h shown in Listing 1.2. The explanation section immediately following the listing illuminates the interesting points.

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 1.6 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 Stellaris version of the “Fly ‘n’ Shoot” game. I break the explanation of this file into three steps.

As you saw in Listing 1.1(21), the main() function eventually gives control to the event-driven framework by calling QF_run() to execute the application. In this section, I briefly explain how QF allocates the CPU cycles to various tasks within the system and what options you have in choosing the execution model.

The “Fly ‘n’ Shoot” game behaves intentionally almost identically to the Quickstart application provided in source code with the Luminary Micro Stellaris EV-LM3S811 evaluation kit [Luminary 06]. In this section I'd like to compare the traditional approach represented by the Quickstart application with the state machine-based solution exemplified in the “Fly ‘n’ Shoot” game.

Figure 1.11(A) shows schematically the flowchart of the Quickstart application; Figure 1.11(B) shows the flowchart of the “Fly ‘n’ Shoot” game running on top of the cooperative “vanilla” kernel. At the highest level, the flowcharts are similar in that they both consist of an endless loop surrounding the entire processing. But the internal structure of the main loop is very different in the two cases. As indicated by the heavy lines in the flowcharts, the Quickstart application spends most of its time in the tight “event loops” designed to busy-wait for certain events, such as the screen update event. In contrast, the “Fly ‘n’ Shoot” application spends most of its time right in the main loop. The QP framework dispatches any available event to the appropriate state machine that handles the event and returns quickly to the main loop without ever waiting for events internally.

Figure 1.11. The control flow in the Quickstart application (A) and the “Fly ‘n’ Shoot” example (B). The heavy lines represent the most frequently exercised paths through the code.

The Quickstart application has much more convoluted flow of control than the “Fly ‘n’ Shoot” example because the traditional solution is very specific to the problem at hand whereas the state-machine approach is generic. The Quickstart application is structured very much like a traditional sequential program that tries to stay in control from the beginning to the end. From time to time, the application pauses to busy-wait for a certain event, whereas the code is generally not ready to handle any other events than the one it chooses to wait for. All this contributes to the inflexibility of the design. Adding new events is hard because the whole structure of the intervening code is designed to accept only very specific events and would need to change dramatically to accommodate new events. Also, while busy-waiting for the screen update event (equivalent to the TIME_TICK event in “Fly ‘n’ Shoot” example), the application is really not responsive to any other events. The task-level response is hard to characterize and generally depends on the event type. The timing established by the hard-coded waiting for the existing events might not work well for new events.

In contrast, the “Fly ‘n’ Shoot” application has a much simpler control flow that is purely event-driven and completely generic (see Figure 1.11(B)). The context of each active object component is represented as the current state of a state machine, rather than as a certain place in the code. That way, hanging in tight “event loops” around certain locations in the code corresponding to the current context is unnecessary. Instead, a state machine remembers the context very efficiently as a small data item (the state-variable; see Chapter 3). After processing of each event, the state machine can return to the common event loop that is designed generically to handle all kinds of events. For every event, the state machine naturally picks up where it left off and moves on to the next state, if necessary. Adding new events is easy in this design because a state machine is responsive to any event at any time. An event-driven, state-machine-based application is incomparably more flexible and resilient to change than the traditional one.

If you've never done event-driven programming before, the internal structure of the “Fly ‘n’ Shoot” game must certainly represent a big paradigm shift for you. In fact, I hope that it actually blows your mind, because otherwise I'm not sure that you really appreciate the complete reversal of control of an event-driven program compared to the traditional sequential code. This reversal of control, known as the Hollywood Principle (don't call us, we'll call you), baffles many newcomers, who often find it “mind-boggling,” “backward,” or “weird.”

The “Fly ‘n’ Shoot” game is by no means a big application, but at the same time it is definitely not trivial, either. You shouldn't worry if you don't fully understand it at the first reading. In the upcoming chapters, I will provide a closer look at the state machine design and coding techniques. In Part II, I discuss the features, implementation, and porting of the QF real-time framework.

My main goal in this chapter was just to introduce you to the event-driven paradigm and the modern state machines to convince you that these powerful concepts aren't particularly hard to implement directly in C or C++. Indeed, I hope you noticed that the actual coding of the nontrivial “Fly ‘n’ Shoot” game wasn't a big deal at all. All you needed to know was just a few cookie-cutter rules for coding state machines and familiarity with a few framework services for implementing the actions.

Wile the coding turned out to be essentially a nonissue; the bulk of the programming effort was spent on the design of the application. At this point, I hope that the “Fly ‘n’ Shoot” example helps you get the big picture of how the method works. Under the event-driven model, the program structure is divided into two rough groups: events and state machine components (active objects). An event represents the occurrence of something interesting. A state machine codifies the reactions to the events, which generally depend both on the nature of the event and on the state of the component. While events often originate from the outside of your program, such as time ticks or button presses in the “Fly ‘n’ Shoot” game, events can also be generated internally by the program itself. For example, the Mine components generate notification events when they detect a collision with the Missile or the Ship.

An event-driven program executes by constantly checking for possible events and, when an event is detected, dispatching the event to the appropriate state machine component (see Figure 1.11(B)). For this approach to work, the events must be checked continuously and frequently. This implies that the state machines must execute quickly so that the program can get back to checking for events. To meet this requirement, a state machine cannot go into a condition where it is busy-waiting for some long or indeterminate time. The most common example of this would be a while loop inside a state-handler function, where the condition for termination was not under program control—for instance, the button press. This kind of program structure, an indefinite loop, is referred to as “blocking” code,⁶ In the context of a multitasking operating system the “blocking” code corresponds to waiting on a semaphore, event flag, message mailbox, or other such operating system primitive. and you saw examples of it in the Quickstart application (see Figure 1.11(A)). For the event-driven programming model to work, you must only write “nonblocking” code [Carryer 05].

Finally, the “Fly ‘n’ Shoot” example demonstrates the use of the event-driven platform called QP, which is a collection of components for building event-driven applications. The QF real-time framework component embodies the Hollywood Principle by calling the application code, not the other way around. Such an arrangement is very typical for event-driven systems and application frameworks similar to QF are at the heart of virtually every design automation tool on the market today.

The QF framework operates in the “Fly ‘n’ Shoot” game in its simplest configuration, in which QF runs on a bare-metal target processor without any operating system. QF can also be configured to work with the build-in preemptive real-time kernel called QK (see Chapter 10) or can be easily ported to almost any traditional OS or RTOS (see Chapter 8). In fact, you can view the QF framework itself as a high-level, event-driven, real-time operating system.