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 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.
Let’s first represent the above seed grid in Scala.
Now we have a basic Representation of our models required in Game of Life.
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