Finite state machines

In this tutorial we are going to look at a design pattern known as "finite state machines". 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. A given finite state machine can only be in one state at any moment in time. For example, if we were to program a "light switch" it will be in either the "on" or "off" state. The light switch cannot be in neither or both states at the same time.
Transitioning between states must be clearly defined. One simple approach involves defining the transitions implicitly in each state. State transitions are generally triggered by events in the game. With the "light switch" example, this would be the "flip switch" 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.

State machine of a platformer

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 will use the Fizz library to handle collisions.

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 a "falling" state. Next, we are going to add some functionality that updates the state of the player:
function Player:setState(state, ...)
  assert(states[state], "invalid state")
  -- exit previous state
  if states[self.state].exit then
    states[self.state]:exit(self)
  end
  self.state = state
  self.elapsed = 0
  -- enter next state
  if states[self.state].enter then
    states[self.state]:enter(self, ...)
  end
end
function Player:updateState(dt)
  self.elapsed = self.elapsed + dt
  states[self.state]:update(self, dt)
end
function Player:message(msg, ...)
  if states[self.state].message then
    states[self.state]:message(self, msg, ...)
  end
end

Events

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 pass 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" - occurs when the player lands on top of a platform
"hitroof" - occurs when the player hits the bottom of a platform
"fall" - occurs when the player is no longer on top of a platform
"move" - occurs when the user presses the left or right arrow key
"jump" - occurs when the user presses the jump button
"stop" - occurs when the user releases the arrow 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

Player states

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. If you want to get fancy, you can play an "idle" animation to make the little guy look bored.
states.standing = {}

function states.standing:message(agent, msg)
  if msg == "fall" then
    agent:setState("falling")
  elseif msg == "jump" then
    agent:setState("jumping")
  elseif msg == "move" then
    agent:setState("running")
  end
end

Running

The "running" state increases the player's horizontal velocity (xv) in the direction (xm) he is facing. Quite a lot of acceleration is necessary to make the character run, because the platform blocks have high friction. Without the friction, the player would slide across platforms like he was on ice.
function states.running:update(agent, dt)
  local xv, yv = agent:getVelocity()
  local xm, ym = agent:getMovement()
  agent:setVelocity(xv + 4000*xm*dt, yv)
end
function states.running:message(agent, msg)
  if msg == "fall" then
    agent:setState("falling")
  elseif msg == "jump" then
    agent:setState("jumping")
  elseif msg == "stop" then
    agent:setState("standing")
  end
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.
function states.falling:update(agent, dt)
  local xv, yv = agent:getVelocity()
  local xm, ym = agent:getMovement()
  agent:setVelocity(xv + 150*xm*dt, yv)
end
function states.falling:message(agent, msg)
  if msg == "hitground" then
    local xm, ym = agent:getMovement()
    if xm == 0 then
      agent:setState("standing")
    else
      agent:setState("running")
    end
  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.
function states.jumping:enter(agent)
  local xv, yv = agent:getVelocity()
  agent:setVelocity(xv, yv + 250)
end
function states.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 states.jumping:message(agent, msg)
  if msg == "hitroof" then
    agent:setState("falling")
  elseif msg == "hitground" then
    local xm, ym = agent:getMovement()
    if xm == 0 then
      agent:setState("standing")
    else
      agent:setState("running")
    end
  end
end

Effects and gameplay 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 a few other factors that affect the "feel" of the game. "fizz.setGravity()" determines how fast the player falls and the trajectory of his jumps. "player.shape.damping" decreases the player's velocity over time, making his jumps feel more controlled. 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.

Download:  fsm.lua
player.lua
states.lua
player.png