# 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