Space Game: A std::variant-Based State Machine by Example

One of a powerful uses of std::variant is to implement State Machines. Some time ago I showed a simple example, but today we have something bigger. In today’s article by Nikolai Wuttke you’ll see how to leverage std::variant and build a space game!

This article is a guest post from Nikolai Wuttke

Nikolai Wuttke is a technical principal at Ableton, a Berlin-based music software company. In his free time, he likes to create metal guitar covers of video game soundtracks, play with his band, collect DOS-era computers, and stare at 16-bit assembly code.

Intro  

One of the new additions C++ 17 brought to the standard library is std::variant, an object which can hold values of different types, but only one type at a time. In type theory, this is called a sum type. It’s a very useful thing to have, and there are many use cases. For a general overview of std::variant and what it can do, have a look at Everything You Need to Know About std::variant from C++17 . In this post, I want to focus on one specific use case: Modelling state machines.

State machines have a wide variety of applications, from video games to managing HTTP connections. Whenever you are dealing with an inherently stateful problem, consider using a state machine - it requires you to be very explicit about all the states your system can be in, and all the possible ways to transition between these states. This, in my experience, often results in code that’s more maintainable and easier to understand compared to tracking state in a less structured way (e.g. using a number of boolean values etc.).

So what exactly is a state machine? There is a formal definition (finite state machine), but I’ll explain it by example. Let’s say we want to make a space combat game.

Game specification  

The player is in control of a spaceship, and has to fight another ship controlled by the computer. The enemy ship should behave as follows:

• When the player is in the center of the playing field, the enemy flies around the player in a circle.
• When the player is outside the center, the enemy stays in the center.
• If the enemy has been in the center for a certain amount of time, it should shortly fly out of the center and back in, to make it harder for the player to hit the enemy.

While this is happening, the enemy is also shooting at the player.
Furthermore, we want the enemy to smoothly transition between being in the center and circling the player.

Thus, we have four distinct states the enemy can be in at any given time:

1. Circling around the player
2. Flying into the center
3. Staying in the center
4. Flying out of the center

If we get to state 4, once we have reached the outer edge of the playing field, we check if the player is still outside the center. Depending on that, we either switch to state 1 (to start circling the player again) or state 2 (to go back into the center).

To express this as a state machine, we draw an ellipse for each state, and lines to indicate possible state transitions, resulting in the following diagram:

Now, pictures are nice, but we ultimately need to write code in order to make our game. How can we turn this state machine specification into a working implementation?

Implementing the enemy ship’s state machine  

First, we need to keep track of the enemy’s current state. We could use an enum to achieve this:

enum class EnemyState {
  Circling,
  FlyToCenter,
  ShootingFromCenter,
  FlyOut
};

And if that was the only state we had to keep track of, this would be a great solution. But unless we want our game to be a text adventure, there’s more we need:

• We want the enemy to fire shots at the player at a specific rate, so we need to keep track of how much time has passed since the last shot was fired.
• We want the enemy to fly out of the center after some time has elapsed, so we also need to know how long it has been in the center.
• To circle around the player, we make the enemy fly towards the 4 corners of the playing field, one by one. So we need to know which corner we are currently approaching, in order to check if we have reached it yet.

Expressed in code, that gives us 3 additional state variables:

double timeSinceLastShot;
double timeSpentInCenter;

// Assuming we have an array with all corner positions
int targetCornerIndex;

Now, we could add these next to a variable of the enum type we declared above, and we would have all the state we need. But there is one problem: All of these variables are only valid in specific states, as shown in the table below:

You might ask yourself: “What’s the big deal, I know when to use which variable and I’ll be careful not to use the wrong one at the wrong time.” And you may be right for a simple example like this, but imagine a much more complicated scenario, with many more states, variables, and possible transitions. At some point, it’s going to become tricky to make sure that all variables are only used when they are actually valid, that we reset variables correctly when transitioning between states, etc. Sure, it’s not impossible to get this right, but at what cost in terms of hours spent in front of the debugger? In the end, we are using modern C++ so that we can leverage its features to make our lives easier, right?

And that’s where std::variant comes in: By encoding the various states of our state machine as types, we can have exactly the variables we need for a certain state as members of the type representing that state. If we then combine all these types into a variant, we have also encoded the state machine’s current state thanks to the variant knowing which alternative it currently holds. Let’s see how this looks in code:

struct Circling
{
  explicit Circling(const int startIndex)
    : mNextCirclePosIndex(startIndex)
  {
  }

  double mTimeSinceLastShot = 0.0;
  int mNextCirclePosIndex = 0;
};


struct FlyToCenter
{
};


struct ShootingFromCenter
{
  double mTimeSinceLastShot = 0.0;
  double mTimeSpentInCenter = 0;
};


struct FlyOut
{
  explicit FlyOut(const int cornerIndex)
    : mTargetCornerIndex(cornerIndex)
  {
  }

  int mTargetCornerIndex;
};

using State = std::variant<
  Circling,
  FlyToCenter,
  ShootingFromCenter,
  FlyOut>;

Doing things this way nicely solves our issues with the enum-based approach:

• It’s impossible to access the variables for any state except the current one, since we only include what’s needed in each struct.
• Just by assigning a new value to the variant, we can switch to a new state, but we also ensure that all variables have proper values thanks to each struct’s constructor. There is no need to manually reset variables on state transitions.
• Similarly, if a certain state requires some of its variables to be set to specific values upon entering that state, we can enforce that by not providing a default constructor for the corresponding struct.

The key takeaway is that we’ve now leveraged C++’s type system to make invalid states impossible to represent in our code. This means we have fewer things to think about, since the compiler will catch mistakes for us, and can focus on the really important part: Writing the actual logic. Only one question remains: How do we implement said logic based on a variant?

For this, The overload Pattern comes in handy. It allows us to write a lambda as a handler for each of our states, almost like pattern matching - a nice language feature which already exists in various other languages like Scala or Rust, and is a core building block in most functional languages (e.g. Haskell). As of today, we can only emulate pattern matching in C++ using libraries, but there are already proposals on the way to add this as a native language feature in the future (P1371, P1260). So, let’s have a look at implementing our enemy’s update function:

mState = match(mState,
    [=](Circling& state) -> State
    {
        // implement circling logic here

        if (playerInOuterZone()) {
          // Switch to next state if applicable
          return FlyToCenter();
        }

        return state;
    },

    [=](const FlyToCenter&) -> State
    {
        // implement flying to center logic here
    },

    [=](ShootingFromCenter& state) -> State
    {
        // implement shooting from center logic here
      },

    [=](const FlyOut& state) -> State
    {
    // implement flying out of center logic here
    }
  );

The function match is a little wrapper around the overloaded helper mentioned above, which doesn’t do much besides saving me a little bit of typing, and putting the variant argument first instead of last (see the source). Here’s the implementation:

template <typename Variant, typename... Matchers>
auto match(Variant&& variant, Matchers&&... matchers)
{
    return std::visit(
         detail::overloaded{std::forward<Matchers>(matchers)...},
         std::forward<Variant>(variant));
}

In order to implement our state machine, we do a match on our variant, and then have a little bit of logic for each state. This logic involves shooting, moving etc., as well as checking if we need to transition to a new state. If that’s the case, we return a state object representing the state we want to transition to, otherwise we return the current state. Whatever we returned from the chosen lambda is then returned by match and assigned to mState.

Why update mState via return value, when we could also capture the this pointer in our lambdas and modify mState directly inside the lambdas? This is a safe-guard to avoid undefined behavior. The problem is that the lambdas take a reference to the current state, which is stored in the variant. If we were to change the variant from inside the lambda, we would turn the lambda’s argument into a dangling reference pointing to an object which is now destroyed. Since the compiler doesn’t prevent us from continuing to access the argument after we’ve assigned to the variant, it’s quite easy to run into undefined behavior if we’re not careful. Since the whole point of using a variant to represent our state machine was making it harder to make mistakes, we should go all the way and make this particular mistake impossible as well.

Avoid extra copies?  

The above mechanism has one drawback: extra state self-assignment when there’s no state change. That’s probably not an issue when the state is simple, but if you want to avoid this cost then you might want to try using std::optional.

using MaybeNextState = std::optional<State>;
auto maybeNextState = match(mState,
    [=](Circling& state) -> MaybeNextState 
    {
        // implement circling logic here

        if (playerInOuterZone()) {
          // Switch to next state if applicable
          return FlyToCenter();
        }

        return std::nullopt;
    },...

if (maybeNextState)
  {
    mState = *maybeNextState;
 }

Above, we only reassign mState if maybeNextState is present so we avoid extra copies.

Note: Such technique was originally implemented by Nikolai, but I wanted to make the code a bit shorter and suggested skipping std::optional. See in this pull request.

Source Code  

If you want to see the game discussed in this article in action, check it out on GitHub. The full source is in the state-machine directory. The enemy logic shown above can be found in enemy.cpp.

Conclusion  

We’ve seen how to implement a simple state machine in a robust way using the C++ 17 standard library and a few lines of utility code. The implementation is quite expressive, and also type-safe, making it harder to make mistakes, while still being fairly lean. I like using this approach whenever I come across a problem that lends itself well to using a state machine. It’s worth noting that this approach to state machines has its limits, so once the number of states and transitions in your state machine reaches a certain size, it might make sense to formalize things a bit more, and look into state machine libraries.

You can also see Niko’s presentation from Meeting C++ 2018: