Monster Crumbs
The 'monster crumbs' shown here are a certain type
of a cellular automata, invented by David Griffeath of the
University of Wisconsin at Madison. I'll assume you're familiar with the
general working principles of cellular automata. The monster crumbs have
the following main features:
- A grid of N times N cells is used. The grid is cyclic, i.e.
the right neighbour of the rightmost cell is the leftmost cell
of the same line an so on.
- Each cell has four neighbours (right,left,top,bottom).
The neighbours of the cell with coordinates [i,j] are
therefore [i+1,j], [i-1,j], [i,j+1] and [i,j-1]. All
additions and subtractions are done modulo N.
- Each cell is in one of S states. Each state is
represented by a different color. The states are cyclic, too.
- The initialization is done by assigning each cell a randomly
chosen state in the range [0,S-1].
- The rules for the simulation are extremely simple: for each
time step, a cell goes from state s to state (s+1) if and
only if at least one of the four neighbouring cells is in
state (i+1). In other words, cells in a certain state 'eat'
their neighbours which are in a state one level below
(remember the states are cyclic, so state 0 eats state S-1).
If a cell eats another cell, it may nevertheless itself
be eaten in the same time step. Of course, all cell changes
are done simultaneously.
Provided here is a simple Java applet which implements the monster
crumbs. You may select the number of states (within a certain
range), the number of simulation steps after which to paint the
current state and the box size. The box size is the size
of the square of pixels which represents each cell. At most you
may have 600 times 600 cells (box size equals 1), but in this case
the simulation is quite slow.
After you've changed one of these settings, click 'init' to
re-initialize the simulation. A click on 'start' starts the
simulation. The 'restart' button re-starts the simulation with
the same cell states as after the last init.
The right-hand side of the graphics area shows the percentage of
cells which changed their states during the last time step. From
top to bottom the last 20 time steps are visualized.
You may notice certain features as the simulation progresses.
Although the initial states for each cell are random choices, there
are four distinct phases during the simulation:
- The initial state of random states for all cells
(example screenshot).
- A phase where some 'germs' or 'seeds' of order are found.
Typically there all also some larger areas of cells within
a single state to be found
(example screenshot).
- A phase of 'crystal defects' where the seeds have grown
significantly and there are few areas of cells in random
states left. This state is meta-stable
(example screenshot).
- A highly ordered and stable state where 'monster crumbs'
are ruling the cellular world. The picture is dominated by
a number of large 'spirals'
(example screenshot).
The reason for this behaviour is quite simple, but I leave it to
you as an exercise ;-)
For an answer, see the article referenced below.
Have fun with it !
Please click here to
start the applet.
Disclaimer: I got the original idea from a article by A.K. Dewdney
in Spektrum der Wissenschaft (October 1989, page 10), the
german edition of Scientific American.
Peter Uelkes
Last modified: Thu May 30 17:15:09 CEST 2002