Conway's Game of Life in F#
Tags: 100daystooffload, fsharp, bolero, webassembly
Published: 2023-10-01 18:52:15

Conway's Game of Life is a classic computer science algorithm from the seventies, and [Wikipedia](https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life) summarize it well.

> The Game of Life, also known simply as Life, is a cellular automaton devised by the British 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. One interacts with the Game of Life by creating an initial configuration and observing how it evolves. It is Turing complete and can simulate a universal constructor or any other Turing machine.

Lets implement this algorithm with [Bolero](https://fsbolero.io/), F# in WebAssembly. Bolero is built on top of [Blazor](https://blazor.net/) and this is done with a set of free and open-source libraries.

This solution will use [WebAssembly](https://webassembly.org/) directly in the browser.


We begin with setting up the project structure for this solution by using the console and the Bolero project template. There are more options to play with, which is documented [here](https://github.com/fsbolero/Template#template-options).

```sh
# Install the project template for Bolero
dotnet new -i Bolero.Templates
# Create a Bolero application
dotnet new bolero-app --server=false --minimal=true -o GameOfLife && $_
# Open the code editor
code .
```

This will create a skeleton Bolero application with empty content. The option `--server=false` makes the solution to only use the `Client` project which will be compiled to WebAssembly.

The project tree structure will look like this.

![Project tree structure](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/viyrnlvquvwamqd6g4cl.png)

Add a new file, `Core.fs`, and place it right before the `Main.fs` file. This module will include all code that is needed for implementing the Game of Life algorithm.

We will represent the game world as a grid where each square is either empty or it will contain a living cell.

```fsharp
module GameOfLife.Client.Core

// The world is a 10x10 grid
let width = 10
let height = 10

// A position is a point on the grid
type Position = { X: int; Y: int }
// A world is a list of all the alive cells
type World = Position list
```

Lets add some helper functions to check if a position in the world has a living cell or not.
 
```fsharp
let isAlive (world: World) (position: Position) =
    List.exists (fun cell -> cell = position) world

let isEmpty (world: World) (position: Position) =
    not (isAlive world position)
```

Now we need to implement a function to get all the neighbors to a cell and the ones that are alive. A neighbor is a cell that is horizontally, vertically, or diagonally adjacent (up to eight).

![Neighbors](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jz0g7yv6cjionqtl5cuk.png)

One important note to make about the world is that it can be seen as a doughnut, which means that the cells will come over to the left side of the grid when it moves beyond the right border.

![The world](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4lmwsnkb94t0c80h7pja.png)

This is something that we will need to think about when designing the function.

```fsharp
// Euclidean remainder, the proper modulo operation
let inline (%!) a b = (a % b + b) % b

let neighbors (position: Position) =
    // Wrap around the edges of the grid.
    let wrap (position: Position) =
        { X = ((position.X - 1) %! width) + 1; Y = ((position.Y - 1) %! height) + 1 }
    
    [
        { X = position.X - 1; Y = position.Y - 1 };
        { X = position.X;     Y = position.Y - 1 };
        { X = position.X + 1; Y = position.Y - 1 };
        { X = position.X - 1; Y = position.Y };
        { X = position.X + 1; Y = position.Y };
        { X = position.X - 1; Y = position.Y + 1 };
        { X = position.X;     Y = position.Y + 1 };
        { X = position.X + 1; Y = position.Y + 1 };
    ] |> List.map wrap

let liveNeighbors (world: World) (position: Position) =
    neighbors position
    |> List.filter (isAlive world)
    |> List.length
```

With those functions in place we can start to implement the game rules.

1. Any live cell with two or three live neighbors survives
2. Any dead cell with three live neighbors becomes a live cell
3. All other live cells die in the next generation. Similarly, all other dead cells stay dead

```fsharp
// Any live cell with two or three live neighbors survives
let survivors (world: World) =
    world
    |> List.filter (fun position ->
        let liveNeighbors = liveNeighbors world position
        liveNeighbors = 2 || liveNeighbors = 3
    )

// Any dead cell with three live neighbors becomes a live cell
let births (world: World) =
    world
    |> List.collect neighbors
    |> List.filter (isEmpty world)
    |> List.filter (fun position ->
        liveNeighbors world position = 3
    )

// All other live cells die in the next generation. Similarly, all other dead cells stay dead
let nextGeneration (world: World) =
    world
    |> survivors
    |> List.append (births world)
    |> List.distinct
```

Last we will create an initial seed for the program called the glider. There are other famous seeds for this game that can be found on the Wikipedia site.

```fsharp
// Initial game seed
let glider =
    [ { X = 4; Y = 2 }
      { X = 2; Y = 3 }
      { X = 4; Y = 3 }
      { X = 3; Y = 4 }
      { X = 4; Y = 4 } ]
```

The `Core` module with all the game logic is now complete.

Time to move back to Bolero and start to create something that can visualize the game for us. With Bolero comes [Elmish](https://elmish.github.io/elmish/) that is leveraging the Model-View-Update architecture.

![Architecture](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wn6ygofn71cus4zahl90.png)

The basic pattern as stated from the Elm documentation

* Model — the state of your application
* View — a way to turn your state into HTML
* Update — a way to update your state based on messages

These three concepts are the core of [The Elm Architecture](https://guide.elm-lang.org/architecture/).

This will be defined in the `Main.fs` file in our application. We begin with our **Model**, open the file and replace the model with this one (note that we also updates the modules/namespace we will be using in this module).

```fsharp
module GameOfLife.Client.Main

open Elmish
open Bolero
open Bolero.Html
open GameOfLife.Client.Core


/// The Elmish application's model.
type Model =
    { generation: int
      world: World }

let initModel =
    { generation = 0
      world = glider }
```

This model will keep track of the state of the game world and the number of generation that has been generated. Here we are using our initial seed, `glider`, for our game.

The code to update next is the `Message` and the `update` function.

```fsharp
/// The Elmish application's update messages.
type Message =
    | NextGeneration

let update message model =
    match message with
    | NextGeneration ->
        { model with
            generation = model.generation + 1
            world = nextGeneration model.world }
```

There is only one message needed for our application, `NextGeneration`. The function `update` is responsible to update the state of our model based on the given message. We only have one message so we only need to handle that message. 

The `generation` property is increased with one. The `world` property is update with the help of our `nextGeneration` function from the `Core` module.

Last part of the *Elmish* architecture is to provide a view based on the current state.

```fsharp
let view model dispatch =
    concat {
        h1 { $"Generation {model.generation}" }
        button { 
            on.click (fun _ -> dispatch NextGeneration) 
            "Next generation"
        }
        table {
            for row in 0..height do
                tr {
                    for column in 0..width do
                        let position = { X = column; Y = row }
                        let isAlive = isAlive model.world position
                        td { 
                            attr.``class`` (if isAlive then "alive" else "dead")
                            "o"
                        }
                }
        }
    }
```

Here we define a title, `h1`, to display how many generation we have produced by clicking on the button, **Next generation**. The `on.click` function on the button is responsible of dispatching the message, `NextGeneraton`, which will produce next generation. Finally we are showing the current state of world with a HTML table. There are also some CSS for this table and it's added to end of the file, `index.css`.

```css
td {
  margin: 0;
  padding: 5px;
  height: 5px;
  width: 5px;
}

.alive {
  background: black;
  color: black;
  border-radius: 50%;
}

.dead {
  background: white;
  color: white;
}
```

With everything on place we can start the application and try it out.

```sh
dotnet run --project src/GameOfLife.Client
```

In the browser, surf to `http://localhost:5000` to see the result.

![The game](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4aifwwqit61g5sinx88x.png)

This is the first rough version of the game. There are of course things to polish here. My next step will probably be to implement some kind of timer that can fire the `NextGeneration` message in a steady stream to simulate the game much better. There are also some improvements around the HTML and CSS, however these things will be done some other time.

The complete source code can be found on [GitHub](https://github.com/stefanalfbo/GameOfLife).

Happy coding!