Game development in Scala

How functional programming helps me sleep at night

Me

• Michael Shaw
• Scala for 4 years (Scalatra/Akka/Game Dev)
• Ruby on Rails at We Are Brand New
• 10 months in to developing a game in Scala
• Mostly functional brain

Context

Problem

False Starts

Solution

Reflection

Lich

• Developed from scratch in Scala ... accidentally
• You're a lich raising an undead army in an open & alive world

Lots of voxels

Lots of creatures/entities

Problem

Lovers of purity prepare your buckets

Your average game loop

            while(running) {
              update(world, 0.05)
              render(world)
            }

            def update(world:World, delta:Double) {
              for(entity <- world.entities) {
                entity.update(world, delta)
              }
            }

            def render(world:World) {
              for(entity <- world.entities) {
                draw(entity)
              }
            }

          

Everyone's favourite return type

          class Entity {
            def update(world:World, delta:Double) : Unit = {
              // here be dragons
            }
          }
          

Who the hell knows what happens in there?

Launch missiles?

Probably not.

IO?

Probably not.

Unrestricted mutation of the game world?

Yeah :(

State

class World(val size:Vec2i) {
  val blocks = new Array[Byte](size.product)
  val entities = new mutable.HashMap[Int, Entity]()

class Entity(val position:Vec2i) {
  val facing = Vec2i(1, 0)
  var health = 100
  var weaponDrawn = false
  var attacking = false
          

• Arrays are fast ... really, really fast
• Performance is a currency to be spent. More creatures, larger worlds
• Immutable datastructures for long running state => Old gen GC pressure
• We're stuck with mutation of some sort

What about Multiplayer?

• Not wise to develop up front (unless that's your focus)
• Painful to add later
• How do we keep that mutable soup of void functions in sync?

In to the void

• If you accept the void/unit functions signatures, you're already screwed
• The type system is not acknowledging our side effects
• How do we reconstruct changesets for multiplayer clients:
• Calculate deltas from retained entity states?
• Make components record changes during the frame?
• Write mutations to clients as they happen?

False Starts

Disclaimer: I lack the formal qualifications to present the next slide

#2 Monadifying things

Too big to copy, let's orchestrate mutation

  sealed trait WorldMonad[S] { // state thread s
    private def blocks : Array[Byte]

    def getBlockId(x:Int, y:Int) : ST[S, Byte]
    def setBlockId(x:Int, y:Int, b:Byte) : ST[S, WorldMonad[S]]
    def getEntity(entityId:Int) : ST[S, Entity]
  }

  // ST[S, A] is a "state transformer" roughly: S => (S, A)
  // transforms state indexed by type S, delivers type A

  object WorldMonad {
    def apply[S](blocks:Array[Byte]) = new WorldMonad[S] {
      val blocks = blocks
    } // called once at the start of game to construct the world
  }

  def updateEntity[S](entity:Entity) : WorldMonad[S] => WorldMonad[S] // ???
          

• Copying is gone. We have typesafe serial mutation of the world.
• The contents of the monad still share the same problems of the mutable version.
• Maybe functional programming isn't the answer ...

Solution

John Carmack

QuakeCon 2013 (heavily paraphrased)

"Run all your entities independently in a functionally pure way, pass in a static copy of the world (from last frame) and themselves, and they return a new version of themselves at the end"

def updateEntity(entity:Entity, world:World) : Entity

But Mr. Carmack? How are the entities going to affect change outside of themselves?

"You create events that get communicated to the target entities"

In their simplest form: Entity => Entity

  def takeDamage(damage:Int)(e:Entity) : Entity = {
    e.copy(health = clamp(e.health - damage, 0, 100))
  } // partially apply with a damage value to get an "event"
          

Events are then routed to their target entities which evaluate them on next frame

Let's modify this a little

• Change the partially applied functions to explicit event classes
• One type per possible side effect
• These events sometimes need to reply with events too

case class TakeDamage(damage:Int, fromEntityId:Int, toEntityId:Int) extends Event {
// immutable version
def applyTo(entity:Entity) : (Entity, Seq[Event]) =  {
  (entity.copy(health = clamp(entity.health - damage, 0, 100)), Seq.empty)
}

// mutable version
def applyTo(entity:Entity) : Seq[Event] {
  entity.health = clamp(entity.health - damage, 0, 100)
  Seq.empty
}
            

• 90% of our entity logic can remain pure, 10% is a simple set of events that can modify entities
• Immutable vs. Mutable is a trivial set of code changes

  def updateEntity(entity:ReadonlyEntity, world:ReadonlyWorld) :
    (Seq[Event], Seq[StateTransition])
            

Goblin A hits Goblin B

Events & Message Passing

Game logic is pure functions that emit events

  def updateEntity(entity:ReadonlyEntity, world:ReadonlyWorld) :
    (Seq[Event], Seq[StateTransition]) // 90%

    // our game loop becomes
    val eventsToRoute = world.entities.values.flatMap { entity =>
      val replyEvents = entity.events.flatMap { ev =>
        ev.applyTo(entity) // take damage from others etc.
      }
      val (externalEvents, stateTransitions) = updateEntity(
        entity.asInstanceOf[ReadonlyEntity],
        worldFromLastFrame
      )
      for(t <- stateTransitions) {
        t.applyTo(entity) // change entity position etc.
      }
      replyEvents ++ externalEvents
    }

  // route events and repeat 

• Explicit Side Effects
• Hidden mutation no longer possible, the update functions have nothing they can change
• Having side effects up front is much easier than reconstructing them from the soup later

Routing

Mutable

  // send events out between frames
  for(event <- eventsToRoute) {
    world.entities(event.toEntityId).events += event
  }

  

Immutable

  // group the events by toEntityId before the frame
  val eventsById = eventsFromLastFrame.groupBy(_.toEntityId).withDefault(Seq.empty)
  // Map[Int, Seq[Event]]

  val eventsToRoute = world.entities.values.flatMap { entity =>
    val replyEvents = eventsById(entity.id).flatMap { ev =>
      ev.applyTo(entity)
    }
    // the rest of the update code

          

Our new game loop

val eventsById = eventsFromLastFrame.groupBy(_.toEntityId).withDefault(Seq.empty)
// Map[Int, Seq[Event]]

val eventsToRoute = world.entities.flatMap { entity =>
  val replyEvents = eventsById(entity.id).flatMap { ev =>
    ev.applyTo(entity) // take damage from others etc.
  }
  val (externalEvents, stateTransitions) = updateEntity(
    entity.asInstanceOf[ReadonlyEntity],
    worldFromLastFrame
  )
  for(t <- stateTransitions) {
    t.applyTo(entity) // change entity position etc.
  }
  replyEvents ++ externalEvents
}

It's all good then right?

• Effects are serialized in the context of entities, and external side effects occur in the next frame (lag)
• Events that you thought would succeed can now fail
• Two entities trying to pickup an item (also an entity) at the same time

This is all great, but I don't recall seeking out purity/correctness or even immutability ...

Parallelism (of the embarassing kind)

Since mutation is entity local, our game loop can become

val eventsToRoute = world.entities.par.flatMap { entity =>
  val replyEvents = eventsById(entity.id).flatMap { ev =>
    ev.applyTo(entity) // take damage from others etc.
  }
  val (externalEvents, stateTransitions) = updateEntity(
    entity.asInstanceOf[ReadonlyEntity],
    worldFromLastFrame
  )
  // rest of update code

          

(We added the .par)

Performance Shmerformance

Routing Revisited

  def updateClientWorld(playerId:Int, world:World, server:MultiPlayerServer) {
    // apply state updates from server
    for((id, events) <- server.entityEvents.groupBy(_.toEntityId)) {
      val entity = world.entityFor(id)
      for(event <- events) {
        event.applyTo(entity)
      }
    }

    // locally simulate our player entity
    val playerEntity = world.getEntity(playerId)
    val replyEvents = server.playerEvents.flatMap { ev =>
      ev.applyTo(playerEntity)
    }

    val (externalEvents, stateTransitions) = updateEntity(playerEntity, world)

    for(t <- stateTransitions) {
      t.applyTo(entity) // mutation
    }

    server.sendEvents(stateTransitions, externalEvents ++ replyEvents)
    // all events must go to the server
  }

          

Multiplayer/Singleplayer is only a routing change away
(with some custom events too)

These problems were always there

Multiplayer clients can never be certain about the success of actions until sent to the server, serialized and replied to.

This is the speed of light rearing it's ugly head again.

In order to support multiplayer later, you need to act like multiplayer now, handle failure & conflict.

A little reflection

Benefits of the FP + Events approach

• Logging/debugging/testing/explicitness/correctness etc. etc.
• Multiplayer/singleplayer is a routing change away
• Game logic remains the same (implement a feature once)
• Our types document things. Expansion of scope requires expansion of events & types
• We're making better use of our compiler
• Purity is enforced through handing our update functions readonly versions of entities/the world

What did I learn here?

• Carmack is a smart man
• The functional process was important, analyzing side effects and data flow
• Purity can be hugely beneficial
• Both mutable and immutable versions of the code were:
• Terrible when the base abstraction was wrong
• Trivially different with the event model

Why didn't events seem obvious from the start?

Thanks for listening

Slides & example code are on michaelshaw.io