DEV Community

Cover image for Conway's Game of Life in F#
Stefan Alfbo
Stefan Alfbo

Posted on

Conway's Game of Life in F#

Conway's Game of Life is a classic computer science algorithm from the seventies, and Wikipedia 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, F# in WebAssembly. Bolero is built on top of Blazor and this is done with a set of free and open-source libraries.

This solution will use WebAssembly 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.



# 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 .


Enter fullscreen mode Exit fullscreen mode

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

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.



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


Enter fullscreen mode Exit fullscreen mode

Lets add some helper functions to check if a position in the world has a living cell or not.



let isAlive (world: World) (position: Position) =
    List.exists (fun cell -> cell = position) world

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


Enter fullscreen mode Exit fullscreen mode

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

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

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



// 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


Enter fullscreen mode Exit fullscreen mode

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


// 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


Enter fullscreen mode Exit fullscreen mode

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.



// 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 } ]


Enter fullscreen mode Exit fullscreen mode

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 that is leveraging the Model-View-Update architecture.

Architecture

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.

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).



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 }


Enter fullscreen mode Exit fullscreen mode

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.



/// 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 }


Enter fullscreen mode Exit fullscreen mode

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.



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"
                        }
                }
        }
    }


Enter fullscreen mode Exit fullscreen mode

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.



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

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

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


Enter fullscreen mode Exit fullscreen mode

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



dotnet run --project src/GameOfLife.Client


Enter fullscreen mode Exit fullscreen mode

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

The game

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.

Happy coding!

Top comments (0)