C++ State Machines

Avoid input parameters

Nystrom considers game programming and his example state machine is concerned with the animation and movement of the players character, a heroine. This is the interface for the heroines state:

class HeroineState
{
public:
  virtual void handleInput(Heroine& heroine, Input input) {}
  virtual void update(Heroine& heroine) {}
};

I propose the following change that handleInput returns a state instead of modifying a Heroine parameter.

class HeroineState
{
public:
  virtual HeroineState* handleInput(Input input) {}
  virtual void update(Heroine& heroine) {}
};

This has two advantages:

• handleInput can only rely on the inputs and not on the state of the Heroine. In Game Programming Patterns handleInput calls setGraphics. Such transition effects are better done in the update method and decoupled from the state transitions.
• No aliasing. In Nystroms version of HeroineState::handleInput the this pointer aliases with the current state in Heroine. Our static analysis does not like that.

To use the state machine, it must be attached to the actual Heroine class. For example as member called state_. In the Heroine class we can add entry and exit actions in a generic way.

class Heroine
{
public:
  virtual void handleInput(Input input)
  {
    auto next = state_->handleInput(input);
    if (next != state_) {
      state_->onExit(*this);
      next->onEntry(*this);
      state_ = next;
    }
  }
};

Nystrom already describes that entry/exit pattern but does not take the next step to remove the heroine parameter.

Of course, you can pass additional parameters to handleInput to explicitly allow state transitions based on additional inputs. You might even pass in the heroine object, but at least you can now make it const.

Transitions

The actually tricky part about state machines is the specification of the transitions. Here is an example: There are four input variables a, b, c, and d, each being true or false. There are three possible states x, y, and z. This means we have to specify for each state what other state to transition to for 16 possible inputs. Here is some code to describe that for one state, can you spot the bug?

if ((!a && !b) || (c && d)) {
    return X;
} else if (!a || (a && !b && d)) {
    return Y;
} else if (!c || b) {
    return Z;
} else {
    assert(FALSE);
};

The last else block is supposed to be unreachable, but it isn't. Can you figure it out?

The logic is hard to understand because the order is important. For example the state Y case is true if only a is true, but the first state X case already covers a lot of cases where a is true. So we would change the order of the checks, we would end up with different behavior. That is dangerous in long-living code or large teams.

It would not help if there were meaningful variable names instead of single letters. For example, you might have doorOpen or sigAccActive instead of a. These meaningful names might help to keep the code aligned with the requirements but that just shifts the problem: How do you find the bugs in the requirements?

What does help is a more visual representation of all possible transitions:

Well, the color helps as well. Now you see that the input a && !b && c && !d has no transition. Inspired by this representation, we could use the following code instead of an if-cascade. The 0 marks the uncovered input.

State[16] = {X, X, X, X,
             Y, Y, Y, X,
             Z, Y, 0, X,
             Z, Z, Z, X};
unsigned index = (a << 3) | (b << 2) | (c << 1) | d;
return State[index];

Is that better? Without titles for the columns and rows the code is not well readable. I guess that GUIs specialized on state machines might have a point here. Code generation allows for arbitrary views unrestricted by the serial nature of text. Text works great for version control though. So pick your poison.

I have no good conclusion here. The if-cascade still looks like the most intuitive way despite the fact that analysis is harder.

---

Discussion on Hacker News