Thursday, December 25, 2014

Single Rotation rule with frame interpolation

A frame from the interpolating simulator.

TL;DR: See the online simulator of the Single Rotation cellular automaton, with interpolation of individual cell movement. frames. Its primary purpose is a nice visual effect, for experiments with reversible cellular automata see online simulator, described in the previous blog post.

In case it is not working for you (Since it is HTML5 canvas application, I did not pay much attention to the old browser support), here is a demonstration video.

Single Rotation rule is a very simple reversible cellular automaton that acts on a grid of cells, that are either dead (0) or alive (1). On each generation, the grid is divided into 2x2 blocks, and if the block contains exactly one alive cell, it is rotated by 90°. Thus "single rotation".

Cell tracking

Single Rotation rule preserves total number of the alive cells. Moreover, from the definition of the rule it is clear that it is possible to track the position of every individual alive cell (something that is impossible in the Conway's Game of Life, where cells born and die but not move). The simulator implements this idea.

Few frames of the symmetric long-period oscillator.

Interpolation

On each generation, alive cells always move by 1 grid unit in some direction, making animation jerky. To make it smoother, this simulator interpolates intermediate coordinates of the cells, using Lanczos resampling.

Oscillation filtering

A single cell in the "Single Rotation" rule would constantly rotate with period 4. To make animation less annoying, a possibility to filter higher frequencies of the cell movement is added: "filter" setting. For example, when "filter" setting is 4, every oscillation with period 4 or less is replaced by the constant average value, and rotating cells visually stand still. Higher filter setting allow to cease oscillations of higher period. This is also done by Lanczos filter. Note that computational complexity is proportional to the the filter setting.

More information

Here are some of my other pages, where you can find information about the reversible cellular automata and Single Rotation rule.

Source code and license

Source code is available on Github, under the permissive MIT license. It is written in CoffeeScript.