log 014

Game Dev Log: Update Loop

Another log incoming, this time let's talk about the update loop. If you remember from the last log this is where left off setting up our high level game loop:

// MAIN ------------------------------------------------------------------------

pub fn main() {
  let app = lustre.application(init, update, view)
  let assert Ok(_) = lustre.start(app, "#app", Nil)

  Nil
}

// MODEL -----------------------------------------------------------------------

type Model {
  Idle
  Ready(previous_time: Float, fps: Float)
}

fn init(_) -> #(Model, Effect(Msg)) {
  #(Idle, schedule_next_frame())
}

// UPDATE ----------------------------------------------------------------------

type Msg {
  Tick(current_time)
}

fn update(model: Model, msg: Msg) -> #(Model, Effect(Msg)) {
  case msg {
    Tick(current_time) -> { 
      let frame_time = calc_frame_time(model, current_time) 
      
      // Since division by 0 is illegal the division function
      // returns a Result type we need to pattern match on.
      let fps = case float.divide(1000.0, frame_time) {
        Ok(fps) -> fps
        _ -> 60.0
      } 
      
      #(Ready(previous_time: current_time, fps: fps), schedule_next_tick())
    } 
  }
}

fn calc_frame_time(model: Model, current_time: Float) { 
  case model { 
    Ready(previous_time, ..) -> float.subtract(current_time, previous_time)
    _ -> 0.0
  }
}

// VIEW ------------------------------------------------------------------------

fn view(model: Model) -> Element(Msg) {
  html.div([], [
    html.canvas([]),
    html.div([], render_debugger(model)),
  ])
}

fn render_debugger(model: Model) { 
  case model { 
    Idle -> html.p([],[html.text("Initializing")])
    Ready(previous_time, fps) -> {
      html.p([],[
        float.to_string(previous_time) |> html.text
        html.text(" • "),
        float.to_string(fps) |> html.text
      ]) 
    }
  }
}

The game loop consists of two separate loops. Each loop has some core ideas to understanding why they exist and how they work together.

The Update Loop:

  1. The game loop does not always run at your target FPS. So your update loop is responsible for “catching up” to the target FPS.
  2. Should process all events since the last update in order.
  3. Should advance any time based state by the number of elapsed frames since the last update.

The Render Loop:

  1. You only want to render once per game loop.
  2. Rendering should not be responsible for any state mutation.

This article is going to demonstrate the core ideas for the update loop for the isometric TRPG I'm building by adding a Map and Cursor to navigate around it.

Let's start by breaking down what I meant by “the game loop does not always run at your target FPS” and how we can mitigate that in our loop.

The target frame per second in my game, as we discussed in the last log, is 60 FPS. What this means is that for every second that passes we have 60 game loops (a update loop + render loop). However, there are factors that can effect the speed of these updates.

  • For some games that is the network latency.
  • Some games it can be cause by very heavy rendering requirements.

Whatever the reason, they are legion, and they fall into the side effects category. Which, as discussed in the last log, means we do not have control over them, but are responsible for their results.

How we manage this specific side effect is by allowing our update loop to “catch up” by running the update loop the same number of frames that we missed since the last update.

Here is how we can update our loop to do that:

Our state is getting larger and will be passed in whole to functions moving forward so let's go ahead and split that into it's own data type separate from our app Model.

type Model { 
  Idle
  Ready(GameState)
} 

type GameState { 
  GameState(
    fps: Float
    previous_time: Float
  )
}

Next, let's add an accumulator to our game state. The accumulator is for us to be able to track drift in our frame rate. This is done by getting the delta between the previous update time with the current update time. Using our fixed frame rate 60 FPS we can calculate how many frames have passed since the last update, and update our game state for each frame that should have happened since the last update.

Because we will write our loop to catch up on all missed frames, one guard rail we will want to put in is a cap on the number of frames to try and catch up on. If we have a huge lag in the game loop this will keep us from compounding that problem accounting for every possible frame.
const max_update_frames = 6

type GameState { 
  GameState(
    accumulator: Float
    fps: Float
    previous_time: Float
  )
}

fn update(model: Model, msg: Msg) -> #(Model, Effect(Msg)) {
  case msg {
    Tick(current_time) -> {
      case model {
        Ready(game_state) -> {
          let updated_state = 
            game_state 
              |> update_time(current_time)
              |> update_state()
      
          #(Ready(updated_state), schedule_next_tick())
      } 
      Idle -> #(Ready(init_game_state(current_time)), schedule_next_frame())
    } 
  }
}

fn update_time(game_state: GameState, current_time: Float) { 
  let time_since_last_frame = calc_frame_time(game_state, current_time)
  let accumulator = float.add(game_state.accumulator, time_since_last_frame)
      
  // Since division by 0 is illegal the division function
  // returns a Result type we need to pattern match on.
  let fps = case float.divide(1000.0, time_since_last_frame) {
    Ok(fps) -> fps
    _ -> 60.0
  }
  
  GameState(..game_state, accumulator: accumulator, fps: fps, previous_time: current_time)
}

fn calc_frame_time(game_state: GameState, current_time: Float) { 
  float.subtract(current_time, game_state.previous_time)
}

fn update_state(game_state: GameState) { 
  update_state_loop(game_state, 0)
}

fn update_state_loop(game_state: GameState, loop_count: Int) { 
  let has_pending_frames = float.compare(acc, fixed_dt) |> is_gt_or_eq
  case has_pending_frames && loop_count <= max_update_frames { 
    True -> { 
      game_state
      // All update logic will be added here
      |> update_state_loop(
           GameState(
             ..game_state,
             accumulator: float.subtract(game_state.accumulator, fixed_dt)
           )
         )
    }
    False -> game_state
  }
}

fn is_gt_or_eq(order: Order) -> Bool {
  case order {
    order.Lt -> False
    _ -> True
  }
}

fn init_game_state(current_time: Float) { 
  GameState(
    accumulator: 0.0,
    fps: 60.0,
    previous_time: current_time,
  )
}

There we have it. The framework we need to run our updates in with the confidence that any hiccups in our frame rate will be picked right back up without spiraling our engine into a black hole. Now we can add something to actually update. This way we can move on to the next core principle.

We will add our types for the Map and Cursor, as well as get our GameState setup to track both.

type GameState { 
  GameState( 
    accumulator: Float
    cursor: Cursor
    fps: Float
    map: Map
    previous_time: Float
  )
}

type Cursor { 
  Cursor(
    coords: Coord
  )
}

type Coord { 
  Coord(x: Int, y: Int, z: Int)
}

type Map { 
  Map( 
    width: Int
    height: Int
  )
}

Okay I have state and an update loop to make changes to the cursor location, but there is no way to tell the loop to move the cursor. We need events, but there is a hurdle we need to address. Our loop is time triggered not event triggered. This means we need a system for pushing events somewhere the update loop can pull from when it is running.

We need an event_queue.

type GameState { 
  GameState( 
    accumulator: Float
    cursor: Cursor
    event_queue: List(Event)
    fps: Float
    map: Map
    previous_time: Float
  )
}

type Event { 
  UserMovedCursor(Direction)
}

type Direction { 
  Up
  Down
  Left
  Right
}

Now let's go back to the update loop we already scaffolded and process the queue during our update.

fn update_state_loop(game_state: GameState, loop_count: Int) { 
  let has_pending_frames = float.compare(acc, fixed_dt) |> is_gt_or_eq
  case has_pending_frames && loop_count <= max_update_frames { 
    True -> { 
      game_state
      |> apply_events()
      |> update_update_loop(
           GameState(
             ..game_state,
             accumulator: float.subtract(game_state.accumulator, fixed_dt)
           )
         )
    }
    False -> game_state
  }
}

fn apply_events(
  game_state: engine.GameState,
) -> engine.GameState {
  game_state.events
    |> list.fold_right(game_state, apply_event)
    |> reset_events
}

fn apply_event(game_state: GameState, event: Event) { 
  case event {
    MoveCursor(direction) -> {
      let coords =
        direction
        |> coord.move(game_state.cursor.coord, game_state.map)
              
      GameState(
        ..game_state,
        cursor: {
          ..game_state.cursor,
          coords: coords,
        }
      )
    }
  }
}

fn reset_events(game_state: GameState) { 
  GameState(..game_state, events: [])
}

We are folding from the right because we want first in first out vs the last in first out approach the default fold uses.

The coord module is actually pretty core to the system. I'm not going to break the whole thing down here for the sake of brevity, but you can check it all here. For this log you can assume the move function works exactly like you would think. It moves a Coord by one in the direction passed.

We have a handler for our event queue, let's start pushing events into it. You'll never guess what we need to add when we are setting up a keyboard event listener that could be triggered at an unknown time for an unknown number of times in our MVU system….(yes it is an Effect)

type Msg {
  Tick(current_time)
  PlayerQueueEvent(Event)
}

fn update(model: Model, msg: Msg) -> #(Model, Effect(Msg)) {
  case msg {
    Tick(current_time) -> {...}
    PlayerQueueEvent(event) -> { 
      case model { 
        Ready(game_state) -> queue_event(game_state, event)
        _ -> panic
      }
    }
  }
}

fn queue_event(game_state: GameState, event: Event) { 
  GameState(..game_state, events: [event, ..game_state.events])
} 

fn setup_listeners() {
  effect.from(fn(dispatch) {
    input.on_keyboard_event(fn(game_key) {
      let direction = direction.from_game_key(game_key)
      dispatch(PlayerQueueEvent(MoveCursor(direction)))
    })
  })
}

I didn't dig too deep into the FFI implementation forrequest_animation_frame last article, but in the implementation for our event listener FFI there is some extra work to put some guard rails on it. Let's take a deeper look.

In our underlying JavaScript code we are taking an extra step to filter the data being returned to our listener. Specifically, we're filtering to target only keyboard events vs just any general event.

function with_keyboard_data(cb) {
  return function listener(e) {
    return cb({
      key: e.key,
      alt_key: e.altKey,
      ctrl_key: e.ctrlKey,
      meta_key: e.metaKey,
      repeat: e.repeat,
      shift_key: e.shiftKey,
    });
  };
}

export function add_keyboard_event_listener(cb) {
  return window.addEventListener("keydown", with_keyboard_data(cb));
}

This allows us to narrow the scope of functionality and make our gleam module for dealing with keyboard input cleaner.

pub type GameKey {
  UpKey
  DownKey
  LeftKey
  RightKey
}

pub type KeyboardEvent {
  KeyboardEvent(
    key: String,
    alt_key: Bool,
    ctrl_key: Bool,
    meta_key: Bool,
    repeat: Bool,
    shift_key: Bool,
  )
}

fn decode_game_key(event: KeyboardEvent) -> Result(GameKey, String) {
  case event.key {
    "ArrowUp" | "w" -> Ok(UpKey)
    "ArrowDown" | "s" -> Ok(DownKey)
    "ArrowLeft" | "a" -> Ok(LeftKey)
    "ArrowRight" | "d" -> Ok(RightKey)
    _ -> Error("Unsupported key")
  }
}

pub fn on_keyboard_event(cb: fn(GameKey) -> Nil) -> Nil {
  add_keyboard_event_listener(fn(event) {
    case decode_game_key(event) {
      Ok(game_key) -> cb(game_key)
      Error(_) -> Nil
    }
  })
}

// Bind for only keyboard event_listener
//
@external(javascript, "../client_lib_engine_ffi.mjs", "add_keyboard_event_listener")
fn add_keyboard_event_listener(listener: fn(KeyboardEvent) -> Nil) -> Nil

In the direction module we have a helper to turn our input key into a Direction type.

pub fn from_game_key(game_key: input.GameKey) -> Direction {
  case game_key {
    input.UpKey -> Up
    input.DownKey -> Down
    input.LeftKey -> Left
    input.RightKey -> Right
  }
}

We have narrowed the raw window event into a keyboard event first and then narrowed it further to a domain that is specific to our game with the use of the GameKey type. Now our listener can pattern match on a Game specific input without any extra filtering or conditions.

There is one final piece to wrap up our update loop, but let's review what we have done so far:

  • Added something to the game we can update
  • Setup timings to track if we need to make up for lost frames
  • Add an event listener to capture user input
  • Added a queue to store user inputs
  • Process and apply the queue to the game state
  • Update our state based on time elapsed since last frame

We applied the pending events to our game state, however in our game we want the Cursor to have an animation. This will apply to a lot of game state that may be triggered based on the time that has elapsed since our last frame.

We will model our Cursor animation to have three key pieces of data to calculate an animation:

  1. Time elapsed: this allows us to track progress towards completing the animation. This animation is a loop so it track progress towards the cycle point to start the animation over.
  2. Cycle duration: as just mentioned it is the total time for a single animation loop to complete.
  3. Amplitude: Since I am still in eeeearly days we use this property to calculate how far the cursor’s z coordinate should be oscillating to and fro until we settle on a final fixed amount.
type Cursor { 
  Cursor(
    coords: Coord
    animation CursorAnimation
  )
} 

type CursorAnimation { 
  CursorIdle(
    elapsed: Float
    cycle: Float
    amplitude: Float
  )
}

fn update_state_loop(game_state: GameState, loop_count: Int) { 
  let has_pending_frames = float.compare(acc, fixed_dt) |> is_gt_or_eq
  case has_pending_frames && loop_count <= max_update_frames { 
    True -> { 
      game_state
      |> apply_events()
      |> update_entities()
      |> update_state_loop(
           GameState(
             ..game_state,
             accumulator: float.subtract(game_state.accumulator, fixed_dt)
           )
         )
    }
    False -> game_state
  }
}


fn update_entities(game_state: engine.GameState) {
  let new_cursor = update_cursor(game_state.cursor)
  GameState(..game_state, cursor: new_cursor)
}

fn update_cursor(cursor: Cursor) { 
  case cursor.animation { 
    CursorIdle(elapsed, cycle, amplitude) -> { 
      let updated_elapsed = 
        elapsed
        |> float.add(fixed_dt)
        |> float.modulo(cycle)
        |> result.unwrap(0.0)
        
      Cursor(
        ..cursor, 
        animation: CursorIdle(
          elapsed: updated_elapsed, 
          cycle: cycle, 
          amplitude: amplitude
        )
      )
    }
  }
}

There we have it! The three core principles of a update loop handled and broken down. As with the last log let's end it with a way for you to see it in action. We will cover the render loop next and start drawing graphics on the screen but for now you can just look at some data.

fn view(model: Model) -> Element(Msg) {
  html.div([], [
    html.canvas([]),
    html.div([], render_debugger(model)),
  ])
}

fn render_cursor(model: Model) { 
  case model { 
    Ready(game_state) -> { 
      html.p([], [
		html.text("Cursor is located at (" <> game_state.cursor.x <> ", " <> game_state.cursor.y)
	  ])
    } 
    _ -> html.text("Waiting...")
  }
}

See ya next time!

I hope you enjoyed

There is a lot more coming...

If you want to get updates when I publish new guides, demos, and more just put your email in below.