![[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