I recently came across an interesting problem/game called Game Of Life. A visual version of this is available here. Also, here is a beginners introduction to Game Of Life, or simply Life, written by Alex Bellos at Guardian.

It is a cellular automation problem created by John Horton Conway, a British mathematician in 1970, not a game you play to win or lose. This problem has a few rules that we need to follow.

Rules

  1. A cell in the grid can be dead or alive.
  2. A live cell with less than 2 live neighbours will die.
  3. A live cell with 2 or 3 live neighbours will stay alive.
  4. A live cell with more than 3 live neighbours will die.
  5. A dead cell with exactly 3 neighbours will become alive.

These rules are pretty simple. Once we know the number of live neighbours of a given cell, we can determine it’s fate in a step. In this post I’m going to dicuss method to find neighbours of a given cell in a matrix.

In Game of Life, we take a seed grid and eventually get another grid as a output, by applying the rules to each cell.

Game Of Life grid

Game of Life is played in an infinite two dimensional grid. But for the sake of simplicity let us take a 4x4 grid.

0 1 2 3
0 Cell(1) Cell(1) Cell(1) Cell(1)
1 Cell(1) Cell(0) Cell(1) Cell(0)
2 Cell(0) Cell(0) Cell(0) Cell(0)
3 Cell(1) Cell(0) Cell(1) Cell(0)

1 is alive and 0 is dead

A cell can have a maximum of 8 neighbours depending on it’s position in the grid, horizontally, vertically, or diagonally adjacent to it.

After applying rules first step, we will get the following

0 1 2 3
0 Cell(1) Cell(0) Cell(1) Cell(1)
1 Cell(1) Cell(0) Cell(1) Cell(1)
2 Cell(1) Cell(0) Cell(1) Cell(1)
3 Cell(0) Cell(1) Cell(0) Cell(0)

Representation in Scala

Let’s first represent the above seed grid in Scala.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
case class Cell(value: Int)
case class Point(row: Int, col: Int) {
  def unapply() = (this.row, this.col)
}
val alive = Cell(0)
val dead = Cell(1)
val row1 = Array(alive, alive, alive, alive)
val row2 = Array(alive, dead, alive, dead)
val row3 = Array(dead, dead, dead, dead)
val row4 = Array(alive, dead, alive, dead)
val board = Array(row1, row2, row3, row4)

Now we have a basic Representation of our models required in Game of Life.

Find neighbours of a given Cell in two dimensional array

Given the co-ordinates of a cell, we should be able to find list of it’s live neighbours.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def findNeighbours(board: Array[Array[Cell]], point: Point):List[Cell] = ???
def findLiveNeighbours(board: Array[Array[Cell]], point:Point):List[Cell] =
        findNeighbours(board, point).filter(c => c.value == 1)
// one step
def step(board: Array[Array[Cell]]): Array[Array[Cell]] = {
  val rows = board.length
  val cols = board(0).length
  // create a new Matrix of same dimensions
  val output = Array.ofDim[Cell](rows, cols)
  // loop through the array and set value for output cell
  // based on number of live neighbours
  for(i <- 0 until rows) {
    for(j <- 0 until cols) {
      val point = Point(i,j)
      val liveNeighbours = findLiveNeighbours(board, point).length
      // apply rules based on number of live neighbours
      output(i)(j) = deadOrAlive(liveNeighbours)
    }
  }
  output
}
// apply rules based on number of live neighbours
def deadOrAlive(liveNeighbours: Int): Cell = {
      if (liveNeighbours < 2) dead
      else if (liveNeighbours == 2 || liveNeighbours == 3) alive
      else if(liveNeighbours > 3) dead
      else if(liveNeighbours == 3) alive
      else dead
}

Find neighbours

Now this is the important bit.

A neighbour is any cell that is adjacent to a given cell, horizontally, vertically or diagonally. (1,1) is adjacent to (0,0), (0,1), (0,2), (1,0), (1,2), (2,0), (2,1), (2,2).

We will implement findNeighbours functions.

1
def findNeighbours(board: Array[Array[Cell]], point(x:Int, y:Int)):List[Cell] = ???

Algorithm

Here is an algorithm, I found on StackOverflow, by Seb

http://stackoverflow.com/questions/652106/finding-neighbours-in-a-two-dimensional-array

1
2
3
4
5
6
7
8
9
10
11
row_limit = count(array);
if(row_limit > 0){
  column_limit = count(array[0]);
  for(x = max(0, i-1); x <= min(i+1, row_limit); x++){
    for(y = max(0, j-1); y <= min(j+1, column_limit); y++){
      if(x != i || y != j){
        print array[x][y];
      }
    }
  }
}

Here is a direct implementation of this algorithm in Scala.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def findNeighbours(board: Array[Array[Cell]], point: Point): List[Cell] = {
  val (row, col) = point unapply
  var cells: List[Cell] = List.empty[Cell]
  val rowLimit = board.length - 1
  val columnLimit = board(0).length - 1
  for (x <- math.max(0, i - 1) to math.min(row + 1, rowLimit)) {
    for (y <- math.max(0, j - 1) to math.min(col + 1, columnLimit)) {
      if (x != i || y != j) {
        cells = cells :+ board(x)(y)
      }
    }
  }
  cells
}