Conway's Game of Life in Haskell

2016 · Haskell · SDL2 · Source

Conway's Game of Life

Conway's Game of Life¹1Wikipedia · Conway's Game of Life is a cellular automaton devised by mathematician John Horton Conway in 1970. It is a zero-player game, meaning that its evolution is determined by its initial state, requiring no further input. The game consists of a grid of cells, each of which can be in one of two states: alive or dead. The state of the cells evolves over discrete time steps according to a set of simple rules:

1. Underpopulation: Any live cell with fewer than two live neighbours dies.
2. Survival: Any live cell with two or three live neighbours lives on to the next generation.
3. Overpopulation: Any live cell with more than three live neighbours dies.
4. Reproduction: Any dead cell with exactly three live neighbours becomes a live cell.

The fun part of doing it in Haskell

Lots of developers use this game to try out new languages and make something fun. There are tons of existing implementations in every programming language known in the cyberspace. At the time, I was learning Haskell and wanted to see how hard it was to use SDL2 with it.

It turned out to be pretty easy, since people had already made SDL2 bindings. What was left was just the logic of the game. I could have done it with classic recursive functions, but I stumbled upon an article where someone used stencil convolution for it in Dyalog APL. This makes a lot of sense when the game is a grid of 0s and 1s. I believe those tools are generally used for image editing.

Stencil convolution

Applying a stencil to an image means:

1. Put the stencil kernel on every pixel.
2. Grab all neighbours and multiply them by the corresponding stencil value.
3. Add them all; this becomes the new value of the pixel.

In our case, if we represent live cells as 1 and dead cells as 0, the stencil we just defined can be used to count the number of neighbours for each cell.

1
2
3
4
5
6
7
8
9
10
11
12sten :: RS.Stencil R.DIM2 Int
sten = [stencil2| 1 1 1
                  1 0 1
                  1 1 1 |]

transit :: Int -> Int -> Int
transit 1 2 = 1
transit 1 3 = 1
transit 1 _ = 0
transit 0 3 = 1
transit 0 _ = 0
transit _ _ = 0

And that’s pretty much it. On each frame, we compute the stencil on every pixel and get a new grid to render! The rest of the code isn’t very interesting; it’s just SDL2 stuff in IO Monads.

Source code: github.com/Rydgel/haskell-conway

Going further

There is so much more to the Game of Life, and some people have been researching this stuff like crazy. There is a book I like, written by Nathaniel Johnston and Dave Greene, called “Conway's Game of Life: Mathematics and Construction”. You can read it on the website, and it includes live demos for all the many constructions and entities²2Wikipedia · Conway's Game of Life › Examples of patterns you can make.

Back to Experiments · see also Flappy Bird in Haskell · Home.