Cellular Automata pattern of the month

Go back to MCell Home

Cellular Automata have two visages. They are a scientific tool, and an artistic medium. I'll try to expose both sides of Cellular Automata on this page. Each month I'll put a new pattern here that made me thinking for a while, or enchanted (hypnotized?) me with its beauty, or both. Click on the thumbnail to see the enlarged picture of the pattern. Click on the pattern name to load it to MCell and run it. If you didn't install MCell, you can still enjoy the described rules in the MJCell Java applet and in the Cellular Automata gallery.

I hope that you will help me in keeping this page interesting. If the patterns you'd like to submit here can be loaded to MCell, please include their source version, plus optional bitmaps. You can also vote for any existing patterns from any CA libraries, if you want. It would be nice if you mentioned why those patterns attracted your attention.


June 2000

Brian Prentice, the author of the wonderful fractals gallery and of the Snake rule proposed a nice puzzle for the Star Wars rule. He took the common in Star Wars still life objects that support runners and constructed many different railroads. An example of such a railroad is shown in the picture (note the train in the SW part of the pattern.) The train is running up along the railroad. When it reaches the N edge it starts moving down, and finally enters the "inner" part of the figure at the S edge. Brian asks: is it possible to construct crossings and switches so that the train's route can change? I suppose it should be possible using Star Wars' guns.

It's very interesting to see other railroads created by Brian. They can be found at his site or in the updated patterns package for MCell 4.


May 2000

Billiard-ball machines (BBM) is a fascinating CA rule that at first seems hardly to be possible to be defined in  a classic range-1 Moore neighborhood. And indeed it's impossible - a very special partitioning scheme has been defined for implementing this and several other rules - a Margolus neighborhood. A good discussion about various BBM rules can be found at Lotus Artificial Life.

Billiard-ball machines rule has been defined by Edward Fredkin and was first published in 1987 in famous Cellular Automata Machines by Toffoli and Margolus.

Click on the picture to the left (or here) to see a short animation of the BBM rule. The animation shows 2 typical objects in the rule - balls being composed of at minimum two active cells and walls being made of at least four cells groupped in 2x2 blocks.


April 2000

The pattern of this month belongs to one of less explored CA families - Larger than Life (LtLife). Rules in the family check for neighbours in bigger ranges, up to 10 in MCell's implementation. The larger distance results in exciting, very original behaviour of cells.

One of noble representatives of the family, Bugs, was discovered by Kellie Evans while exploring LtLife phase space on the CAM8 cellular automaton machine. The rule works in R5 extended Moore neighbourhood; cells with the total count of live neighbours between 34 and 58 can survive; empty cells with 34 to 45 neighbours turn alive. It's a seriously endangered species in the crowded environment of the rule's characteristic dynamics. The rule features various bugs, often very amusing. Some of them (like Bosco) even are able to turn while traversing the space!


March 2000

WireWorld is one of the oldest and well explored Cellular Automata rules. The automaton was designed by Brian Silverman and was included in his program PHANTOM FISH TANK in 1987. A. K. Dewdney publicized WireWorld in his "Computer Recreations" column (Scientific American, January, 1990).

Cells in WireWorld have one of four possible states: background (0), electron head (1), electron tail (2), and wire (3). The rules for updating cells are:
- background (0) always remains background.
- electron head (1) always changes to electron tail.
- electron tail (2) always changes to wire.
- wire (3) changes to electron head if one or two of its neighbours are electron heads.

These simple rules allow fairly complicated logic circuits to be constructed. The fascinating pattern presented to the left comes from an excellent "Cellular" package by dr J. Dana Eckart (http://www.cs.runet.edu/~dana/index.html ). It was created by one of Dana's students. Starting with version 4 MCell is equipped in a large number of WireWorld patterns.


February 2000

2000_02_dib02_s.gif (5660 bytes)
Digital Inkblots.mcl
Jason Rampe has explored an interesting version of the classic Rudy Rucker's Rug rule with 9 cells neighbourhood and the increment of 3. It turns out that these parameters produce really amazing results! Jason named this rule Digital Inkblots. Most of the patterns go through stages of relatively small changes for a while and then suddenly hit a chaotic stage that usually spreads out destroying the previous stable state and creating a new stable (but more complicated) phase.
The visual effects depend very much to the color palette used. Best palettes seem to be shaded bands of colors, i.e. black=>white=>black=>white or black=>any color=>black=>any color etc. Shaded palettes without the black fade-out bands do not give as nice effects.

See more pictures of Digital Inkblots: pic1, pic2, pic3, pic4, pic5


January 2000

2000_01_s.gif (921 bytes)
Spaceship c7.lif
Back to the roots...

David Eppstein (http://www.ics.uci.edu/~eppstein/) has just found the first period 7 spaceship in Conway's Game of Life. The speed of the ship is 2c/7 - the spaceship travels 2 cells every 7 cycles. According to Stephen Silver, David's discovery is the first new velocity for four years.
The spaceship is relatively small, so it's really surprising why it needed 30(!) years to be discovered...


December 1999

1999_4352_s.gif (2127 bytes)
Ebb&Flow is a rule discovered by Michael Sweney. I remember when I first looked at this rule I thought "Mhm... just another chaotic exploding rule." I couldn't be more wrong! Michael soon sent me patterns designed for the rule that show that it has an amazing tolerance for the creation of stable complex effects. Check the Michael's patterns!

Here is a very original oscillator - an example of how the plane can be tiled in this rule with blinkers. The timing of the blinkers is up to the designer with the constraint that neighboring orthogonal blinkers can not be in the same generation. In this example Michael created a "random" effect (sequential movement illusions get boring after awhile!)

Click on the picture to see the oscillator as an animated GIF.


November 1999

1999_4042_s.gif (474 bytes)
Hex gliders.mcl
The pattern of this month illustrates how powerful and easy to implement are hexagonal CA. The pattern shows 6 gliders sent in a loop using 6 reflectors. This particular hexagonal rule, "Hexrule b2o", was designed and explored by Paul Callahan. It is symmetric (not totalistic) with 2 states. Note that hexagonal rules do not necessarily have to be played on a hexagonal lattice. A simple way to emulate a hexagonal grid is to use the Moore neighborhood omitting two opposite diagonal corners, what is especially easy to do in MCell in Weighted Life rules family.
"Hexrule b2o" has many properties associated with Life: gliders, reflectors, oscillators, still life, duplicators, reflectors, etc. It's also missing some features, for example it's not chaotic enough - it dies down too quickly.
Paul Callahan designed a number of interesting patterns for the rule. I've converted them to MCell format and made them available here for downloading. I encourage you also to read the original Paul's essay on the rule.


October 1999

1999_38_s.gif (6767 bytes)
"Balloons" rule is a very interesting example of aggregation. It was discovered by Brian Silverman using his "Phantom Fishtank" program. Balloons is implemented in MCell as a rules table.
Balloons is driven by Silverman's Brain rule. If enough firing Brain cells are together, they turn on a permanent firing cell. These permanent firing cells serve as seeds around which more turned-on cells agglutinate. If a turned on cell is entirely surrounded, it changes state, so that one soon gets the effect of cells with membranes. As a final fillip, if there is too much excitement at a cell's membrane, the membrane bursts and the cell goes over to a "dead" state which can slowly be nibbled away by the ever active Brain rule.
The rule plus its description was copied from CelLab by Rudy Rucker & John Walker.


September 1999

1999_3438_s.gif (6767 bytes)
This month's pattern shows one of very surprising features of Cellular Automata - the capability of replicating initial configurations. Replicators occur commonly in the CA space. They are known in both von Neumann and Moore neighbourhoods.
Perhaps the best known replicator is the "Fredkin" (13579) rule in the "Vote" family found by Edward Fredkin. It's a totalistic rule. After 32 steps every starting pattern is replicated 9 times. The patterns keep self-replicating and soon the whole universe is covered with stamps of the initial pattern. There exist also replicators in other families of rules. The "Replicator" rule (1357/1357) in the "Life" rules family creates 8 copies of initial configurations. "Fredkin2" and "Fredkin3" rules are implementations of the Fredkin rule in the von Neumann neighbourhood. Both create 5 copies of initial configurations, but Fredkin3 is a unique rule: it uses 3 states, and it's period is 27.


August 1999

1999_33_s.gif (6767 bytes)
The pattern of this month combines both beauty and engineering capabilities. It illustrates the Janko Gravner's "Flakes" rule, also known as "Life without Death" (LwoD). The rule, when started  from simple groups of cells usually produces beautiful growing flakes (try for example various filled circles with radius > 20 cells). Often ladder-like formations of cells emerge and travel to infinity.

David Griffeath and Cris Moore noticed that the ladders can be used to construct a universal computer. In fact they proved that thanks to possibilities of turning, stopping and rephasing ladders  the rule is P-complete. The updated MCell 2.20 library of patterns will contain illustrations of all basic operations on ladders.


July 1999

1999_32_s.gif (14670 bytes)
Yin Yang Fire
This month's pattern illustrates the Yin Yang Fire Cellular Automaton, discovered by Jack Ruijs.
Yin Yang Fire (YYF) is a new cellular automaton that exhibits very complex chaotic behaviour and even shows beautiful fractal-like structures. The whole automaton is a very dynamical system with appearing and disappearing structures in a seemingly ever-changing fashion.
The algorithm behind the Yin Yang Fire rule is very simple and can be described in one clear sentence, however the algorithm will not be revealed until more research has been done on it's significance.

For more details about the rule refer to the Yin Yang Fire home page. Note that the page contains also a YYF mpeg animation that was shown in MTV's program Top Selection on June 10th 1999.

June 1999

1999_31_s.gif (515 bytes)
Guns of all periods.mcl
The relatively new "Star Wars" rule has exceptional patterns-creating capabilities, what was clearly shown by Stephen Silver. The pattern of this month shows how simple is the construction of a universal gun with any period > 5 (the construction is simple, not the process of designing it...). Note that it's also easy to create irregular guns! Here is the original recipe from Stephen:
"To construct a gun of period n > 5 do the following:
  • Choose a positive integer m such that 6(m+1) is a multiple of n. For example, you can always choose m=n-1, but a smaller choice of m is possible if n is a multiple of 2 or 3.
  • Make the still life consisting of m 5-cell crosses joined in a row.
  • Place 6(m+1)/n 3-cell "runners" around the edge of this still life, spaced n generations apart.
  • Add the other two still lifes in the manner shown in the examples."

Does any other automaton exist, where a universal gun can be created with such a small number of cells?

May 1999

1999_30_s.gif (4188 bytes)
This pattern was created using the "Fireworks" rule by John Elliott. "Fireworks" is one of the most beautiful rules I've seen so far. It produces interesting results from both random and prepared initial states. Even several cells scattered over the lattice will produce long-running ravishing pictures. John discovered the rule using his own Webside CA Java applet.

Load the included Cross.mcl pattern and watch it running for at least several minutes. You'll soon understand why I prize the rule so high. I suggest that you use the "MCell Standard" color palette.

April 1999

1999_29_s.gif (4188 bytes)
Day & Night.lif
"Day & Night" is one of the most surprising rules in the Life family. Discovered in April 1997 by Nathan Thompson, it has one unique property: this property is that the rule is symmetric with respect to ON and OFF cells. That is, if you take an arbitrary object in this universe, and invert it so that all ON cells become OFF cells, and vice versa, then the inverted object has the same evolution as the original object, except for the inversion.
The properties of the rule were in-depth explored by David Bell.

This  Night & Day rule property can be best observed on the included pattern Day & Night.lif. Note that the moving cells in the big red area are in fact holes in the solid block of cells.


Webmaster: Mirek Wojtowicz

globe http://www.mirekw.com

MCell mirrors:
globe USA  http://psoup.math.wisc.edu/mcell/
globe Europe  http://www.mirwoj.opus.chelm.pl

Last update: 5 Dec 2000