jimmyff

Fun loving creative (he/him) πŸ³οΈβ€πŸŒˆ

17Jul 17

The many beautiful worlds of Cellular Automata

(I've also posted this article over on Medium.)

I've been interested in Cellular Automata (such as 'Conway's Game of Life') for years. I've implemented them countless times in various programming languages. A couple of weeks back I created a Dart library for exploring playing with Cellular Automata, it's open source and available on Github. You can browse the demos on github or see the library running on my personal website -the gifs on this article were also generated using the library.

GIF

What are Cellular Automata?

Cellular Automata were all the rage in Science and Math clubs back in the 70s & 80s however the first papers on the subject actually date way back to the 40s. In those days mathematicians & scientists created the rules using pen and paper rather than a computer (John Conway actually created his 'Game of Life' rules on a Go board!). Stephen Wolfram wrote numerous papers on the subject in the 80s & 90s.

A Cellular Automaton is a grid of 'cells', each of which has a single 'state'. For each cycle (known as a new 'generation') a set of rules are applied to each cell in the grid which could potentially change it's state. The rules usually consider each of the cells 'neighbourhood' (the surrounding cells). Cellular Automata rules are usually incredibly simple. Below are the rules to 'Conway's Game of Life' (here is my library's code implementation):

  • Any living cell with fewer than two live neighbours dies, as if caused by underpopulation.
  • Any living cell with two or three live neighbours lives on to the next generation.
  • Any living cell with more than three live neighbours dies, as if by overpopulation.
  • Any dead cell with exactly three live neighbours becomes a living cell, as if by reproduction.

GIF

'Conway's Game of Life' (among many other rules) can be described as Turing-complete, meaning they can perform computations (if the necessary cell states are in particular formations β€” like this). Wire World is another incredibly simple rule that allows the simulation of electronic logic elements β€”the 80s equivalent of Minecraft's redstone circuits!

What fascinates me is that from such a simple set of rules, complex systems can arise. Often stable groups of cells occur and large complex formations that can even move as a single unit. Reoccurring patterns arise that can span numerous generations (there's a simple 3 generational pattern in the header graphic). I find this aspect of Cellular Automata so exciting -you never know what you are going to see. It's as if we're simulating a very basic universe. What would happen if rather than a very simple 2D grid of cells, we simulated protons, neutrons & electrons? Would we also see complex structures appear; or even simulated life? (aside: Simulation hypothesis)

The Dart library

The library separates the Cellular Automata rules (the fun bit) from the boilerplate processing & rendering. This makes it quick & easy to add new rules or experiment. I've added a few rules so far and also added support for 'MCell' rules so it can run any of the hundreds of rules published in the MCell rules Lexicon. I plan to add the ability to have numerous rule sets running in the same scene although this feature will have to wait for a rainy day. The rendering code is also decoupled which means you can easily add/swap renderers as you need, I've already added a few (WebGL, Canvas, Html) and I plan to add another that can drive an LED Matrix.

GIF

The dart package 'cellular_automata' is published on pub.dartlang.org. Have fun with it and don't forget to send me a pull request! ;-)