Quite for some time I was thinking about refreshing Akka skills and providing some simple demo of what one can do with Akka and Actor Model. Finally, the winter time has come, I will show the Conway’s Game of Life reactive implementation with Akka Actors.

TL;DR: code

The rules are very simple, the current state of a cell on a two-dimentional grid depends only on previous state of the cell and a number of “alive” cells among surrounding 8 neighbors cells (immediate vertical, horizontal and diagonal adjacent cells). The implementation in Scala looks like this:

object Cell {
    def apply(alive: Boolean, around: Int): Boolean = {
        assert(around >= 0)
        (alive, around) match {
            case (true, n) if n < 2 => false
            case (true, n) if n == 2 || n == 3 => true
            case (true, n) if n > 3 => false
            case (false, n) if n == 3 => true
            case _ => false
        }
    }
}

The initial idea I had was to keep each cell’s state in a dedicated actor, thus allowing “reactive” and consistent transitions to the next state. The only events happening are cells becoming “alive” or “empty”, thus once cell becomes “alive”, the surrounding 8 cells receive a message that number of neighbors increased, and respectfully, when cell becomes “empty” - decreased. Scaling this out (to suppot grids that don’t fit single instance) might be tricky, as messages between adjacent cells must still be able to find their way to addressed cell. Location transparency FTW.

For this post, I will limit the scope to small grids, but the code doesn’t need to be changed much for a distributed case, just using Akka Remoting looks enough. The distributed option will remain on my to-do list, as it might be interesting to run. Tricky to visualize/observe though - how to observe million by million grid? It’s 1E12 cells, but it might be interesting to play with some statistics about it.

Back to small grids, but keep scaling out in mind. I need to split a grid in chunks, perfect use case for a Quad Tree. The quad tree nodes are forks and leaves, with forks keeping list of quads that belongs a level down, and leaves keeping the sub-grid of cells and mapping from cell’s position to a CellActor. So for sub-quad border-line cells, some adjacent cells lay in different quads, and it makes sense to forward updates to such “remote” cells via parent quad tree node. Then quad tree node can decide if an update should go to respective quad or go to a higher level of a quad tree. Eventually such event will land respective cell, and the longet such path (for central 4 cells) will go up to the quad tree root and then down to respective cell through quad tree nodes. It scales though, and each actor keeps doing their thing: CellActor stores state and handles updates from neighbors, GridActor stores either split quads or references to actual cells and handles routing of updates for “remote” cells.

This is all very nice, but how do I actually see what is really happening on the grid? I isolated 2 abstractions: Contol to let user provide some input (click on specific cell) and Display, that is responsible for rendering specific cell in a given state. I believe the signatures below are self-explanatory enough:

// The position of the cell on the grid
case class Pos(row: Int, col: Int)

trait Control {
  def click(pos: Pos): Unit
  def terminate(): Unit
}

trait Display {
  def fill(pos: Pos): Unit
  def clear(pos: Pos): Unit
}

These two abstractions are more than enough to keep the show going! The actuall execution of input and state updates is performed in scope of DisplayActor, as this is essentially all what can happen: user can click or a cell gets rendered on a screen.

The actual rendering is implemented via SimGraf, nice and small UI library (built on top of Akka as well). The result looks like this:

Conway's Game of Life

The unit-tests of the code are left as an excercise for a reader.