Wednesday, December 5, 2012

hex life and sandpiles

As I mentioned in a previous post, I've been meaning to learn more about cellular automata. Maybe in preparation for more formal learning, or maybe instead of it, I've been playing around with some simple examples.

Another Hex Life Critter
The classic cellular automata example is Conway's Game of Life. One thing I've been playing with here is using a grid based on hexagonal-close-packed circles instead of the usual squares.

Although this hex life is not as exciting or explosive as the standard square grid Game of Life, it does yield some nice stable patterns and oscillators (in the earlier post I mentioned some windmills and blinking diamonds). The picture at the top of this post is of another formation that includes a repeating 3-cycle.

Reasoning out why a pattern stays, decays, or oscillates reminds me of playing MineSweeper, without the explosions. For a given pattern, look and see how many "live" cells are around each cell, and decide whether or not that cell will stay the same or change state, based on the rules.

The standard Game of Life rules, used here, are:
  1. Any live cell with fewer than two live neighbours dies, as if caused by under-population. (Starvation)
  2. Any live cell with two or three live neighbours lives on to the next generation. (No Change)
  3. Any live cell with more than three live neighbours dies, as if by overcrowding. (Overcrowding)
  4. Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction. (Birth)
There are lots of other rules that give interesting patterns - sandpiles, for example.

Hex Sandpiles
I learned about these from a recent post on Math Munch. Unlike the standard Game of Life, sandpile cells have many states - not just dead or alive. The pictures below show some sandpiles on a hexagonal grid where there are six states, state 0 is black, state 6 is white, and states 1-5 are shades of grey.

Initially, all cells in the sandpile have state 0 (no grains of sand in that cell). One particular cell, the center of the sandpile, keeps having its state incremented (sand is pouring onto that cell). The key rule for sandpiles is that once a cell reaches its maximum state (full of sand) it spills out into its neighbours: once a cell reaches state 6, it gets reset to state 0 and all its six neighbours have their state incremented by 1.

This leads to a symmetric growing pattern that, when done on a hexagonal board, creates patterns that look like snowflakes. What is interesting to watch with these is that things can progress quite slowly until suddenly the whole pile can get into a state where there are cascading changes as waves of "sand" ripple through the whole pattern.

Here are some examples of the sort of things you'll see while watching sandpiles grow (on the white background below, state 0 is white and state 6 is black):