Simplifying Interactive Behavior Implementation

I once worked on a project where we were tasked to create 100+ tutorials each with different behavior.

Implementing one behavior by manually implementing a state machine presented no problem, but some of the behaviors were non-trivial, there were many of them, and they were all slightly different.

Unfortunately, they kept changing too. Changes small and large were pouring into the project and these manually constructed state machines were difficult to maintain, extend and modify.

Sequential Execution

Most of the programs interactions could be described in question / answer format. For instance, imagine a program that worked like this:

The right side of the scale is lower than the left.

What would you like to do?
(1) Add a 10g piece to the left side of the scale.
(2) Add a 5g piece to the left side of the scale.

?> 1

The left side of the scale is lower than the right.

What would you like to do?
(1) Add a 10g piece to the left side of the scale.
(2) Add a 5g piece to the left side of the scale.
(3) Remove a 10g piece from the left side of the scale.

?> 3

The right scale of the scale is lower than the left.

What would you like to do?
(1) Add a 10g piece to the left side of the scale.
(2) Add a 5g piece to the left side of the scale.

?> 2

Great! The scale is balanced. Now look at the scale and enter the number of grams on the left side of the balance.

?> 5

Good job!

At first glance, this is a ridiculously easy program to write...but you can’t simply write the logic in the most straight-forward way.

We’re not displaying text. We’re playing audio, we’re displaying animations and if the user doesn’t answer after a certain timeout period, we might give them a hint.

There are a lot of things going on and the program can’t simply block until a response comes from the user.

We know what we want to do after each action (it is very easy to define) but practically everything we do has to occur asynchronously because the program can’t just “wait” for a response.

If you’re familiar with jQuery or Node.js, you’ll might see some parallels.

Co-routines

Depending on your language/platform, you might already have a solution available. For instance, C# recently added very rich support for asynchronous programming and Ruby has native support in the form of fibers.

You can also get good results on most platforms by using threads, where execution can be suspended on the thread without impacting the execution of the rest of the program.

Threads can be pretty heavy-weight though and what we really want are Coroutines. These are bits of code that run normally but can give up control and resume work at some later point. This means you can do something like this:

displayPrompt("Choose A or B:")

startAnimation("A_or_B_Animation")
response = getResponseFromUser(timeout: "Choose A or B!")

while(true)
  if response == "A"
    doActionX()
    break
  else
   doActionY()
   break
  end
end

stopAnimation("A_or_B_Animation")

doFinalAction()

This is much easier to deal with than code that more explicitly constructs a state machine (which might look more like this):

switch(state)
  case START:
    displayPrompt("Choose A or B:")
    startAnimation("A_or_B_Animation")
    state = WAIT_FOR_INPUT
  case WAIT_FOR_INPUT:
    input = getInput()
    if input == "A"
      actionX.start()
      state = WAIT_FOR_ACTION_X
    else if input == "B"
      actionY.start()
      state = WAIT_FOR_ACTION_Y
    end
  case WAIT_FOR_ACTION_X:
    if actionX.finished() state = FINISH
  case WAIT_FOR_ACTION_Y:
    if actionY.finished() state = FINISH
  case FINISH:
    stopAnimation("A_or_B_Animation")
    finish.start()
    state = WAIT_FOR_FINISH
  case WAIT_FOR_FINISH:
    if finish.finished() exit()
end

If you’re not sure whether or not your platform or language natively supports co-routines, check it out.

Using Flash (or JavaScript)?

ActionScript and JavaScript are very similar and they share a few of weaknesses in this context.

  • They lack native support for coroutines.
  • They lack support language features that would allow you to implement co-routines yourself (e.g., iterators in C# or generators Python).
  • There is no support for threads on Flash or in JavaScript.

Before we go any further, let me say this: consider all of your options. The next step is pretty crazy and it might not be the right choice for your project.

In our case it made sense but I suspect that in most cases it will not. I would certainly hesitate before making a choice like this again.

Our maintenance problem was enough to keep me looking and eventually I took a fairly drastic step and switched languages. It turns out there is a language that compiles to Flash-compatible byte code and has a very extensive meta-programming support: Haxe.

Rewriting Expressions

So, in an exhausting, sleepless weekend I used Haxe’s macro feature to add co-routines to the language. I won’t go into a lot of technical detail here. The idea isn’t specific to Haxe and should be portable to any language that allows you to inspect & transform expressions.

A colleague had already put a system in place for constructing a state machine by defining individual nodes. For instance, if you needed to do task A, then task B, then task C, you could do something like this:

machine = new Sequence(new TaskA(), new TaskB(), new TaskC())

machine.start()

Likewise, if the state transition depended on run-time state, you could construct an “if” node like so:

input = new Input("A", "B")

branch = new If(function(){ return input.choice = "A" })
  .ifTrue(new TaskA())
  .ifFalse(new TaskB());

machine = new Sequence(input, branch)

machine.start()

Again, though, we want to write something closer to this (assuming “return” halts execution until the specified co-routine has completed):

var input = new GetUserInput("A", "B")
return input;

if (input.choice == "A") {
  return new TaskA()
} else {
  return new TaskB()
}

So, how do we get there? By examining the expression and using it to produce a new expression that does what we want.

In the above example, we basically have only three operations we want to transform: if statements and return statements.

The first thing we do is generate a sequence node, because (in imperative languages at least) basically everything we look at is going to be a sequence of commands to perform.

var auto_generated_sequence1 = new Sequence()

The first line is a variable assignment and in my processor. We need to split this into a variable declaration and an assignment. The assignment has to be split off so that it can be put into the sequence and the code associated with it executed at the proper time.

var input;
auto_generated_sequence1.add(new Functor(function() {
   input = new GetUserInput("A", "B")
});

The next line is a return statement. Normally, this would exit the function which isn’t what we want to happen. We’re going to subvert it to make “return” in this context mean “yield until the specified co-routine has finished”.

auto_generated_sequence1.add(input)

Now we need to construct the if. We can examine the if and find three parts: the condition, the “then” branch and the “else” branch. First, let’s construct sequences to represent each of the branches.

var auto_generated_sequence2 = new Sequence()
auto_generated_sequence2.add(new TaskA())

var auto_generated_sequence3 = new Sequence()
auto_generated_sequence3.add(new TaskB())

Now, we’ll create the actual if and add it to the sequence:

var auto_generated_if1 = new If(function() {
  return input.choice == "A";
});

auto_generated_if1.then(auto_generated_sequence2)
auto_generated_if1.else(auto_generated_sequence3)

auto_generated_sequence1.add(auto_generated_if1)

All together, we’ve replaced the original code with this:

var auto_generated_sequence1 = new Sequence()

var input;
auto_generated_sequence1.add(new Functor(function() {
  input = new GetUserInput("A", "B")
});

auto_generated_sequence1.add(input)

var auto_generated_sequence2 = new Sequence()
auto_generated_sequence2.add(new TaskA())

var auto_generated_sequence3 = new Sequence()
auto_generated_sequence3.add(new TaskB())

var auto_generated_if1 = new If(function() {
  return input.choice == "A";
});

auto_generated_if1.then(auto_generated_sequence2)
auto_generated_if1.else(auto_generated_sequence3)

auto_generated_sequence1.add(auto_generated_if1)

return auto_generated_sequence1;

Well, That Was Ugly

Luckily, no human should ever see the output. This is all about simplifying things for the programmers. It’s not very fast (but it doesn’t need to be) and it is very complicated under the hood (which is unfortunate) but on a daily basis the programmer doesn’t have to look into it.

Post-mortem

In the end, I believe the system paid for its complexity. The co-routines were coupled with a few other ideas we’d been toying with for simplifying development and my own efficiency sky rocketed so that I was able to complete the initial programming for a single tutorial every day. For the first time, the programming team was able to actually get work done on tutorials before the artists got to them.