Sunday, October 23, 2011

A "snaky" tribute to Stuart in Scala with Akka

Hello again.

Today a little bit of Scala. My Clojure current algorithm not being complete, I found myself with the same recurring dilemma. What  am I going to talk about? This is a commitment in trying to understand, then expose a little subject, whatever it is, so to learn how to transfer ideas.

The subject came to me while reading Stuart Halloway book, programming Clojure. Nice book, full of interesting exercises. One of the exercises aims to picture some very amusing use of STM (aka Software Transactional Memory) in the form of a simple Snake game.
A very entertaining part and potentially a nice code kata. One must steer a moving snake in a rectangular area. Some Apple(s) is(are) dispatched in the game area while the snake is rambling. The purpose is to catch apples in order to make the snake grow. One can control the snake using the arrow keys. Once the snake has grown enough you win. But beware the head of the snake must never hit the snakes body . Simple.
Although I do not play game, programming Stuart Halloway example was quite fun and the game may be in implementing the solution.  Stuart Halloway presents a nice simple  architecture separating the purely functional aspect from the mutable state and the GUI. The mutable part of the game can evolve in three ways
  • A game can be reset to its initial state.
  • Every turn, the snake updates its position. If it eats an apple, a new apple
  • is placed.
  • A snake can turn.
My (small !!) Scala brain started yelling : "God, You can do that in Scala" with actors. The game state can be managed by some actor that can reinforce the serialisation of the change. My Scala mind tortures me enough, so I do not want to upset her....but let spice the idea with some Akka.

Having not found a pet project yet in Scala and no Scala Master for guidance, this is the only opportunity I have to bring Akka into the game (may I say). Naturally, I would not recommand using Akka in order to program a little game, the Scala genuine actors being self sufficient in order to manage this kind of implementation.
In the large set of Akka modules we can also find a STM module, and I will not resist in using it. Before starting, I provide here the sbt build.scala project content, sbt being a nice tool, not always very easy to start with:
import sbt._
import sbt.classpath._
import Keys._
import Process._
import System._

object BuildSettings {
  val buildSettings = Defaults.defaultSettings ++ Seq (
    organization        := "com.promindis",
    version             := "0.1-SNAPSHOT",
    scalaVersion        := "2.9.1",
    scalacOptions       := Seq("-unchecked", "-deprecation")
  )
}


object Resolvers {
  val typesafeReleases = "Typesafe Repo" at "http://repo.typesafe.com/typesafe/releases/"
  val scalaToolsReleases = "Scala-Tools Maven2 Releases Repository" at "http://scala-tools.org/repo-releases"
  val scalaToolsSnapshots = "Scala-Tools Maven2 Snapshots Repository" at "http://scala-tools.org/repo-snapshots"
}

object TestDependencies {
  val specs2Version = "1.6.1"
  val testDependencies = "org.specs2" %% "specs2" % specs2Version % "test"
}

object AKKADependencies {
  val akkaVersion = "1.2"
  val actorDependencies = "se.scalablesolutions.akka" % "akka-actor" % akkaVersion
  val stmDependencies = "se.scalablesolutions.akka" % "akka-stm" % akkaVersion
}

object SwingDependencies {
  val swingDependencies = "org.scala-lang" % "scala-swing" % "2.9.1"
}


object MainBuild extends Build {
  import Resolvers._
  import TestDependencies._
  import AKKADependencies._
  import BuildSettings._
  import SwingDependencies._

  lazy val algorithms = Project(
    "Snake",
    file("."),
    settings = buildSettings ++ Seq(resolvers += typesafeReleases) ++  
              Seq (libraryDependencies ++= Seq(testDependencies, actorDependencies, stmDependencies, swingDependencies))
  )

}

Why not following Stuart Halloway path in reusing idioms from the language? Scala being a multi-paradigm language, we could use actors of course, and object oriented approach, colored by some functional treatment into the pattern matching implemented in the actors' bodies .

I wanted the stuff to be simple. The approach can be resumed by the following scheme:

 

The global state lays into an Entities Actor in charge of handling all events incoming from the graphic interface. I voluntarily split the Game board (a swing panel) from the entities actor using a second actor called a board driver.The board driver plays the part of a single access point to the game board, both sending and receiving events in coordination with the entities actor.
The entities actor will send notification concerning the model update to the board driver while the board driver will send direction update notifications and refresh notifications.
Basically, a timer will issue the periodic update to the board driver that will convert it into some actor message. No big stuff.

 Like Stuart Halloway we need useful tools in order to help us swapping from the model world to the screen world. First of all, the Game world must be described by abstractions like positions , dimensions etc... For the sake of simplicity, I introduced the following tool class:
import scala.util.Random._

case class WorldLocation(x: Int, y:Int) {
  def + (location: WorldLocation) : WorldLocation ={
    WorldLocation(x + location.x, y + location.y)
  }
}

object World {
  def winLength = 5

  object Direction {
    val Left = WorldLocation(-1, 0)
    val Right = WorldLocation(1, 0)
    val Down = WorldLocation(0, 1)
    val Up = WorldLocation(0, -1)
  }

  def origin: WorldLocation = WorldLocation(0,0)

  def randomLocation(): WorldLocation = WorldLocation(nextInt(width), nextInt(heigth))

  def heigth: Int = 75
  def width: Int = 100

}

where a position into our small universe can be pointed out by a WorldLocation. The randomLocation method provides us a simple mean to pop an apple in a different location on need. The + operation has been implemented in order to provide more fluent expressions during WorldLocation manipulations. winLength defines the size a snake must grow up to in order for the player to win the game  Describing a small universe serves no purpose unitl we convert our desription into a screen world language. 
Here comes the GraphConverters object, very helpful when dealing with transformations from model to screen:

 
case class ScreenLocation(x: Int, y:Int, width: Int, height: Int)

object GraphicConverters {
  val factor = 10

  def converted(length: Int): Int = length * factor

  def converted(location: WorldLocation): ScreenLocation = diplayPointFrom(location)

  def converted(segment: List[WorldLocation]): List[ScreenLocation] = segment.map(diplayPointFrom(_))


  def diplayPointFrom(location: WorldLocation): ScreenLocation = {
    ScreenLocation(location.x * factor, location.y * factor, factor, factor)
  }

}


A scale factor of value 10 will provide a visible graphical panel surface delimited by a 750 * 1000 rectangle. The diplayPointFrom method takes in charge the basic conversion processe from the game World to the screen World, so it will be reused from the converted methods in charge of handling simple coordinates or list of coordinates. 

 Nice. The game started. We need a entities actor managing our entities. The entities are classified in two sub classes definitions: a snake and an apple. So two object abstractions:

 
 sealed trait Entity

  case class Snake(body: List[WorldLocation], direction: WorldLocation) extends Entity {
    def go(toDirection: WorldLocation): Snake = Snake(body, toDirection)

    def moved: Snake = Snake(ahead::body.take(body.size - 1), direction)

    def grown: Snake = Snake(ahead::body, direction)

    def ahead: WorldLocation = head + direction

    def head: WorldLocation = body.head
  }

case class Apple(location: WorldLocation) extends Entity

I found case classes to be natural implementations of board entities Some of you, dear pals, are going to yell at me. Yes, the Snake entity is a real object, taking in charge its own growth, like a real adult snake, being capable of changing its direction on demand etc...Or does it. As a matter of fact snake instances are immutable, so real "value objects". Every object invocation consists in a pure read access, like head position or leads to the creation of a new snake like moved, grown or go. Can it be more functional ? The location of the methods into the snake definition serves a modular purpose only. Precisely the methods purpose:

 
methodpurpose
gochange direction
movedchange snake position
growngrow snake
aheadprovides next location of head
headlocation of head


We have our two objects.

Good, we need an actor behavior to manage the transformations induced by the incoming events. An akka actor receives its event notifications via the ...receive method:
protected def receive =  {
    case Refresh() => updatePositions(snake,  apple)
    case UpdateDirection(to) => updateDirectionOf(snake, to)
  }

where we recognize the Refresh and UpdateDirection messages set earlier in the model graphic . Starting with  the easiest of all, the snake direction update:
 var snake: Snake = _

 def updateDirectionOf(withSnake: Snake, to : WorldLocation) {
    snake = withSnake.go(to)
  }


The internal actor mutable reference to the snake is basically updated . The updatePosition invocation involves a little bit more of trickery:

 
var snake: Snake = _
  var apple: Apple = _

 def reset() {
    snake = Snake(List(origin), Direction.Right)
    apple = Apple(randomLocation())
  }


 def updatePositions(fromSnake: Snake, fromApple: Apple) {
    fromSnake.body match {
      case head::tail if head == fromApple.location =>
        apple = Apple(randomLocation())
        snake = fromSnake.grown
      case head::tail if tail.contains(head) =>
        Game.displayMessage("You lose")
        reset()
      case head::tail if tail.size == World.winLength  =>
        Game.displayMessage("You win")
        reset()
      case _ => snake = fromSnake.moved
    }

    display ! Updated(snake.body, apple.location)
  }


If the snake eats the apple, in essence , if the the snake head meets the apple location, then a new apple is re-created and the snake grown.
If coincidentally the snake head location meets the snake body, the game is lost, so restarted after notifying the main game board (Game.displayMessage
If hopefully the size of the snake is enough the game is won, so restarted after notifying the main game board (Game.displayMessage
...else we move the snake in its current direction. 

 So suitable is pattern matching dealing with our update !! 

 The Updated message, wraps around locations only and not entities that do belong to the model world. And that's all. Our model is safe, thanks to a containing actor:

package com.promindis.games.snake

import com.promindis.games.snake.World._
import akka.actor.{ActorRef, Actor}

sealed trait StateMessage
case class Refresh() extends StateMessage
case class UpdateDirection(to: WorldLocation) extends StateMessage
case class Updated(snake: List[WorldLocation], apple: WorldLocation) extends StateMessage


class Entities(display: ActorRef) extends Actor {

  sealed trait Entity

  case class Snake(body: List[WorldLocation], direction: WorldLocation) extends Entity {
    def go(toDirection: WorldLocation): Snake = Snake(body, toDirection)

    def moved: Snake = Snake(ahead::body.take(body.size - 1), direction)

    def grown: Snake = Snake(ahead::body, direction)

    def ahead: WorldLocation = head + direction

    def head: WorldLocation = body.head
  }

case class Apple(location: WorldLocation) extends Entity


  var snake: Snake = _
  var apple: Apple = _
  reset()

  def reset() {
    snake = Snake(List(origin), Direction.Right)
    apple = Apple(randomLocation())
  }

  def updatePositions(fromSnake: Snake, fromApple: Apple) {
    fromSnake.body match {
      case head::tail if head == fromApple.location =>
        apple = Apple(randomLocation())
        snake = fromSnake.grown
      case head::tail if tail.contains(head) =>
        Game.displayMessage("You lose")
        reset()
      case head::tail if tail.size == World.winLength  =>
        Game.displayMessage("You win")
        reset()
      case _ => snake = fromSnake.moved
    }

    display ! Updated(snake.body, apple.location)
  }

  def updateDirectionOf(withSnake: Snake, to : WorldLocation) {
    snake = withSnake.go(to)
  }

  protected def receive =  {
    case Refresh() => updatePositions(snake,  apple)
    case UpdateDirection(to) => updateDirectionOf(snake, to)
  }
}

object Entities {
 def apply(display: ActorRef): ActorRef = Actor.actorOf(new Entities(display)).start()
}


We provided a companion object to the actor in order to simplify both creation and start of the actor. A reset action is fired while instantiating the actor. The second part concerns the board and its driver. 
There, we fall into Scala Swing. The Game extends the standard SimpleSwingApplication while gathering the three elements:

val driver = BoardDriver()
val board = new Board(handleFor(driver))
val state = Entities(driver)

where the handle notifying the board of key press events will look like:

def handleFor(boardDriver: ActorRef) : (Value) => Unit = {
    (key: Value) => boardDriver ! ReceivedPressed(key)
  }

Call me a nit-picker if you want, but I did not want the display to know about the driver, although they do lay into the same Game class (making my own bakery of doom ?). So notification of key pressure is blindly fired through a function closing onto the driver. 
 The board by itself (not my favorite part), embeds some DSL's from the the Scala Swing layers:

 
class Board(handle: => (Value) => Unit ) extends Panel {
    var doPaint: ((Graphics2D) => Unit) = (onGraphics) => {}
    preferredSize = new Dimension(GraphicConverters.converted(World.width), GraphicConverters.converted(World.heigth))
    focusable = true

    override def paintComponent(onGraphic: Graphics2D) {
      super.paintComponent(onGraphic)
      doPaint(onGraphic)
    }

    listenTo(keys)

    reactions += {
      case KeyPressed(source, key, modifiers, location) =>
        handle(key)
    }

    def apply(snake: List[ScreenLocation], apple: ScreenLocation) {
      def paintPoint(screenLocation: ScreenLocation, color: Color, onGraphics: Graphics2D) {
        onGraphics.setColor(color)
        onGraphics.fillRect(screenLocation.x, screenLocation.y, screenLocation.width, screenLocation.height)
      }

      doPaint = (onGraphics: Graphics2D) => {
        paintPoint(apple, new Color(210, 50, 90), onGraphics)
        snake.foreach {
          paintPoint(_, new Color(15, 160, 70), onGraphics)
        }
      }
      repaint()
    }
  }

As of Scala Swing the listenTo(keys) and reactions += {...} expressions elegantly set the environment as key event listener. We just added the constructor handle method to the list of reactions to be fired on key press event reception. 
The apply method provides us with an idiomatic way to drive the panel repaint from the board driver. The apply methods receives ScreenLocation infornation immediately converted into a closure that will be invoked during the next paint action, issued from the repaint invocation. As a matter of fact I don't like the idea of storing a reference to the closure on a variable, although the driver board is an actor so serialises its incoming events treatment. 

The board driver implementation remains very simple as a single entry point. Its purpose being only the translation of timer/user inputs into actor messages and actor messages into actions onto the main board:  

class BoardDriver() extends Actor {
    import GraphicConverters._
    import World._

    val directions = Map[Value, WorldLocation](
      Left -> Direction.Left,
      Right -> Direction.Right,
      Up -> Direction.Up,
      Down -> Direction.Down
    )

    protected def receive = {
      case Updated(snake, apple) =>
        board(converted(snake), converted(apple))
      case ReceivedPressed(key) =>
        state ! UpdateDirection(directions(key))
       case ShowMessage(text) => showMessage(parent = board, message = text)

    }
  }

As in all actors, the main purpose is implemented into its receive method. An incoming Updated message implies the invocation of the board after conversion of WorldLocation abstractions into ScreenLocation abstraction. The reception of a KeyPressed message will fire an update order to the entities model and finally a show message will display the dialog box. 
The periodic timer is started into the Game definition. Here it is at the bottom of the whole Game class definition:

 
package com.promindis.games.snake
import java.awt.{Dimension, Graphics2D}
import swing.event.KeyPressed
import swing._
import java.awt.event.{ActionEvent, ActionListener}
import event.Key._
import akka.actor.{ActorRef, Actor}
import swing.Dialog._

object Game extends SimpleSwingApplication {
  val driver = BoardDriver()
  val board = new Board(handleFor(driver))
  val state = Entities(driver)


  def handleFor(boardDriver: ActorRef) : (Value) => Unit = {
    (key: Value) => boardDriver ! ReceivedPressed(key)
  }

  class Board(handle: => (Value) => Unit ) extends Panel {
    var doPaint: ((Graphics2D) => Unit) = (onGraphics) => {}
    preferredSize = new Dimension(GraphicConverters.converted(World.width), GraphicConverters.converted(World.heigth))
    focusable = true

    override def paintComponent(onGraphic: Graphics2D) {
      super.paintComponent(onGraphic)
      doPaint(onGraphic)
    }

    listenTo(keys)

    reactions += {
      case KeyPressed(source, key, modifiers, location) =>
        handle(key)
    }

    def apply(snake: List[ScreenLocation], apple: ScreenLocation) {
      def paintPoint(screenLocation: ScreenLocation, color: Color, onGraphics: Graphics2D) {
        onGraphics.setColor(color)
        onGraphics.fillRect(screenLocation.x, screenLocation.y, screenLocation.width, screenLocation.height)
      }

      doPaint = (onGraphics: Graphics2D) => {
        paintPoint(apple, new Color(210, 50, 90), onGraphics)
        snake.foreach {
          paintPoint(_, new Color(15, 160, 70), onGraphics)
        }
      }
      repaint()
    }
  }


  case class ShowMessage(text: String)
  case class ReceivedPressed(keyCode: Value)

  class BoardDriver() extends Actor {
    import GraphicConverters._
    import World._

    val directions = Map[Value, WorldLocation](
      Left -> Direction.Left,
      Right -> Direction.Right,
      Up -> Direction.Up,
      Down -> Direction.Down
    )

    protected def receive = {
      case Updated(snake, apple) =>
        board(converted(snake), converted(apple))
      case ReceivedPressed(key) =>
        state ! UpdateDirection(directions(key))
       case ShowMessage(text) => showMessage(parent = board, message = text)

    }
  }

  object BoardDriver {
    def apply() = Actor.actorOf(new BoardDriver()).start()
  }

  def displayMessage(text: String) {
    driver ! ShowMessage(text)
  }

  def top = new MainFrame {
    title = "Snake"
    contents = new FlowPanel() {
      val timer = new javax.swing.Timer(100, new ActionListener() {
        def actionPerformed(e: ActionEvent) {
          state ! Refresh()
        }
      }).start();
      contents += board
    }
    pack()
  }
}

One minute pals. Didn't I promise for a STM implementation ? Well, the Game, its board and board drivers remaining almost unchanged, the stuff that do really changes is the Entities class. No more actor involved in this template.

package com.promindis.game.snake.stm
import com.promindis.game.snake.stm.World._
import akka.stm._


object Entities {
  sealed trait Entity

  case class Snake(body: List[WorldLocation], direction: WorldLocation) extends Entity {
    def go(toDirection: WorldLocation): Snake = Snake(body, toDirection)

    def moved: Snake = Snake(ahead::body.take(body.size - 1), direction)

    def grown: Snake = Snake(ahead::body, direction)

    def ahead: WorldLocation = head + direction

    def head: WorldLocation = body.head
  }

  case class Apple(location: WorldLocation) extends Entity

  val snake: Ref[Snake] = Ref(Snake(List(origin), Direction.Right))
  var apple: Ref[Apple] = Ref(Apple(randomLocation()))

  private def reset() {
    snake.set(Snake(List(origin), Direction.Right))
    apple.set(Apple(randomLocation()))
  }

  def updatePositions() {
     atomic{
       val fromSnake: Snake = snake.get()
       val fromApple: Apple = apple.get()
       fromSnake.body match {
          case head::tail if head == fromApple.location =>
              apple.set(Apple(randomLocation()))
              snake.set(fromSnake.grown)
          case head::tail if tail.contains(head) =>
            Game.displayMessage("You lose")
            reset()
          case head::tail if tail.size == World.winLength  =>
            Game.displayMessage("You Win")
            reset()
          case _ => snake.set(fromSnake.moved)
        }
       Game.update(snake.get().body, apple.get().location)
     }
  }

  def updateSnakeDirection(to : WorldLocation) {
    atomic {
      snake.alter(fromPrevious => fromPrevious.go(to))
    }
  }
}

The global state of game, consisting in a snake and an apple will be updated atomically in one transaction. The code will look familiar to Clojure developers. And it is, quoting Jonas Boner, "Refs (transactional references) are mutable references to values and through the STM allow the safe sharing of mutable data. Refs separate identity from value." 
A transaction is delimited using the atomic keyword. The snake and apple definitions remaining the same, the snake and apple object "values" will be identified by two immutable reference fields:

val snake: Ref[Snake] = Ref(Snake(List(origin), Direction.Right))
val apple: Ref[Apple] = Ref(Apple(randomLocation()))

The updatePositions method implementation makes use of the atomic keyword, using then the get/set methods of references in order to modify the references value. Invoked from the Game, the updateSnakeDirection method uses the alternate alter method which accepts a function that takes the old value while creating a new value of the same type, still in the scope of a transaction. 
We used a closure for the purpose of our implementation. The reset method is made private as being exclusively invoked from an atomic scope. Coming back to the Game class, we provide a version very close to the previous one:

 
package com.promindis.game.snake.stm
import java.awt.{Dimension, Graphics2D}
import swing.event.KeyPressed
import swing._
import java.awt.event.{ActionEvent, ActionListener}
import event.Key._
import akka.actor.{ActorRef, Actor}
import swing.Dialog._

object Game extends SimpleSwingApplication {
  val driver = BoardDriver()
  val board = new Board(handleFor(driver))


  class Board(handle: => (Value) => Unit ) extends Panel {
    var doPaint: ((Graphics2D) => Unit) = (onGraphics) => {}
    preferredSize = new Dimension(GraphicConverters.converted(World.width), GraphicConverters.converted(World.heigth))
    focusable = true

    override def paintComponent(onGraphic: Graphics2D) {
      super.paintComponent(onGraphic)
      doPaint(onGraphic)
    }

    listenTo(keys)

    reactions += {
      case KeyPressed(source, key, modifiers, location) =>
        handle(key)
    }

    def apply(snake: List[ScreenLocation], apple: ScreenLocation) {
      def paintPoint(screenLocation: ScreenLocation, color: Color, onGraphics: Graphics2D) {
        onGraphics.setColor(color)
        onGraphics.fillRect(screenLocation.x, screenLocation.y, screenLocation.width, screenLocation.height)
      }

      doPaint = (onGraphics: Graphics2D) => {
        paintPoint(apple, new Color(210, 50, 90), onGraphics)
        snake.foreach {
          paintPoint(_, new Color(15, 160, 70), onGraphics)
        }
      }
      repaint()
    }
  }

  def displayMessage(text: String) {
    driver ! ShowMessage(text)
  }


  def handleFor(boardDriver: ActorRef) : (Value) => Unit = {
                          (key: Value) => boardDriver ! ReceivedPressed(key)
  }

  case class ShowMessage(text: String)

  case class ReceivedPressed(keyCode: Value)

  case class Updated(snake: List[WorldLocation], apple: WorldLocation)
  class BoardDriver() extends Actor {
    import GraphicConverters._
    import World._

    val directions = Map[Value, WorldLocation](
      Left -> Direction.Left,
      Right -> Direction.Right,
      Up -> Direction.Up,
      Down -> Direction.Down
    )

    protected def receive = {
      case Updated(snake, apple) =>
        board(converted(snake), converted(apple))
      case ReceivedPressed(key) =>
        Entities.updateSnakeDirection(directions(key))
      case ShowMessage(text) => showMessage(parent = board, message = text)
    }
  }

  object BoardDriver {
    def apply() = Actor.actorOf(new BoardDriver()).start()
  }

  def update(list: List[WorldLocation], location: WorldLocation) {
    driver ! Updated(list, location)
  }

  def top = new MainFrame {
    title = "Snake"
    contents = new FlowPanel() {
      val timer = new javax.swing.Timer(100, new ActionListener() {
        def actionPerformed(e: ActionEvent) {
          Entities.updatePositions()
        }
      }).start();
      contents += board
    }
    pack()
  }
}


Hurray, we have did it !!!!!!! 

Okay the game's very simple, the boundary positions are not controlled, but the kata is worth while. Thank you Stuart Halloway. Must go to fix my next blog code...in Clojure this time. Very strange bug indeed. 

 Be seeing you !!! :)

5 comments:

mslinn said...

It would be great to see all of the source code, so I can understand what you did better.

Thank you for this post.

Globulon said...

Ah !! Was thinking about github :) Going to check how to post code :)

mslinn said...

The top of each class should have:
package com.promindis.game.snake.stm
... which is where I put the 4 classes so they could compile.

Here is my build.sbt:

import com.typesafe.startscript.StartScriptPlugin

seq(StartScriptPlugin.startScriptForClassesSettings: _*)

name := "ActorTest"

version := "1.0"

scalaVersion := "2.9.1"

resolvers ++= Seq(
"Sonatype" at "http://nexus.scala-tools.org/content/repositories/public",
"Scala Tools" at "http://scala-tools.org/repo-releases/",
"JBoss" at "http://repository.jboss.org/nexus/content/groups/public/",
"Akka" at "http://akka.io/repository/",
"GuiceyFruit" at "http://guiceyfruit.googlecode.com/svn/repo/releases/"
)

libraryDependencies ++= Seq(
"se.scalablesolutions.akka" % "akka-actor" % "1.2",
"se.scalablesolutions.akka" % "akka-stm" % "1.2",
"org.scala-lang" % "scala-swing" % "2.9.1",
"org.scalatest" %% "scalatest" % "1.6.1" % "test"
)

Globulon said...

Thanks a lot for the build.sbt file content :). I added the package definitions as they were in source code .

mslinn said...

I did not find this project in github. A simplified and cleaned up version of Game.scala is at https://gist.github.com/1314819

Post a Comment