Why Games Love State Machines

Less bugs. Clear code paths.

"I start programming my Character Controller, thinking 'this time, it's gonna be neat, simple, and easy to extend'... and then it turns into spaghetti code"

Sound familiar?

Let's outline an example of how this may go down. To make the example simpler, we'll only focus on is_jumping, is_dashing and is_falling, though this problem gets worse the more boolean flags we add.

Player_State :: struct {
  is_running: bool,
  is_jumping: bool,
  is_falling: bool,
  is_dashing: bool,
  is_grounded: bool,

  pos: Vec2,
  vel: Vec2,
}

player_update :: proc(ps: ^Player_State) {
  // Jump
  if input.jump && !ps.is_jumping && ps.is_grounded {
    ps.is_jumping = true
    ps.is_grounded = false
    ps.vel.y = JUMP_VEL
  }

  if input.dash && !ps.is_dashing {
    ps.is_jumping = false
    ps.is_dashing = true
  }

  // Dashing keeps current vertical position
  if ps.is_dashing {
    ps.vel.y = 0
  }

  // Fall (+Y is often 'down' in 2D games)
  if ps.is_falling {
    ps.vel.y += GRAVITY
    ps.vel.y = max(ps.vel.y, TERMINAL_VEL)
  }

  // ...
}

Do you see the bug? Even with this small amount of code, it may be difficult to spot!

The is_falling flag is not set to false when a dash is started. Therefore, if the player starts dashing on the way up their jump, everything seems fine. However, if they start just at the apex, or on the way down, the dash will have gravity applied.

This is a small example, but you can imagine how complex these controllers get in a full game. You may have dozens of booleans.

Another thing to point out is that bugs can occur not just because a boolean is set or unset, but also the order in which they are checked.

Finite State Machines

Enter finite state machines (FSMs). They provide a way to define a finite number of valid states for our character.

Not all the booleans fit into the FSM. For example, we can be dashing but not jumping (these fit, and are hence orthogonal states). However, we may be grounded and running at the same time.

Player_Movement_State :: enum {
  Idle,
  Running,
  Jumping,
  Falling,
  Dashing,
}

Player_State :: struct {
  movement_state: Player_Movement_State,
  is_grounded: bool,

  pos: Vec2,
  vel: Vec2,
}

player_update :: proc(ps: ^Player_State) {
  switch ps.movement_state {
  case Idle:
    if input.left || input.right {
      ps.movement_state = .Running
    }
    if input.jump {
      ps.movement_state = .Jumping
      ps.is_grounded = false
    }
  case Running:
    if input.jump {
      ps.movement_state = .Jumping
      ps.is_grounded = false
    }
  case Jumping:
    ps.vel.y = JUMP_VEL
    // Somehow determine when jump finished (up to implementation)
    if jump_apex_reached {
      ps.movement_state = .Falling
    }
  case Falling:
    ps.vel.y += GRAVITY
    ps.vel.y = max(ps.vel.y, TERMINAL_VEL)
  case Dashing:
    // Somehow determine dash finished (up to implementation)
    if dash_finished {
      if ps.is_grounded {
        ps.movement_state = .Idle
      } else {
        ps.movement_state = .Falling
      }
    }
  }
}

Now you can see exactly what code is running depending on orthogonal states. Some code is duplicated, and wherever necessary, you can easily pull that out:

player_try_jump :: proc(ps: ^Player_State) {
  if input.jump {
    ps.movement_state = .Jumping
    ps.is_grounded = false
  }
}

It's common to want to use state machines everywhere, but I'd caution against that. I would suggest using these in places where it's clear there are orthogonal states and you definitely do not want overlapping behaviours.

In some cases, you may want overlapping behaviours - I'll write about that in a future newsletter.

The trade-off of FSMs is inherent in it's structure: it creates N number of code paths for you to now consider, and perhaps even more.

player_update -> [N]Player_Movement_State -> [M]player_try_xxx.

More Examples

You've already seen the character controller example, let's briefly touch on a couple more.

Enemy AI

Consider an enemy in your game. You may want it to patrol randomly, or following some waypoints. Then, when the player comes into a certain range, you want the enemy to start chasing the player. If the enemy gets within striking distance, it should throw out an attack. If the player gets lost somehow (invisibility, running too fast, etc) - then the enemy may walk back to it's post and continue patrolling.

[Patrolling]
player detected --> [Chasing]

[Chasing]
player within range --> [Attacking]
player lost --> [Searching]

[Searching]
search timer ended --> [Returning]

[Returning]
returning finished --> [Patrolling]

UI Screens

Usually, we don't want multiple menus open at the same time. For example, when the player is loading a saved game, they don't want to look at the settings menu.

[Main Menu]
'continue' selected --> [Load Game Menu]
'settings' selected --> [Settings Menu]

Hierarchical State Machines

State machines can be nested into a hierarchy in multiple ways.

One way is to use the standard enum approach I showed and have a particular set of states, making up their own orthogonal set, that are only accessible via one state.

However, that can be confusing as the amount of states that are unrelated pile up.

Another approach is to simple create a separate state machine.

Imagine an old-school JRPG game.

Primary State: [Exploration, Combat, Menu]

Exploration States: [Walking, Running, Swimming, Climbing]
Combat States: [Attacking, Blocking, Dodging, Casting]
Menu States: [Inventory, Skills, Map, Dialogue]

With this kind of setup, the map cannot be opened during combat, for example.

You can't accidentally start climbing while in the middle of casting.

Event Based State Changes

So far, the only way we've seen to change states is by putting some conditions right into the active code path.

However, you may want to allow events to update states. This decouples state change from the code path and could get messy quickly, but is very powerful.

For example, imagine a scenario where an enemy is chasing the player, so it's in the [Chasing] state. The player is crafty, though, and throws a smoke bomb - obscuring the enemy's vision and making it lose the player.

// Perhaps the smoke bomb has some code like this
entity_ids := gather_entities_nearby(pos, radius)

for entity_id in entity_ids {
  event_emit(entity_id, "vision_obscured")
}

Now the enemy can react to this dynamic event without having it coded in the state machine itself:

event_listen(entity_id, "vision_obscured", proc() {
  entity.state = .Searching
})

This approach allows us to keep the code that handles vision and detection separate from the AI state machine itself. Any system that affects visibility may emit an event and the AI will respond in kind.

Conclusion

State machines keep orthogonal states in design orthogonal in the code.

An escape hatch can be added with something like an event system (for example) - but without caution, this will soon turn into hard to debug spaghetti code once again.

As usual, there’s no silver bullet - just trade-offs.