← Back Home

# Game Of Life (in Scala)

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.

``````case class Cell(value: Int)

case class Point(row: Int, col: Int) {
def unapply() = (this.row, this.col)
}

val alive = Cell(0)

val row1 = Array(alive, alive, alive, alive)

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.

``````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
}

// apply rules based on number of live neighbours
def deadOrAlive(liveNeighbours: Int): Cell = {
else if (liveNeighbours == 2 || liveNeighbours == 3) alive
else if(liveNeighbours == 3) alive
}

``````

## 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.

``````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

``````row_limit = count(array);
if(row_limit > 0){
column_limit = count(array);
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`.

``````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
}
``````