2014年2月21日金曜日

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



1 件のコメント: