Elementary Cellular Automata Explorer

As a by-product of struggling to implement this paper myself, I wrote a very fast, interactive elementary cellular automata visualizer (code) using HTML5 canvas and some bit of javascript. In this post, I'll share some ideas behind the implementation.

Looking (2k)^2 cells of rule 54

Hashlife

 Hashlife is a well-known algorithm for running Conway's Game of Life (simply Life) exponentially faster than usual stepping. I'll not go into details since there's already an well-written article, but still provide very basic concept. Basically, hashlife represents the universe by a quadtree, whose nodes are re-used heavily. In fact, there are no two nodes that shares the same pattern.

Each node also has an additional reference to a node, representing the state after steps proportional to the node size.

Spatio-temporal Visualization

It's relatively straightforward to adapt hashlife to ECA. Just replace quadtree with binary tree and we're done.

But in many cases, simply running CA is not enough; it needs to be visualized. In case of Life, whose space is 2D, commonly used visualization is 2D spatial image at specified timestamp. Using the hashlife quadtree, generation of such image is easy. Since each quadtree node occupies 2^n×2^n spatial region, we can attach an image to the node. The image can be constructed by combining the 4 children (nw, ne, sw, se) of the node. No need to consider temporal aspects at all.

Space-time structure of Hashlife

However, in case of ECA, 1D spatial × 1D temporal image like the top figure is more desirable. At first this seems easy, but it's not. (at least to me)

Space-time region completely determinable by a single node actually looks like the triangle like below.

Space-time region of a node and its children 

A node has 3 natural children (left, right, next), but the central region cannot be constructed easily, so simply combining the children doesn't work.

An alternative is to take the rectangular sub-region, and divide it into four like below. The nodes corresponding to the quadrants are shown in color.

Left: Natural node children  Right: Quadrants and necessary nodes

Although not trivial, they can be constructed by composing grandchildren. Here, construction of the blue node is shown:

 blue = combine(  
  combine(node.left.left.right, node.left.right.left),  
  combine(node.left.right.right, node.right.left.left))  

(for other nodes, see getSTDivision() in the source code)

At this point, it's just the same as the hashlife case.

Gallery

Rule 30: although worst case for hashlife, class 3 (chaotic) works well enough

Rule 90 (contrast adjusted): spanning 1.5M cells horizontally

You can try the Elementary Cellular Automata Explorer at http://www.xanxys.net/ecax/.

Fiat Lux

I'll write about artificial life and such, starting from bonsai.

bonsai r6

I've always been thinking, existing evolutionary systems are too simple in their environments (or physics). Granted, super simple and abstract rules can result in complex and interesting phenomena (class 4 in Stephen Wolfram's terms).

The problem is, such game-theoretic phenomena are hard to notice and often completely useless outside that specific system. What I want to see is phenomena or morphology worthy of bio-mimicry.

Now the real challenge arises; how to achive such system. Ideal solution would be to create atomic scale system and pour in massive human and computation resource. (i.e. creation of autoverse in Permutation City) In real life, it's not feasible to create such system and wait until whole ecosystem of living things emerges; we need to pick a specific kind of life and tune everything to make them survive.

Plants seem good choice for a few reasons:

1. No brain (fast iteration)
2. Human-scale (obeys familiar physics)

In the first few iterations of bonsai, I was actually targetting recreation of embryogenesis at maybe somewhat reduced scale and even watched some online lectures on cell biology and plant biology (also, bonsai is written in C++ at that time). But it became gradually apparent that tuning such system so that something remotely similar to what we call plant to sustain is extremely difficult and fruitless. Simply put, we don't have enough real-world data to tune many parameters. Also, it'd be extremely fragile (from lack of computation resource), so no interetsting evolution will occur.

This is why I switched to more light-weight, artificial design approach. In bonsai's current state (r6), the following aspects are simulated.

• oragan-level morphogenesis based on some coding system (genome)
• downward lighting and photosynthesis
• asexual replication with genome mutation
• pseudo mechanical simulation (just a bunch of sanity checks on shape)

It starts off with 9 identical genome, and for most of the time, they die away. However, some plants do look good (to my eyes) and survive for fair amount of time, so I'm thinking total population is too small. Next revision will have re-written light simulator with accelerated ray tracing.