Interactive Simulation Newsletter

WELCOME!

We begin this month's newsletter with advice regarding using questions as part of a prototyping process for simulations.

However, this month's newsletter is focused on the technical subject of an alternative approach to implementing state machines. In particular, it focuses on the approach of Miro Samek, author of "Practical Statecharts in C/C++". For those of you who don't know about this book and of his website, www.quantum-leaps.com, we have been directing people toward his work ever since his book came out in the middle of last year. It really is excellent. About 6 months ago, Miro ported his code to ActionScript, and we've been waiting for the right time to release it to the community. Today is the day! Newsletter subscribers can download the code both in Flash MX and in Flash MX 2004.

In the course of discussing state machines with the community, we've had the pleasure to interact with Ralf Bokelberg ('bokel', to the Flash community), www.helpQLODhelp.com. Ralf was also intrigued by Miro's approach, and took the initiative to write an ActionScript (Flash MX) variant. Ralf's code includes examples to verify email syntax and a menu. We think that Ralf strikes a nice balance between the classic "class" approach to state engines, and Miro's approach of developing a lightweight architecture (as compared with our more fully-featured, but more complex implementation, FStEng).

Enter your email address here to receive the accompanying source code and automatic notification on future newsletter releases.

We will discuss this variant in this newsletter following the article on Miro's code. Thanks Ralf for sharing your code with all of us!

As always, your comments and feedback are welcome.

At a recent conference, we were speaking with Will Thalheimer of work-learning.com and sharing our strategies for designing simulations. Some people are surprised how much in common we have, since Will focuses on teaching how to write simulation-like questions to replace expensive multimedia. Doesn't Will's approach direct potential clients away from our business of creating simulations that use a lot of interaction?

The answer is "no." Our approach, like Will's, focuses on performance impact, not simply applying technology. We are very much aligned with Will's approach of questioning the need for extensive multimedia if the problem situation can be solved without such technology. In fact, when we develop simulation projects, during the initial requirements gathering and into the storyboarding phase, we even develop a set of "simulation-like" questions that help us to determine whether the performance problem or sub-problem can be completely addressed by expressing the task as a question (or series of related questions), rather than having to use more involved interactive elements. Reading about Will's research on his site can help you to see the essential elements of effective questions as you use this technique to prototype, storyboard, or otherwise gather requirements and plan your simulation projects.

The result will be a series of questions, potentially with branching (i.e., a different series of questions depending on the responses to prior questions). As you see them breakdown into details or require operational skill demonstration, you can determine where more involved interaction (and the extent of its behavior) needs to be inserted. The questions are really designed to evoke assessment-related queries, so in a sense you are abstracting the physical movements (to replace them with real interaction with simulators or other elements), yet still focusing on the outcome, i.e., the successful matching of the user's ability to recall or retrieve infomation or skills to perform a task in the appropriately-triggered context.

To find out how to write simulation-like questions, we recommend you visit Will's site and read his papers, starting with his "Simulation-like questions: The basics of how and why to write them" http://www.work-learning.com/sim_questions_basics_intro.htm.

As many of those we've talked with know, while writing our book we became aware of Miro Samek's work on statecharts for programming embedded systems. He had been writing articles for a few years prior to this time, but his book, Practical Statecharts in C/C++, was about to come out in July, 2002.

He impressed us with his ability to distill the essence of statecharts in productive and precise terms. At the same time, he brought valuable insights based on his experiences and that of other groups working over the past 15 years of statechart development, from Harel's original paper through specifications in UML statecharts. We strongly suggest those interested in understanding the meaning of statecharts to buy his book and study his examples. Here is an excerpt from Jonathan's review of his book on Amazon:

...Since I am not from the embedded system world, I was a bit apprehensive about approaching this book. While I can see that author Miro Samek has a directed target for his audience, I strongly feel that this book is a "must read" for technical developers in all areas who want to improve their program design abilities or developers who want to understand the philosophy, use, and implementation of statecharts intimately.

As the title indicates, this book brings the topic of statecharts from the realm of expensive design tools to the PRACTICAL realm, illustrating its points with full examples and extensive commentary.

Essentially Samek postulates that the slow adoption by developers of best practices by statechart design is due to lack of understanding of the fundamental nature of statecharts and how it is perceived as requiring expensive tools to use well. Samek insightfully discusses how statecharts as a best practice embody "behavioral inheritance" as a fundamental design concept that stands as a peer alongside the conventional pillars of object-oriented programming, namely inheritance, encapsulation, and polymorphism....

It's obvious from his book and his web site (www.quantum-leaps.com) that Miro, too, wants to encourage developers to recognize the value of programming in a state-centric approach. To that end, we talked with Miro about the relationship of his work to what we were doing. There was a natural fit, of course. Fundamentally, Miro argues that designing/programming with statecharts is as natural as designing/programming with object-oriented practices, once the developer understands the motivation and organizational clarity gained by organizing behavior by context (state approach).

There isn't the time or space here to explain the intracacies of his approach, so we will concentrate on some basic differences with what we have produced, and then get on to the code.

The two state engines included in the distributed code were ported to ActionScript by Miro Samek, and are

• QFsm: A finite state machine (FSM) engine
• QHsm: A hierarchical state machine (HSM) engine.

If you look at Miro's code, you will see that the ActionScript version is very close to the C version. You can find his code for languages other than ActionScript at his code repository. Our discussion will focus on the QHsm engine.

One Critical Difference: States as Classes vs. Methods

The approach that we take in our book and in updated versions of the state engine can be classified as an approach that uses a class to represent a state. We also have classes to represent transitions and actions. This is similar to how others have implemented state engines as well. Each state has an event handler to process events when that state is active.

The approach of defining a formal state class, while perfectly fine for high-level software domains, suffers from two problems:

1. It is more memory intensive, which may be problematic in domains such as embedded systems in which memory and CPU cycles are at a premium;
2. It is more difficult to reuse and adapt behaviors of sub-systems, since they would have to be duplicated in memory potentially at considerable expense in an embedded system.

Miro's revelation to address these problems took form as a lightweight hierarchical state architecture. In spite of being lightweight, this architecture can handle all of the fundamental aspects of statecharts, and can be extended straightforwardly to handle some of the less fundamental aspects as well, such as state concurrency, history, and event queueing (read his book for more info on how to implement these--we show how to implement the history mechanism in the watch example included in the code).

He defined a basic "hierarchical state machine" class, which he calls QHsm. The idea is that specific state machines subclass the QHsm class, to inherit state machine behavior such as dispatching events, handling transitions, etc. In his architecture, the role of states is to handle events appropriate for each context. Therefore, Miro's states are simply methods of the sub-class. When the system receives an event, it's dispatch routine determines the active state (most specific), and invokes the state method to handle the event. If the state does not handle that event, it passes the event up to its parent state, which gets a shot at handling the event, and so on. Entry and exit actions are just another type of event. Here is an example of what a sub-class would look like to define some state1:

   1:  class MyNetwork extends QHsm {

   2:     ...

   3:     function myState1 (e:QEvent):Function {

   4:        switch (e.sig) {

   5:           case ENTRY_SIG: trace("Entry actions here!"); return null;

   6:           case EXIT_SIG: trace("Exit actions"); return null;

   7:           case OTHER_SIG: trace("OTHER event"); Q_TRAN(myState2); return null;

   8:        }

   9:        // If event is not handled, give to parent state to handle

  10:        return myParentStateMethod;

  11:     }

  12:     ...

  13:  }

The reason this is more efficient than the state class approach is that the state network is defined purely in terms of functions, and hence less overhead than classes and instances (see sidebar).

The really amazing part has to do with item #2 above. Using this methodology, you can actually inherit sub-system behavior just by sub-classing a define state network, and selectively override behaviors to modify system behavior, all without copying instances. For example, suppose that we wanted to customize the behavior of myState1 in MyNetwork (in the code sample above). Rather than copying all the state objects of MyNetwork, we simply would do

class MyNetworkCustom extends MyNetwork {
   ...
   // override the behavior of myState1 from that of MyNetwork
   function myState1Method (e:QEvent):Function {
      ...
   }
   ...
}

Imagine that you were using statecharts to model the decision-making process of each character in a game. You might have one statechart that models common behavior, and then each character can inherit those behaviors, as well as override aspects relevant for specific character types or personalities. If there were only one or two characters, then copying the statecharts as objects would not be bad, but imagine you have 1000 characters!

This approach is efficient in terms of storage as well as performance. Critics of statecharts have used the argument that the state engine framework is heavy and impacts performance for critical tasks such as those involved on the embedded systems. With Miro's approach, there is only a small performance impact, quite reasonable considering the overwhelming benefit from the organizational clarity provided by the statechart concept.

The Essence of How It Works

At the heart of the QHsm class are the workhorse routines, dispatch, responsible for routing an event to the proper context (the currently active state), and Q_TRAN, the method that handles bookkeeping when transitions are taken (Q_TRAN is not reproduced here because it is quite long).

class QHsm {
  private var __state:Function;

   ...
   function dispatch (e:QEvent) {
      __source = __state;
      do {
        __source = __source(e);
      } while (__source != null);
   }
   ...
}

The __state variable holds the current state (which is a method). You can see in the dispatch routine how the processor routes the event first to the most specific state, and if the state does not handle it (returns non null), then the processor checks to see if the parent state wants to handle it, and so on (the protocol for a state is to return null if it handled the event, and otherwise return its parent state--see the example MyState1 in the MyNetwork code above). This is how sub-states specialize the behavior of parent states--if the sub-state can handle the event, it overrides the behavior of any ancestor state that, if not for the specialization, would have handled it.

An Example Network

Try exercing the QHsm in the following example (this is QHsmTest in this month's download).

In this example, you can interactively send events to the state engine to see the sequence of actions that result. Pressing a button with a letter sends that event to the active state. In the text window, you will see the trace output as entry, exit, and init (default start state events) are handled.

The Bottom Line

To some, it may seem like we're moving in the direction of greater complexity, rather than less. Miro's approach requires the developer to take more responsibility for properly structuring event handlers, but it comes with the great benefit of less overhead--something particularly important in embedded system domains. By adopting this framework, you can also port your infrastructure virtually immediately to C, C++, C#, and other languages. That can be a great advantage! Suppose you get your product design team on board with this approach--you can then develop simulators in product design that can easily be adapted for other purposes throughout the product life cycle (marketing, training, etc.). That's quite a bang for your buck!

It may seem to some that Miro's approach is too low-level--why not go with the programs that automatically generate code? For this, we refer to the age old saying in Computer Science, "GIGO: Garbage in, Garbage Out.". While we're being somewhat sarcastic, the bottom line is that if one does not understand the methodology well, then a tool to automate the code generation is not going to magically produce good designs or applications of the methodology.

We feel that tools can empower developers, but not to the point of replacing understanding--that is key. When one develops a good grasp of the methodology, something developed through project experience, then one recognizes how natural the principles are, similar to the way programmers are now almost instinctively thinking in terms of the object-oriented design model. Tools can make the process much more efficient, but they don't absolve a real understanding for what you need to accomplish--GIGO!

This has been a quick introduction to some salient points about Miro's implementation. Please post questions or comments to the discussion board, or if you'd like us to elaborate, let us know!

BACK TO TOP

Several months ago, Ralf Bokelberg (www.helpQLODhelp.com) contacted us about state machines, and was intrigued after seeing our book materials on FlashSim, and Miro Samek's book materials on quantum-leaps.com. He recognized that our engine was, in several respects, heavier and more complex than the approach by Miro, and so he took a sort of middle ground approach. This became the result he sent us, and what is available for download today (Flash MX version). Thank you Ralf for sending the code to us and letting us distribute it to the community!

Essentially, Ralf's approach, like Miro's, cuts out the hierarchical concurrent states and histories, as well as the objects for transitions, actions, and activities. All of these can be modeled by extending Miro's approach, though the approach both Miro and Ralf take makes a fundamental difference when executing transition actions that even Miro recognizes as departing from the UML specification (though Miro does defend his position with a good argument). Implementing concurrent states is much more involved, but nonetheless very doable.

Unlike Miro, Ralf sticks with the object-based representation of classes, rather than Miro's method-based approach. This is obviously means that Ralf's approach cannot be used like Miro's to sub-class state machines, but the tradeoff allows what we feel is a more developer-intuitive approach (from object-oriented perspective) for handling events. For example, in Ralf's approach (like our FStEng v1.5 approach, which we discuss extensively on our discussion boards), you handle events by defining methods of the state, for example, state1.onButtonChar = function () { ... }, to define the "onButtonChar" event handler for state1.

Ralf's implementation follows Miro's in that events are dispatched to the most specific active sub-state first, as the dispatch code below shows.

   1:  o.dispatch = function(event){

   2:      traceOut("dispatch " + arguments + ":" + this.current.name);

   3:      var state = this.current;

   4:      //

   5:      while(state[event] == undefined && (state = state.parent)){

   6:          traceOut("Unknown event, passing up to parent: " + event + ":" + state.name);

   7:      };

   8:      state[event].apply(this, arguments);

   9:  }

In Miro's approach, state methods return null if they have handled the event, and non-null (the parent state) if they have not. You can see that on line 5, however, Ralf looks on the state object for an event handler, and, if found, lets that state handle the event. This is a good system for most events, but it doesn't give the flexibility to define a class of events and let the handler selectively filter particular messages based on other system conditions. One might argue that if other conditions are relevant, then you should make a different event or different state, so there are reasonable claims for each position.

Another difference between Ralf and Miro's approach has to do with processing transitions. Ralf follows a similar approach to our implementation in that the developer gives parameters for the path to the target state. In Ralf's approach, the developer specifies the least common ancestor, and the target state:

   1:  //

   2:  o.changeState = function(lca, targetState){

   3:      traceOut("changeState " + [this.current.name, lca.name, targetState.name]);

   4:      this.goUpToCommonAncestor(this.current, lca);

   5:      this.goDownToTarget(lca, targetState);

   6:  }

Unlike our approach, however, there are inefficiences in this and Miro's ActionScript (but not C/C++) approach because the path from the least common ancestor (lca) has to be constructed each time. This is due to their approaches not having an explicit representation of a transition, which makes an individual entity that can store specific path information.

Because Ralf's is so simple to understand, we really like using it, even though it requires a bit more carefulness on the part of the developer (similar to FStEng v1, but with an easier event handling scheme). Not to mention that Ralf prepared two nice examples of his QHsm for us, an email address syntax checker, and a menu system.

Ralf's Examples

As a demonstration of Ralf's QHsm implementation, he built the following code that embodies a context-sensitive grammer to validate email addresses syntactically.

The program goes character-by-character through the given email address and dispatches events to the state machine based on the type of the character:

   1:  var ch = this.email.charAt(i);

   2:  if(ch == "."){

   3:      my_hsm.dispatch("onDot");

   4:  } else if( ch == "@") {    

   5:      my_hsm.dispatch("onAt");

   6:  } else if(ch.isEmailCharacter()){

   7:      my_hsm.dispatch("onChar", ch);

His second example is a simple hierarchical menu that remembers the last item chosen.

Which Approach is Best to Use?

Our intention of publishing the different engines is to give you the flexibility to see which approach makes the most sense to you. Our state engine out-of-the-box has more functionality than Miro's or Ralf's, but certainly that does not mean that their approaches are necessarily more limited. We really like the concept behind Miro's approach that allows one to subclass state machines. This can have significant savings when you need to replicate base functionality. We like Ralf's approach for its simplicity and also for his API regarding states. While cosmetic, we think it's more natural to define methods of states to add states, rather than our engine's API that hooks the states together through state managers. In our FStEng v2, due out in a few months, we use an API like what Ralf has started.

In the end, we find that we use Ralf's approach for small to medium projects, and then for larger projects, we choose between our engine and Miro's, depending on specific requirements (such as the relevance of sub-classing, or potential need to target languages other than ActionScript). You be the judge--let us know on the discussion boards what you think!

We constantly run into all different people around the country and world who have interesting simulation projects they have in mind or have prepared. We want to encourage you simulator programmers, instructional designers, gamers, managers, and other developers to share your stories and best practices with the rest of us. We invite you to lead or join the discussion on our FlashSim discussion board:

http://FlashSim.infopop.cc/

We also will monitor the discussions for particular topics that might make good newsletter information, so go forth and post!

If you have suggestion for topics you'd like to see in the newsletter, or links to events or interesting Flash pieces you've made, please email us at newsletter@FlashSim.com.

If you'd prefer not to receive this newsletter, send us your name, your registered e-mail address, and the message: "Unsubscribe" to removeListener@FlashSim.com.

If you are receiving this newsletter from a friend and want to subscribe yourself, please email us a message with the subject "Subscribe" to addListener@FlashSim.com.