## DEV Community is a community of 550,319 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Cellular Automata in F#

Logan Mortimer Originally published at isthisit.nz ・8 min read

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

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
.?.....        ..?....        ...?...        ....?..        .....?.
.......        .......        .......        .......        .......
.......        .......        .......        .......        .......
``````

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

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 `Cell`s 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
``````

## 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
)
``````

So

``````generateStandardFirstRow 7
``````

Gives us

``````Empty Empty Empty Full Empty Empty Empty
``````

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 `Cell`s into groups of 3 `Cell`s, 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
}
``````

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

Now we can generate the grid!

``````let firstRow = generateStandardFirstRow 101
let rows = generatePattern rule222 firstRow |> Seq.take 10
``````

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
``````
``````..................................................X..................................................
.................................................XXX.................................................
................................................XXXXX................................................
...............................................XXXXXXX...............................................
..............................................XXXXXXXXX..............................................
.............................................XXXXXXXXXXX.............................................
............................................XXXXXXXXXXXXX............................................
...........................................XXXXXXXXXXXXXXX...........................................
..........................................XXXXXXXXXXXXXXXXX..........................................
.........................................XXXXXXXXXXXXXXXXXXX.........................................
``````

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

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

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

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

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

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

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