Conference rusure::math

1126.0. "Gerhardt Schuster Cellular Automaton" by DRUMS::FEHSKENS () Tue Sep 19 1989 12:33

    I recently implemented the Gerhardt-Schuster cellular automaton
    described in the Computer Recreations column in Scientific American
    (I think it was the August 1988 issue).  This cellular automaton,
    called the "hodgepodge machine" in the article, simulates those
    chemical reactions that produce waves of color changes when confined
    to a plane (e.g., in a filter paper disk).
    
    The problem is my program has a bug that I can't find.  The article
    is not complete in its description of the algorithm, and I wondered
    if anybody else had implemented this automaton and what their
    experience was.
    
    The idea behind the automaton is that a cell can be "healthy"
    (state = 0), "infected" (1 < state < n) or "ill" (state = n).
    The state transition rule depends on the cell's current state:
    
    	if healthy,  the next state is  floor(a/k1 + b/k2)
    	if infected, the next state is  min((floor(s/a) + g), n)
    	if ill,      the next state is  0 
     
    k1, k2, g, and n are parameters that characterize the automaton.
    The examples cited by the article use k1 = 2, k2 = 3, n = 100,
    and g is unspecified.
    
    a, b and s are evaluated from the cell's neighborhood:
    
    	a is the number of infected cells in the neighborhood
    	b is the number of ill cells in the neighborhood
    	s is the sum of the states of the cells in the neighborhood,
    	     plus the cell's own state.
    
    What if a = 0, i.e., the cell's neighborhood consists entirely of
    healthy or ill cells?  If the cell itself is infected, (s/a) is
    undefined.  Should ill cells be counted as infected?
    
    What is a reasonable value of g?  The article describes four kinds
    of behaviour as g increases, but provides no guidance as to actual
    values of g.  I assume that the transitional values of g are related
    to the value of n.
    
    I wrote versions using the von Neumann (4 cell, "north, west, east,
    south") neighborhood and the Moore (8 cell, "northwest, north,
    northeast, west, east, southwest, south, southeast") neighborhood.
    In the evaluation of the rule for infected cells, I added the test
    
    	IF a = 0 THEN a <- 1 END IF
    
    I used n = 27 (as I had 28 colors available to represent states),
    and set k1 = 2, k2 = 3 and g = 4, and initialized the cell space
    randomly.  I ran cell spaces of about 100 * 100 cells (actually,
    122 * 104, because the pixels on my Amiga's monitor aren't square,
    and these values produce a square cell space). 
    
    The 4 neighbor case ran ok, but produced "square spirals" rather
    than the smoothly curving spirals depicted in the photographs
    accompanying the article.  The 8 neighbor case runs ok for a while,
    but gradually develops "tumors", small areas of cells with a "salt
    and pepper" state configuration (lots of healthy or ill cells mixed
    up in a quasi-checkerboard pattern with a few intermediate state-valued
    infected cells scattered among them) which slowly grow to take over
    the entire cell space.
    
    I have been over the code for both versions pretty carefully, and
    with the exception of the test for a = 0 mentioned above they conform
    exactly to the algorithm as described in the article (yes, I know,
    famous last words for all programmers).
    
    Has anybody else implemented this automaton and successfully duplicated
    the behaviour described in the article?
    
    len.
      
    	                                                       

        In min((floor(s/a) + g), n), think of s/a as infinite if
        a is 0, so that the min becomes n.  Try it that way and
        see what happens.
        
        Dan

    Hmm, very clever.  I'll try that.
    
    By the way, there's a bug in my description of the rule for healthy
    cells (I did it from memory, known to be a risky proposition); the
    correct rule is
    
    	floor(a/k1) + floor(b/k2)
    
    len.