Create patterns using cellular automata
A little history
In the 1940’s, at what is now the Los Alamos National Laboratory (LANL), the mathematician John von Neumann
was working on the problem of sef-replicating systems
, such as those found in biology or cybernetics. At the
same time his friend and colleague at LANL, Stanislaw Ulam
, was studying a related problem of crystal growth.
Ulam was using what today would be called a computer simulation technique. He represented the crystal surfaces
as nodes in a lattice network
and using one of the early computers built for the Manhattan Project, probably
the ENIAC, he observed the changes to the surfaces as the nodes obeyed rules that he imposed on them.
(This is supposition on my part: I have not actually seen any of Ulam’s publications related to this work.)
Ulam suggested to von Neumann that he try a similar computational approach to the study of self-replicating
systems. Von Neumann adopted this approach and gave the concept the name Cellular Automata
(CA). He did
considerable work with CA and in 1966 published a book entitled The Theory of Self-Reproducing Automata.
[A.W. Burks (ed), Univ. of Illinois Press]. In the 1970’s CA surfaced in the popular culture in the form of the
mathematician John Conway’s Game of Life
largely as a result of Marvin Gardner's article in Scientific American:
The Fantastic Combinations of John Conway’s New Solitaire Game ‘Life’
[Sci. Am., 223:120-123,1970].
In the 1980’s considerable work was done on CA by Stephen Wolfram
. The concepts of CA are a central theme
of his book A New Kind of Science
[Wolfram Media, Inc., 2002]. This book contains a complete history
of CA as well as a full exposition of the science and mathematics associated with CA. The rules used to identify
CA that are defined in Wolfram’s book are the rules I have used in my program CA Pattern Maker
. In fact,
Wolfram’s book was in large part the inspiration for the development of this program.
What are Cellur Automata?
The analytical (pencil and paper) way to solve for the state of physical systems undergoing change is to
solve differential equations that assume space and time are continuous quantities.
Computer simulations of these systems, on the other hand, divide space and time into discrete elements.
The elements of space are called “cells” and the elements of time are called “steps”. CA are arrays of cells whose state at a particular time step depends automatically and only on its
own state and the state of its neighbor cells at the previous step. If the CA array is confined to a
line where the neighbors are just the ones to the Left and Right, the CA is said to be one dimensional.
Two dimensional CA arrays can involve just 4 neighbors (North,West,South and East) or all 8 neighbors
including the diagonals (N,NW,W,SW,S,SE,E,NE). In principle the cells within the CA can have any number of states. Von Neumann’s
self-reproducing robots, for example, had 29 states. But the CA cells we are considering here have only 2 states:
dead or alive, empty or filled, white or colored, or, in the usual computer parlance, 0 or 1. The rules that the CA obey as they evolve are
coded as a set of integer numbers according to the schemes defined in Wolfram's
book. I have included a detailed explanation of how the integer codes relate to
the rules imposed on 1D and 2D CA on a separate page.
You can view a collection of CA patterns here
. The captions
for 1D CA patterns give the rule number; e.g., CA161. For 2D patterns, the caption
gives the rule number and number of steps; e.g., CA491_66 which means 4 neighbor
rule 491 run for 66 steps. Patterns using 8 neighbor rules have captions like CA8_174826_200,
meaning 8 neighbor rule 174286 run for 200 steps. Captions where the steps are given
like 46x6 means the pattern was run for 46 steps 6 times in a row (very different
from 276 steps all at once.)
A cross-platform (browser based) version of CA Pattern Maker
has been developed
as a Silverlight application. This version includes printing capability but I have not yet
tried to implement image saving in Silverlight.
The program will operate in any browser equiped with a Silverlight plugin (available
for free, about 7MB).
Operating the Program
You can adjust the settings for the three stages of pattern setup:
You can create your own pallette of colors and/or change
color of the pattern using a color-picker;
You can define how the colors in the pallette are sequenced
through the time steps
required to generate the pattern: randomly, uniformly
with a specified number of
steps per color, using the Fibonacci sequence where the
steps per color progress
through a specified portion of the Fibonacci sequence,
or custom, where you
choose the number of steps for each color in the pallette.
You can choose to generate 1D or 2D patterns or to play
Conway's Game of Life.
You can specify the size of the cells (in pixels) and
the rule number
(code) for the
1D and 2D CA.
3)Initial cell positioning:
For the 1D and 2D CA you can choose to have the
starting cell positioned at the
center, you can manually position any number
of starting cells, or, in 1D, you can randomly position the initial cells.
For the Game of Life you can select among a set
of established starting patterns
or create your own custom pattern.
You then push "Start" to generate: the entire pattern for 1D, the pattern after
number of steps for 2D, or, to begin the Game of Life.