Finite state machines

Introduction

In this tutorial we are going to look at a design pattern known as the "finite state machine". Finite state machines are one of the most common ways to script the behavior of agents in games.

How finite state machines work

The basic idea involves dividing the behavior of an agent into several simpler and well-defined "states". There are a couple of important rules when implementing finite state machines. Any given agent can only be in one state at any moment in time. For example, if we were to program a "light switch" it can be in either the "on" or "off" state. The light switch cannot be in neither or both states at the same time.
In this example, all transitions between states are hard-coded inside each state. State transitions are generally triggered by events in the game. With the "light switch" example, this would be the "flip" event. Events themselves could be associated to user input (i.e. pressing a button), timers or could be triggered by the collision system of the game.

Implementation

Now that you have a general idea of how finite state machines work, let's try to implement one. We will start with the player object and we are going to make him run and jump. Note that the following examples uses the FizzX library although any physics library will do.

Player = {}
PlayerMT = { __index = Player }

function Player:create(x, y)
  local self = {}
  setmetatable(self, PlayerMT)
  -- collision
  self.shape = fizz.addDynamic("rect", x, y, 4, 8)
  self.shape.damping = 1.5
  self.grounded = false
  -- state
  self.state = "falling"
  self.elapsed = 0
  return self
end

So far so good. We have the player starting in the "falling" state. It is also useful to track the amount of time "elapsed" since we have entered this state. Next, we are going to add some functionality that updates the state of the player. As you see, the "falling" state is just a string, but it corresponds to a state object where all of the logic is contained. We use the global "states" table to store and access the different states.

function Player:setState(state, ...)
  assert(states[state], "invalid state")
  -- exit previous state
  self:message('exit')
  self.state = state
  self.elapsed = 0
  -- enter next state
  self:message('enter', ...)
end
function Player:updateState(dt)
  self.elapsed = self.elapsed + dt
  self:message('update', dt)
end
function Player:message(msg, ...)
  local func = states[self.state][msg]
  if func then
    func(self, ...)
  end
end

Events and messages

Remember that an agent should never choose or assign his own state. Transitioning between states is always triggered using messages. Messages are used to pass information or "input" to the current state of the player. For example, when the player lands on a platform, we send the "hitground" message. The current state of the player determines how to handle the event. In this example, the player could be in one of four states: "standing", "running", "jumping" and "falling". Transitions can be triggered by six different types of events:

"hitground" - the player lands on top of a platform
"hitroof" - the player hits the bottom of a platform
"fall" - the player is no longer supported by any platform and his vertical velocity is negative
"move" - the user pressed the left or right arrow key
"jump" - the user pressed the jump key
"stop" - the user released the movement keys

State machine diagram with four states (green) and six types of input events (red)

Note that the "move", "jump" and "stop" events are triggered by user input. On the other hand "hitground", "hitroof" and "fall" are caused by the game's collision system. In order to detect and report these events, we have to check the player's desired movement (xm, ym), velocity (xv, yv) and displacement (xd, yd).

function Player:update(dt)
  -- current movement, velocity and displacement
  local xm, ym = self:getMovement()
  local xv, yv = self:getVelocity()
  local xd, yd = self:getDisplacement()

  local isgrounded = yd > 0
  local wasgrounded = self.grounded
  self.grounded = isgrounded
  
  if isgrounded and not wasgrounded then
    self:message("hitground")
  end
  if not isgrounded and wasgrounded then
    self:message("fall")
  end
  if yd < 0 and yv > 0 then
    self:message("hitroof")
  end
  if xm ~= 0 then
    self:message("move")
  end
  if ym > 0 then
    self:message("jump")
  end
  if xm == 0 then
    self:message("stop")
  end
  
  if isgrounded then
    self.shape.friction = 1
  else
    self.shape.friction = 0
  end
  
  self:updateState(dt)
  
  self:setDisplacement(0, 0)
end

Example rectangle (red) displaced after a collision with a circle (green)

The player's velocity and desired movement are self-explanatory. The displacement vector (xd, yd) is a little more complicated. To calculate the displacement vector we have to check all collisions that have occurred during the last physics step. Then we add the changes in the player's position caused by these collisions. The actual code depends on the physics library you are using. Fizz can provide the displacement vector for any shape using:

local dx, dy = fizz.getDisplacement(shape)

The accumulated displacement vector can be calculated like so:

function player.shape:onCollide(b, nx, ny, pen)
  -- add up displacement vectors
  self.xd = self.xd + nx*pen
  self.yd = self.yd + ny*pen
  return true
end

States

One important thing to note about these examples is that each state contains just logic. All of the data and variables are stored in the "agent" object which posseses the state. This limitation is essential so that we can share one state between multiple agents.

Standing

The "standing" state if pretty simple. This state waits until the player presses one of the arrow keys or the jump button (triggering the "move" or "jump" events). Note that we also handle the "fall" event, in case the platform that the character is standing on disappears. By checking the "elapsed" variable, you can play an "idle" animation to make the little guy look bored.

local standing = {}

function standing.fall(agent)
  agent:setState("falling")
end
function standing.jump(agent)
  agent:setState("jumping")
end
function standing.move(agent)
  agent:setState("running")
end
function standing.update(agent, dt)
  if agent.elapsed >= 3 then
    print("I'm bored!")
  end
end

Running

The "running" state increases the player's horizontal velocity (xv) in the direction (xm) he is facing. One temptation could be to use "love.keyboard" here. It's better to get the movement information directly from the agent otherwise all other agents in this state will be contolled using the same keyboard!

local running = {}

function running.update(agent, dt)
  local xv, yv = agent:getVelocity()
  local xm, ym = agent:getMovement()
  agent:setVelocity(xv + 4000*xm*dt, yv)
end
function running.fall(agent)
  agent:setState("falling")
end
function running.jump(agent)
  agent:setState("jumping")
end
function running.stop(agent)
  agent:setState("standing")
end

Falling

The player is in the "falling" state when he is not supported by a platform and his vertical velocity is negative. Note that we only handle the "hitground" message here so that the player can't jump while already falling.

local falling = {}

function falling.update(agent, dt)
  local xv, yv = agent:getVelocity()
  local xm, ym = agent:getMovement()
  agent:setVelocity(xv + 150*xm*dt, yv)
end
function falling.hitground(agent)
  local xm, ym = agent:getMovement()
  if xm == 0 then
    agent:setState("standing")
  else
    agent:setState("running")
  end
end

Jumping

When the players enters the "jumping" state we immediately set his initial jump velocity. While jumping, the player can transition to the "falling" state by releasing the jump button. As soon as the jump button is released we set the vertical velocity to 0. This method results in sharp and unnatural jumps, but for the purposes of this tutorial we'll let it slide.

local jumping = {}

function jumping.enter(agent)
  local xv, yv = agent:getVelocity()
  agent:setVelocity(xv, yv + 250)
end
function jumping.update(agent, dt)
  local xv, yv = agent:getVelocity()
  local xm, ym = agent:getMovement()
  if ym <= 0 or yv < 0 then
    if yv > 0 then
      agent:setVelocity(xv, 0)
    end
    agent:setState("falling")
    return
  end
  agent:setVelocity(xv + 300*xm*dt, yv)
end
function jumping.hitroof(agent)
  agent:setState("falling")
end
function jumping.hitground(agent)
  local xm, ym = agent:getMovement()
  if xm == 0 then
    agent:setState("standing")
  else
    agent:setState("running")
  end
end

Effects and tweaks

The final step is adding graphics, animations and sound effects to the game. You may have noticed that states have an "enter" and "exit" functions which are called during transitions. This should make it fairly easy to associate animations or sounds to each state.

Note that every shape in the game has a "friction" value. When the player is running on top of a platform, friction slows him down so he doesn't "slide". Friction affects the player when he is jumping against walls too. One quick fix is to disable the player friction while he's in the air.

  if self.state == "jumping" or self.state == "falling" then
    self.shape.friction = 0
  else
    self.shape.friction = 1
  end

There are many other factors that affect the "feel" of the game. Unfortunately, programming a decent jumping mechanic is beyond the scope of this tutorial. Thanks for reading and hopefully this tutorial has helped you with the basics.