DEV Community

Cover image for Cellular Automata in F#
Logan Mortimer
Logan Mortimer

Posted on • Originally published at isthisit.nz

Cellular Automata in F#

#fsharp #dotnet

Rule 90

Rule 90

Simple rules can generate complex behaviour. I'm reading A New Kind of Science by Stephen Wolfram. A key idea of the book is that a simple rule, applied iteratively, can generate complex behaviour. The difference between Rules 222, 90, and 30 are trivial, yet they generate vastly different results.

In this post we explore the principles and implement the Elementary Cellular Automata system in F#.

Rule 222

Rule 222

Rule 30

Rule 30

Cellular Automata

Here's a 7 x 4 grid. The dots represent Empty cells, the X represent Full cells. All of our grids start with a single Full cell in the middle of the top row.

...X...
.......
.......
.......
Enter fullscreen mode Exit fullscreen mode

We then define a rule. A rule is a function which decides whether a single cell is Empty or Full. This rule function takes values of the 3 cells from the row directly above, corresponding to the cells above and to the left (1), directly above (2), and above and to the right (3). We visualise this below. The cell we are trying to calculate is ?.

123....        .123...        ..123..        ...123.        ....123
.?.....        ..?....        ...?...        ....?..        .....?.
.......        .......        .......        .......        .......
.......        .......        .......        .......        .......
Enter fullscreen mode Exit fullscreen mode

The same rule is applied row after row. The rule is not applied to cells in the far left column and far right columns. These cells will always remain Empty. We'll look at the naming convention of rules later on, but for now here's one example.

Below is Rule 222. The first pattern is saying that if cells 1, 2, and 3 are Full, then the cell ? will be Full. And so on, for every possible combination of those 3 cells.

XXX    XX.    X.X    X..    .XX    .X.    ..X    ...
 X      X      .      X      X      X      X      .
Enter fullscreen mode Exit fullscreen mode

This system of rules is as simple as we can get. Each cell can only have two possible states, and the value of the next cell only depends on it's neighbours.

Rules as Code

We just described the Celluar Automata domain. Let's implement it in code.

  • A Cell can be either Empty or Full.
  • The Rule type is a function which takes 3 Cells and returns the value of a single Cell. 
// A Cell is either Empty or Full
type Cell = Empty | Full

// Rules are functions which take in the values of 3 Cells, and return a single Cell value
type Rule = (Cell * Cell * Cell) -> Cell

// Rule 222 implemented in code
let rule222: Rule = function 
    | (Full, Full, Full) -> Full
    | (Full, Full, Empty) -> Full
    | (Full, Empty, Full) -> Empty
    | (Full, Empty, Empty) -> Full
    | (Empty, Full, Full) -> Full
    | (Empty, Full, Empty) -> Full
    | (Empty, Empty, Full) -> Full
    | (Empty, Empty, Empty) -> Empty
Enter fullscreen mode Exit fullscreen mode

Modelling the Grid

We've just described the Cellular Automata system in its entirety. Patterns and complexity emerge from just those rules. The rules by themselves are abstract and we need to apply them somehow. Here we apply the rule on a simple grid. But the same rule could be applied to any other surface - a 3D surface, mobius strip, or grid where the values wrap around.

Onto the implementing the system on a grid. Let's start off by generating the first row.

let generateStandardFirstRow (width: int) =

    if width % 2 = 0 then invalidArg "width" (sprintf "Value must be an odd number. Value passed was %d." width)

    Seq.init width (function
        | n when n = (width / 2) -> Full
        | _ -> Empty
    )
Enter fullscreen mode Exit fullscreen mode

So

generateStandardFirstRow 7
Enter fullscreen mode Exit fullscreen mode

Gives us

Empty Empty Empty Full Empty Empty Empty
Enter fullscreen mode Exit fullscreen mode

In order to generate the next row we only need to know the row before it. We take the previous row and apply Seq.windowed. This splits the row of Cells into groups of 3 Cells, which we need in order to calculate the next value.

Recall that our rule requires 3 cells in order to calculate the next value. This is the cell above and to the left, the cell directly above, and the cell above and to the right. This is a problem for the far left and far right columns of the grid. They only have 2 of the 3 cells required. To get around this we enforce a rule that the left column and right column will always remain Empty.

let generateNextRow (rule: Rule) (row: Cell seq) =
    let generatedCells =
        row
        |> Seq.windowed 3
        |> Seq.map (fun v ->
            rule (v.[0], v.[1], v.[2])
        )

    // the first and last Cells of each row are Empty since we didn't generate a value for them above
    seq {
        yield Empty
        yield! generatedCells
        yield Empty
    }
Enter fullscreen mode Exit fullscreen mode

Now let's write a function which generates row after row. Sequences in F# are lazily evaluated. They're the C# IEnumerable type under the hood. By treating everything as a sequence we're essentially defining the rules as to how the grid will be generated.

Seq.unfold iteratively applies the Rule to whatever the previous row was, collecting results. Notice we don't specify how many rows to generate, that's up to the caller of this function.

let generatePattern (rule: Rule) (firstRow: Cell seq) = 
    firstRow
    |> Seq.unfold (fun row ->
        Some(row, (generateNextRow rule row))
        )
Enter fullscreen mode Exit fullscreen mode

Now we can generate the grid!

let firstRow = generateStandardFirstRow 101
let rows = generatePattern rule222 firstRow |> Seq.take 10
Enter fullscreen mode Exit fullscreen mode

But we want to visualise it. Here's a basic ASCII renderer.

let drawCell = function
| Full -> "X"
| Empty -> "."

/// Render the grid to an ASCII string
let drawGrid (grid: Cell seq seq) =
    grid
    |> Seq.map (fun row ->
        row
        |> Seq.map drawCell
        |> String.concat ""
    )
    |> String.concat "\n"

drawGrid rows
Enter fullscreen mode Exit fullscreen mode 
..................................................X..................................................
.................................................XXX.................................................
................................................XXXXX................................................
...............................................XXXXXXX...............................................
..............................................XXXXXXXXX..............................................
.............................................XXXXXXXXXXX.............................................
............................................XXXXXXXXXXXXX............................................
...........................................XXXXXXXXXXXXXXX...........................................
..........................................XXXXXXXXXXXXXXXXX..........................................
.........................................XXXXXXXXXXXXXXXXXXX.........................................
Enter fullscreen mode Exit fullscreen mode

Other Rules

Our algorithm works! Let's experiment with other rules.

let rule90: Rule = function
    | (Full, Full, Full) -> Empty
    | (Full, Full, Empty) -> Full
    | (Full, Empty, Full) -> Empty
    | (Full, Empty, Empty) -> Full
    | (Empty, Full, Full) -> Full
    | (Empty, Full, Empty) -> Empty
    | (Empty, Empty, Full) -> Full
    | (Empty, Empty, Empty) -> Empty

let firstRow = generateStandardFirstRow 101
let rows = generatePattern rule90 firstRow |> Seq.take 50
let arrayOfRows = rows |> Seq.toArray

drawGrid rows
Enter fullscreen mode Exit fullscreen mode 
..................................................X..................................................
.................................................X.X.................................................
................................................X...X................................................
...............................................X.X.X.X...............................................
..............................................X.......X..............................................
.............................................X.X.....X.X.............................................
............................................X...X...X...X............................................
...........................................X.X.X.X.X.X.X.X...........................................
..........................................X...............X..........................................
.........................................X.X.............X.X.........................................
........................................X...X...........X...X........................................
.......................................X.X.X.X.........X.X.X.X.......................................
......................................X.......X.......X.......X......................................
.....................................X.X.....X.X.....X.X.....X.X.....................................
....................................X...X...X...X...X...X...X...X....................................
...................................X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X...................................
..................................X...............................X..................................
.................................X.X.............................X.X.................................
................................X...X...........................X...X................................
...............................X.X.X.X.........................X.X.X.X...............................
..............................X.......X.......................X.......X..............................
.............................X.X.....X.X.....................X.X.....X.X.............................
............................X...X...X...X...................X...X...X...X............................
...........................X.X.X.X.X.X.X.X.................X.X.X.X.X.X.X.X...........................
..........................X...............X...............X...............X..........................
.........................X.X.............X.X.............X.X.............X.X.........................
........................X...X...........X...X...........X...X...........X...X........................
.......................X.X.X.X.........X.X.X.X.........X.X.X.X.........X.X.X.X.......................
......................X.......X.......X.......X.......X.......X.......X.......X......................
.....................X.X.....X.X.....X.X.....X.X.....X.X.....X.X.....X.X.....X.X.....................
....................X...X...X...X...X...X...X...X...X...X...X...X...X...X...X...X....................
...................X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X...................
..................X...............................................................X..................
.................X.X.............................................................X.X.................
................X...X...........................................................X...X................
...............X.X.X.X.........................................................X.X.X.X...............
..............X.......X.......................................................X.......X..............
.............X.X.....X.X.....................................................X.X.....X.X.............
............X...X...X...X...................................................X...X...X...X............
...........X.X.X.X.X.X.X.X.................................................X.X.X.X.X.X.X.X...........
..........X...............X...............................................X...............X..........
.........X.X.............X.X.............................................X.X.............X.X.........
........X...X...........X...X...........................................X...X...........X...X........
.......X.X.X.X.........X.X.X.X.........................................X.X.X.X.........X.X.X.X.......
......X.......X.......X.......X.......................................X.......X.......X.......X......
.....X.X.....X.X.....X.X.....X.X.....................................X.X.....X.X.....X.X.....X.X.....
....X...X...X...X...X...X...X...X...................................X...X...X...X...X...X...X...X....
...X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.................................X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X...
..X...............................X...............................X...............................X..
.X.X.............................X.X.............................X.X.............................X.X.
Enter fullscreen mode Exit fullscreen mode

Image Output

Here's a graphical renderer for the same grid implementation.

#r "nuget:SixLabors.ImageSharp"
open SixLabors.ImageSharp;
open SixLabors.ImageSharp.PixelFormats;

let cols = 501;
let rows = 250;

let image = new Image<Rgba32>(cols, rows);
let white = new Rgba32(255F, 255F, 100F, 1F);
let black = new Rgba32(0f, 0f, 0f, 1F);

let grid =
    generateStandardFirstRow cols
    |> generatePattern rule90
    |> Seq.take rows

let withIndexes x = x |> Seq.mapi (fun index item -> (index, item))

for (rowIndex, row) in withIndexes grid do

    for (cellIndex, cell) in withIndexes row do

        let colour =
            match cell with
            | Full -> black
            | Empty -> white

        image.[cellIndex, rowIndex] <- colour

image.Save("rule90.png")
image
Enter fullscreen mode Exit fullscreen mode

Rule 90

Rules

So far we've looked at a few specific rules. But how many rules are there and can we generate them dynamically? We've hardcoded rules as functions

let rule222: Rule = function 
    | (Full, Full, Full) -> Full
    | (Full, Full, Empty) -> Full
    | (Full, Empty, Full) -> Empty
    | (Full, Empty, Empty) -> Full
    | (Empty, Full, Full) -> Full
    | (Empty, Full, Empty) -> Full
    | (Empty, Empty, Full) -> Full
    | (Empty, Empty, Empty) -> Empty
Enter fullscreen mode Exit fullscreen mode

All rules must return a value for each pattern. Because the patterns are static we could think of identifying rules by what they return for each case, what is on the right hand side of the ->. We could think of the above rule as:

(Full, Full, Empty, Full, Full, Full, Full, Empty)
Enter fullscreen mode Exit fullscreen mode

So a rule is a identified as a list of 8 boolean values. If we use binary to represent this we need a byte (8 bits) of information. This means there are 2^8 rules, giving us 256 possible rules in the Wolfram automata system.

So there are only 256 rules in this Wolfram automata system, and the rule's name determines what it returns. This is illustrated below. The binary pattern maps 1 to Full and 0 to Empty.

128 64 32 16 8 4 2 1 Written Out Rule
1 1 0 1 1 1 1 0 128 + 64 + 16 + 8 + 4 + 2 + 1 = 222
0 1 0 1 1 0 1 0 64 + 16 + 8 + 2 = 90 
let generateRule(ruleNumber: byte) = 
    let ruleBitString = Convert.ToString(ruleNumber, 2).PadLeft(8, '0');

    let patternToBitStringIndex = function 
        | (Full, Full, Full) -> 0
        | (Full, Full, Empty) -> 1
        | (Full, Empty, Full) -> 2
        | (Full, Empty, Empty) -> 3
        | (Empty, Full, Full) -> 4
        | (Empty, Full, Empty) -> 5
        | (Empty, Empty, Full) -> 6
        | (Empty, Empty, Empty) -> 7

    let ruleFn (cells: Cell * Cell * Cell) = 
        let bitIndex = patternToBitStringIndex cells

        match ruleBitString.[bitIndex] with
        | '0' -> Empty
        | '1' -> Full
        | _ -> raise (Exception("Unexpected input"))

    ruleFn

let rule254 = generateRule(254uy)
rule254 (Empty, Empty, Empty)
Enter fullscreen mode Exit fullscreen mode

And there we have it, our rule function generator. Here are some interesting rules.

Rule 62

Rule 62

Rule 110

Rule 110

Rule 150

Alt Text

Conclusion

F# is a perfect language to implement Cellular Automata. The type system allows us to exactly model the domain, and sequences make the implementation elegant. There's no confusing cruft in our code. From this basic implementation you can easily make modifications to the Cellular Automata system. Here's a few fun things to try out. What if ...

  • The first row was randomly generated
  • Cells could have a value other than Full or Empty?
  • Rules incorporated some degree of randomness when deciding the value of the next cell?
  • The grid was hexagonal rather than square based?

The Jupyter Notebook and an F# project containing the code for this post is available here.

This is part of F# Advent Calendar 2020. Check out other posts here.

Further Reading

Top comments (0)

Read next

dotnetfullstackdev profile image

You should know these different execution types in LINQ before writing in C#

DotNet Full Stack Dev -

clickit_devops profile image

Why .NET for Cloud Native Development? Exploring .NET 8 & .NET Aspire ☁️

ClickIT - DevOps and Software Development -

vizzv profile image

Building a Real-Time Chat Application with .NET Core 7 and SignalR

Vishw Patel -

aldo_hernandez_35dcf62348 profile image

Link Many To Many entities with shadow join-table using Entity Framework Core

Aldo Hernandez -