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.
- A cell in the grid can be dead or alive.
- A live cell with less than 2 live neighbours will die.
- A live cell with 2 or 3 live neighbours will stay alive.
- A live cell with more than 3 live neighbours will die.
- 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.
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
Representation in Scala
Let’s first represent the above seed grid in Scala.
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.
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
Here is an algorithm, I found on StackOverflow, by Seb
Here is a direct implementation of this algorithm in