![[haskell-conway.webp]]
# Conway's Game of Life
Conway's Game of Life[^1] 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 are using this game to tweak and try new languages and overall making something fun. There is a ton of existing implementations in every programming languages known in the _cyberspace_. Back then I was learning [Haskell](https://www.haskell.org/), and wanted to see how hard it is to use [SDL2](https://www.libsdl.org/) with it.
Turns out it was pretty easy, since SDL2 bindings were already made by people. 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 that someone used stencil convolution for it, in ==Dyalog APL==. This makes a lot of sense when that game is a grid of 0 and 1. Those tools are generally used for image editing I believe.
## Stencil convolution
Applying a stencil to an _image_ means
1. Put the stencil kernel on every pixel
2. Grab all neighbours and multiply with the corresponding stencil value
3. Add them all and it become the new value of the pixel
In our case, if we represent live cells as 1, dead cells as 0 the stencil we just defined be used to count the number of neighbours for each cell.
```haskell
sten :: 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 pixels and we get a new grid to render! The rest of the code isn’t really interesting, that’s just SDL2 stuff in ==IO Monads==.
![[virus.gif]]
Source: https://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](https://conwaylife.com/book/) I like written by [Nathaniel Johnston](http://njohnston.ca) 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_[^2] you can do.
[^1]: https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life
[^2]: https://en.wikipedia.org/wiki/Conway's_Game_of_Life#Examples_of_patterns