Grids  Grids     Algorithmic Art  Algorithmic Art       Root  Radical Art        

Two-Dimensional Cellular Automata

(Detail; click for complete image.)

Béla Julesz: Computer Graphic, 1965.

Julesz used random black & white grids in his psychological research on stereopsis. The piece illustrated here looks as if it may have been derived from such a random pattern by one or two applications of a simple voting rule. Julesz displayed this piece in an early computer art show (Howard Wise Gallery, New York, 1965), though he denies any artistic intention.

Assignment [Art History students]: Reconstruct the 1965 show by Kenneth Knowlton and Béla Julesz at the Howard Wise Gallery. Find descriptions of how this piece (and other, similar pieces) came about.

Assignment [Computer Science students]: Experiment with Cellular Automata which yield this kind of pattern from a random initialization. Devise tests which characterize this kind of pattern and apply them to the results of the Cellular Automata.

John Conway: The Game of Life, 1970.

A simple but cleverly designed voting rule generates complex dynamic patterns in a black & white square grid.

Martin Gardner: The fantastic combinations of John Conway's new solitaire game "life", Scientific American 223 (October 1970), pp. 120-123.

Gary W. Flake: The Computational Beauty of Nature (Cambridge, Mass.: MIT Press, 1998). [Choose "Conway's game of life" in the menu on the Java-Applets page.]

Lambert Meertens and Leo Geurts: Kristalstructuren, 1970.

Kristalstructuren ("crystal structures") is a family of algorithms which all use majority voting. Some of them use larger neighborhoods than the immediately adjacent cells. The update regime is incremental: cells are updated one by one.

L.J.M. Geurts: Kristalstructuren, een experiment in computer-kunst. Amsterdam: Stichting Mathematisch Centrum, 1973. (Vacantiecursus Abstracte Informatica.)

Peter Struycken: FIELDS, 1979/1980.

FIELDS uses a square grid with 8-bit color cells. Update-rule: the color of a cell adapts in the direction of the average color of the surrounding cells. Repeated application of the rule thus ends with a uniformly colored surface. But before this stable endpoint is reached, the automaton goes through a sequence of configurations of irregular shapes.

Stephen Wolfram: Articles on Cellular Automata, 1983-2002

An automaton generating snowflake-shapes on a grid with hexagonal cells.
(From: A New Kind of Science, 2002.)

Paul Coddington and Enzo Marinari: Visualizations of spin models, 1993

Antiferromagnetic triangular lattice
Ising model (detail)

Antiferromagnetic triangular lattice
Potts model (detail)

O(3) vector spin model

Michael Creutz: XToys, 1995.

Ising Model

16 State Potts Model


The interactions between the spin directions in neighboring atoms of ferromagnetic and antiferromagnetic materials can be nicely modelled by certain versions of cellular automata – though they can not be captured by the basic one-layer automaton where all cells are updated simultaneously by the same update rule at each time step. Simultaneous update of neighboring cells can be avoided by doing all updates sequentially (as in Meertens & Geurts (1970), mentioned above), or by imposing an update regime which alternates between "even" and "odd" positions in the grid. Toffoli & Margolus (1987) use the latter approach and discuss spin modelling in detail.

The visualizations by Coddington & Marinari were created by efficient algorithms which maintain descriptions of regions of cells with identical-looking neighborhoods.

J. Apostolakis, P. Coddington & E. Marinari: "New SIMD Algorithms for Cluster Labeling on Parallel Computers" International Journal of Modern Physics C, 1993.

Michael Creutz: "Deterministic Ising Dynamics," Annals of Physics 167 (1986), pp. 62-76.

Michael Creutz, "Xtoys: cellular automata on xwindows," Nuclear Physics B (Proc. Suppl.) 47 (1996), pp. 846-849.

Tommaso Toffoli and Norman Margolus: Cellular Automata Machines. A New Environment for Modeling. Cambridge, MA.: The MIT Press, 1987.

David Griffeath: Primary Soup Kitchen, 1994-1998

Turbulence in a Cyclic Cellular Automaton, 1994

Soap Bubble Clustering of a Plurality Vote Rule, 1994

Brian P. Hoke: Cellular Automata and Art, 1996.

The 'stepping stone' rule: First, choose a number between 0 and 1; this will be the update probability for all cells. At every time step, generate a random number between 0 and 1 for every cell. If the number is lower than the update probability, the color of the cell changes to that of one of its neighbors (selected uniformly at random). (The neighbors are defined here as the four orthogonally adjacent cells: north, east, south, west.)

Left: the initial condition: 256 colors distributed randomly. Right: the result of applying the rule repeatedly.



Erwin Driessens & Maria Verstappen: IMA Traveller, 1998/1999.

A recursive cellular automaton. At every time-step, every cell is split into 4 cells. The colors of the newly generated cells are probabilistic variations on the color of the "mother-cell" and the colors of the neighboring cells.