[Arjen Markus] (26 August 2002) A few years ago cellular automata were "in vogue": they formed a new type of mathematical objects that had rather interesting properties. Given a few simple rules, they could exhibit a wealth of structures. The most famous one of all: the Game of Life.

I recently came across them again and concocted this little script. If I remember the rules correctly, it is an implementation of the Game of Life.

''Remark:'' as noted below by [DKF] the rules are definitely not those of Life. However, it is rather dynamic :)

The idea:
   * A cell gets a new state (0 or 1) depending on its own state and that of its neighbours.
   * In the case shown the rules are very simple: count the number of "live" neighbours. If it is even, then the new state of the centre cell becomes 0. Otherwise it becomes 1.

The rules are found in the proc newCellState.

Note: I paid little attention to customisation or presentation. Just watch and be fascinated.

----

 # cellular_automata --
 #    Implement simple two-dimensional cellular automata
 #

 package require Tk

 # displayState --
 #    Display the current state
 # Arguments:
 #    window   Window to update
 #    cells    Cells array
 #    state    State array
 #    nocols   Number of columns
 #    norows   Number of rows
 # Result:
 #    None
 # Side effects:
 #    Display the new state by chnaging the colour of the cells
 #
 proc displayState { window cells state nocols norows } {
    upvar #0 $cells cellId
    upvar #0 $state newState 

    for { set j 0 } { $j < $norows } { incr j } {
       for { set i 0 } { $i < $nocols } { incr i } {
          $window itemconfigure $cellId($i,$j) \
             -fill [lindex {white black} $newState($i,$j)]
       }
    }
 } 

 # calculateNewState --
 #    Calculate the new state
 # Arguments:
 #    window     Window for display
 #    cells      Cell IDs
 #    old_state  State array holding current state
 #    new_state  State array holding new state
 #    nocols     Number of columns
 #    norows     Number of rows
 # Result:
 #    None
 # Side effects:
 #    Set new values in the array new_state
 #
 proc calculateNewState { window cells old_state new_state nocols norows  } {
    upvar #0 $old_state state
    upvar #0 $new_state newState
 
    for { set j 0 } { $j < $norows } { incr j } {
       for { set i 0 } { $i < $nocols } { incr i } {
          set ie [expr {$i+1} ]
          set iw [expr {$i-1} ]
          set jn [expr {$j+1} ]
          set js [expr {$j-1} ]
          set ie [expr {($ie >= $nocols) ? 0           : $ie} ]
          set iw [expr {($iw <  0      ) ? ($nocols-1) : $iw} ]
          set jn [expr {($jn >= $norows) ? 0           : $jn} ]
          set js [expr {($js <  0      ) ? ($norows-1) : $js} ]
          set newState($i,$j) \
             [newCellState $state($i,$j)  $state($iw,$j) \
                           $state($ie,$j) $state($i,$jn) \
                           $state($i,$js) ]
       }
    } 

    displayState $window $cells $new_state $nocols $norows

    #
    # Schedule this routine again - reversed arrays!
    #
    after 100 [list \
       calculateNewState $window $cells $new_state $old_state $nocols $norows ]
 }

 # setUpDisplay --
 #    Initialise the display
 # Arguments:
 #    window     The window used to display the result
 #    cells      Array with cell IDs
 #    nocols     Number of columns
 #    norows     Number of rows
 # Result:
 #    None
 # Side effects:
 #    Set new values in the array cells
 #
 proc setUpDisplay { window cells nocols norows } {
    upvar #0 $cells cellId

    for { set j 0 } { $j < $norows } { incr j } {
       for { set i 0 } { $i < $nocols } { incr i } {
          set iw [expr {10*$i} ]
          set ie [expr {$iw+9} ]
          set js [expr {10*($norows-$j)} ]
          set jn [expr {$js-9} ]
          set cellId($i,$j) \
             [$window create rectangle $iw $jn $ie $js -outline "" -fill white]
       }
    }
 }

 # newCellState --
 #    Determine the new state of a cell
 # Arguments:
 #    state_c    State of the current cell
 #    state_w    State of the cell west of the current cell
 #    state_e    State of the cell east of the current cell
 #    state_n    State of the cell north of the current cell
 #    state_s    State of the cell south of the current cell
 # Result:
 #    New state
 #
 proc newCellState { state_c state_w state_e state_n state_s } {
    set sum [expr {$state_w+$state_e+$state_n+$state_s}]

    switch -- $sum {
    "0" { set result 0 }
    "1" { set result 1 }
    "2" { set result 0 }
    "3" { set result 1 }
    "4" { set result 0 }
    default { set result 0 ;# Should never happen though }
    }

    return $result
 }

 # main --
 #    Steer the application
 # Arguments:
 #    None
 # Result:
 #    None
 # Note:
 #    It is necessary to use global arrays - because of [after]
 #
 proc main {} {
    canvas .cnv
    pack .cnv -fill both

    set norows 30
    set nocols 29

    setUpDisplay .cnv ::cells $nocols $norows

    #
    # Initial condition
    #
    for { set j 0 } { $j < $norows } { incr j } {
       for { set i 0 } { $i < $nocols } { incr i } {
          set ::state($i,$j) 0
       }
    }
    set ::state(5,5) 1

    displayState .cnv ::cells ::state $nocols $norows

    after 100 [list \
       calculateNewState .cnv ::cells ::state newState $nocols $norows ]
 }

 #
 # Start the program
 #
 main
----
''[DKF]'' - This is not the classic rules for Conway's Life.  That uses the eight nearest neighbours (diagonal too), and states that a cell will remain in its current state when it is next to two living neighbours, become/remain alive when it is next to three living neighbours, and become/remain dead when it is next to any other number of neighbours ("overcrowding" and "loneliness", if you will.)

Please see later in this page for Conway in Tcl...

''[DKF]'' - There are other interesting categories of cellular automata.  One of my favourites is "wires" where each cell can be in one of four states:
   blank:   Always remains blank.
   wire:   Becomes a head if-and-only-if next (using 8 neighbours rule) to one or two heads.
   head:   Becomes a tail.
   tail:   Becomes a wire.
This is not quite as dynamic as Life (the rules keep the overall form by-and-large static) but it is computationally complete (note that heads and tails combine to form pulse chains that travel in definite directions):

 "3-cycle Pulse Source"

  H############ ->
  T

 "OR Gate"
 -> #####
         #
        ############ ->
         #
 -> #####

 "INHIBIT Gate"
 -> ########## ####### ->
              #
             ###
              #
 -> ##########
 (The inhibit input)

It's possible to build complex "circuits" using this, though layout is tricky because you have to be very careful about the timing.

----
'''Langton's Ant'''

Langton's Ant is an automaton that wanders around blindly for a while, before getting its act together and heading off determinedly in a particular direction.

To make its life marginally more interesting, this Ant lives on a toroid, so it keeps tripping over its own tracks.

There is some background at [http://mathworld.wolfram.com/LangtonsAnt.html].

 # lant.tcl	Langton's Ant
 
 set size 400			;# pixels per canvas side
 set side 400			;# cells per canvas side
 set cell [expr $size/$side]	;# pixels per cell
 set bgcol yellow
 set fgcol red
 set adir(0) {1 0};set adir(1) {0 1};set adir(2) {-1 0};set adir(3) {0 -1}
 
 catch {destroy .c}
 canvas .c -width [expr $size+1] -height [expr $size+1] -bg $bgcol
 bind .c <Button> {set run 0}
 pack .c
 
 set x [expr int(rand()*$side)];set y [expr int(rand()*$side)];set dir 0;set run 1
 while {$run} {
 	set col [.c itemcget $x,$y -fill]	;# read cell at ant position
 	if {![string length $col]} {		;# create new fg cells on demand
 		.c create rectangle \
 			[set ax [expr $x*$cell+2]] [set ay [expr $y*$cell+2]] \
 			[expr $ax+$cell] [expr $ay+$cell] \
 			-outline $fgcol -fill $fgcol -tag $x,$y
 		set dir [expr ($dir+1)%4]	;# turn right
 	} elseif {[string match $col $bgcol]} {	;# invert bg cell
 		.c itemconfigure $x,$y -outline $fgcol -fill $fgcol
 		set dir [expr ($dir+1)%4]	;# turn right
 	} else {				;# invert fg cell
 		.c itemconfigure $x,$y -outline $bgcol -fill $bgcol
 		set dir [expr ($dir+3)%4]	;# turn left
 	}
 	set x [expr ($x+[lindex $adir($dir) 0])%$side]
 	set y [expr ($y+[lindex $adir($dir) 1])%$side]
 	update
 }
 
Bob Clark

----
'''Langton's Other Ants'''

While reading more about Langton's Ant above, I learned that there are infinitely more and more interesting Langton's Ants.

Langton's First Ant above is named "LR", because it turns Left when it encounters the background colour (turning it foreground), and turns Right when it encounters the foreground colour (turning it background). Langton's Second Ant is "RL", a very close relative that does the same thing in the opposite direction.

There are some redundant Ants, "L" and "R" - these just spin round turning the background to background.

But the other Ants from "LLL" to infinity all do something more or less interesting - some wander then head off like the First Ant, some make random amoebic blobs, some make complex space-filling patterns, others make intricate symmetrical traceries that shimmer with colours - there are definite families of Ants.

I particularly like the Ant called "LLLLLLLLLLLLRRRRRRRRRRRR" - it looks like a brain having thoughts. So does "LLLLRRRR" in fact, but less colourfully.

 #	lants2.tcl	Langton's Other Ants 2
 
 proc runworld {cell cycle directions colours} {		;# track a lant and update the display
 global Config
 	.lants.world delete all
 	set x [expr {$Config(side)/2}]			;# starting position
 	set y [expr {$Config(side)/2}]
 	array set xdir {0 1 1 0 2 -1 3 0}			;# dx per direction
 	array set ydir {0 0 1 1 2 0 3 -1}			;# dy per direction
 	set dir 0						;# 0=0 1=90 -1=3=270 -2=2=180 degrees
 	set noofcols [llength $directions]			;# number of colours from palette
 	while {$Config(.lants.startstop)} {			;# until stop button
 		set inserts [list]				;# list of new cells
 		array unset updates				;# array of distinct updated cells
 		for {set t 0} {$t<$cycle} {incr t} {		;# do a lot of lant cycles
 			if {[catch {set col $cells($x,$y)}]} {	;# new cell required
 				set col 0			;# 0=background
 				lappend inserts $x $y		;# list of new cells
 			}
 			set dir [expr {($dir+[lindex $directions $col]+4)%4}]
 			set col [expr {($col+1)%$noofcols}]	;# change direction, update colour
 			set cells($x,$y) $col			;# array of current cell colour
 			set updates($x,$y) ""			;# array of distinct updated cells
 			set x [expr {$x+$xdir($dir)}]	;# new x
 			set y [expr {$y+$ydir($dir)}]	;# new y
 		}
 		foreach {x1 y1} $inserts {			;# create rectangles for inserts
 			.lants.world create rectangle \
 					[set ax [expr {$x1*$cell+2}]] [set ay [expr {$y1*$cell+2}]] \
 					[expr {$ax+$cell}] [expr {$ay+$cell}] -tag $x1,$y1
 		}
 		foreach xy [array names updates] {		;# paint rectangles for inserts and updates
 			set col [lindex $colours $cells($xy)]
 			if {![string length $col]} {set col black}
 			.lants.world itemconfigure $xy -outline $col -fill $col
 		}
 		update
 	}
 }
 
 proc checkname {} {	;# tidy up the lant name and convert to Config(directions)
 global Config
 	set Config(.lants.name) [string map {" " ""} [string toupper $Config(.lants.name)]]
 	set Config(directions) [string map {L -1 R 1 F 0 B -2} [split $Config(.lants.name) ""]]
 	if {[set l [llength $Config(directions)]]} {
	 	for {set x 0;set i 0} {$i<$l} {incr i} {
	 		if {[catch {incr x [lindex $Config(directions) $i]}]} {
	 			set Config(.lants.name) [string range $Config(.lants.name) 0 [expr {$i-1}]]?[string range $Config(.lants.name) [expr {$i+1}] end]
	 			set Config(directions) [lreplace $Config(directions) $i $i 0]
	 		}
	 	}
	 } else {
	 	set Config(directions) [list 0]
	 }
 }
 
 proc startstop {} {	;# start or stop the lant
 global Config
 	if {$Config(.lants.startstop)} {
 		.lants.name configure -state normal
 		.lants.startstop configure -text Start
 		set Config(.lants.startstop) 0
 	} else {
 		checkname
 		.lants.name configure -state disabled
 		.lants.startstop configure -text Stop
 		set Config(.lants.startstop) 1
 		after 0 [list runworld $Config(cell) $Config(.lants.cycle) $Config(directions) $Config(colours)]
 	}
 }
 
 array unset Config
 array set Config {
	size			400	;#	{pixels per canvas side}
	side			200	;#	{cells per canvas side}
	directions		{-1 1}	;#	{initial =LR}
	colours			{ivory red2 darkorange2 yellow2 chartreuse2 green2 springgreen2 
					turquoise2 dodgerblue2 blue2 blueviolet magenta2 deeppink2 
					red3 darkorange3 yellow3 chartreuse3 green3 springgreen3 
					turquoise3 dodgerblue3 blue3 darkviolet magenta3 deeppink3 
					red4 darkorange4 gold4 chartreuse4 green4 springgreen4 
					turquoise4 dodgerblue4 navy purple4 magenta4 deeppink4}		
					;#	{spectral}
	.lants.name		LR	;#	{initial =LR}
	.lants.cycle		1000	;#	{cell cycles per canvas refresh}
	.lants.startstop	0	;#	{0 when Stopped, 1 when Started}
 }
 set Config(cell)		[expr {$Config(size)/$Config(side)}]  	;# pixels per cell

 wm title . "Langton's Other Ants"
 catch {destroy .lants}
 frame 	.lants					
 entry 	.lants.name		-textvariable Config(.lants.name)	-width 40
 button	.lants.startstop	-text Start	-command startstop
 canvas	.lants.world      -width [expr {$Config(size)+1}] -height [expr {$Config(size)+1}] -bg [lindex $Config(colours) 0]
 pack .lants .lants.name .lants.startstop .lants.world
  
This is a slightly more readable update on the original version, and accepts the letters "F" for forward and "B" for back (directions +0 and -2) - which introduce whole new classes of ants to be exercised.

Bob Clark

----
'''Conway in Colour'''

One more cellular automaton - Conway's Game Of Life from the 1970's - the most-written program after Hello World apparently. There's a lot of background and a true explorer applet at [http://www.math.com/students/wonders/life/life.html]. This is more of a cut-down version, although it does use colour to differentiate the states Birth (yellow), Living (green), Died Cold (blue) and Died Hot (dark red). Press the Start button to kick off a random population and watch it wind down, repeat to taste.

You can also paste an interesting initial pattern into the text box - there's a couple of examples after the program.

 #	conway.tcl	Conway's Life
 
 proc runworld {side cell freq colours toroid delay minb maxb minl maxl updates} {	;# run the world
 global Config
 	foreach xy $updates {set Updates($xy) 1}						;# 1=newborn
 	while {$Config(.main.startstop)} {							;# until Stop button
 		array unset newNs								;# array of new Neighbour xys
 		foreach {xy state} [array get Updates] {					;# for each state change at xy
 			if {$state} {								;# if not 0=empty
 	 			foreach {x y} [split $xy ,] break
 				set newc [lindex $colours $state]				;# new colour
 				if {[catch {set World($xy)}]} {				;# if new cell
 			 		.main.world create rectangle \
 			 			[set ax [expr {$x*$cell+2}]] [set ay [expr {$y*$cell+2}]] \
 			 			[expr $ax+$cell] [expr $ay+$cell] \
 			 			-outline $newc -fill $newc -tag $xy
 				} else {							;# existing cell
 	 				.main.world itemconfigure $xy -outline $newc -fill $newc
 				}
 				set World($xy) $state						;# preserve state in World array
 	  			if {[set incr [lindex {0 1 0 -1 -1} $state]]} {		;# if birth or death event, notify Neighbours (including self)
 	 				foreach {dx dy dv} {-1 1 1  0 1 1  1 1 1  -1 0 1  0 0 0  1 0 1  -1 -1 1  0 -1 1  1 -1 1} {
 			 			set nx [expr {$x+$dx}];set ny [expr {$y+$dy}];set ni [expr {$incr*$dv}]
 			 			if {$toroid} {set nx [expr {($nx+$side)%$side}];set ny [expr {($ny+$side)%$side}]}
 						if {[catch {incr Neighbours($nx,$ny) $ni}]} {set Neighbours($nx,$ny) $ni}
 						set newNs($nx,$ny) ""
 	 				}
 				}
 			 } else {.main.world delete $xy;unset World($xy)}			;# empty cell, tidy canvas and World array
 		}
 		array unset Updates;update;after $delay
 		foreach xy [array names newNs] {						;# for each potential state change at xy
 			if {![set neighbours $Neighbours($xy)]} {unset Neighbours($xy)}	;# tidy Neighbours array
 			if {[catch {set state $World($xy)}]} {set state 0}
 	  		if {$state==0} {							;# 0=empty - may experience birth
 	  			if {($neighbours>=$minb)&&($neighbours<=$maxb)} {set Updates($xy) 1}
 	  		} elseif {$state==1} {						;# 1=newborn - may experience death or continued life
 	  			if {$neighbours<$minl} {set Updates($xy) 3} elseif {$neighbours>$maxl} {set Updates($xy) 4} else {set Updates($xy) 2} 
 			} elseif {$state==2} {						;# 2=living - may experience death
 	  			if {$neighbours<$minl} {set Updates($xy) 3} elseif {$neighbours>$maxl} {set Updates($xy) 4} 
 			} else {								;# 3/4=dead - may experience birth or be emptied
 	  			if {($neighbours>=$minb)&&($neighbours<=$maxb)} {set Updates($xy) 1} else {set Updates($xy) 0}
 		  	}
 		} 
   	}
 }
 
 proc populate {side freq toroid initial} {							;# return list of populated cell xys from text map, or at random
 	if {[string length [string map [list " " "" \t "" \n ""] $initial]]} {
 		set y 0;foreach line [split [string map [list \\n \n \\t \t] $initial] \n] {
 			set x 0;foreach char [split $line ""] {
 				if {$char=="\t"} {set x [expr {($x%8)+8}]} elseif {$char==" "} {incr x} else {set births($x,$y) "";incr x}
 				if {$toroid} {set x [expr {$x%$side}]}
 			}
 			if {$toroid} {set y [expr {($y+1)%$side}]} else {incr y}
 		}
 	} else {
 		for {set i 0;set l [expr {int($side*$side*$freq)}]} {$i<$l} {incr i} {set births([expr {int(rand()*$side)}],[expr {int(rand()*$side)}]) ""}
 	}
 	return [array names births]
 }
 
 proc startstop {} {	;# start or stop
 global Config
 	if {$Config(.main.startstop)} {
 		.main.startstop configure -text Start
 		set Config(.main.startstop) 0
 	} else {
 		.main.startstop configure -text Stop
 		set Config(.main.startstop) 1
 		.main.world delete all
 		after 0 [list runworld $Config(side) $Config(cell) $Config(freq) $Config(colours) $Config(.main.toroid) $Config(.main.delay) \
 				$Config(.main.minbirth) $Config(.main.maxbirth) $Config(.main.minlife) $Config(.main.maxlife) \
 				[populate $Config(side) $Config(freq) $Config(.main.toroid) [.main.initial get 0.0 end]]]
 	}
 }
 
 array unset Config
 array set Config {
 	size			320					;#	{pixels per canvas side}
 	side			80					;#	{cells per canvas side}
 	freq			0.1					;#	{fraction of random births}
 	colours			{black white white black black}	;#	{traditional}
 	colours			{white black black white white}	;#	{modern}
 	colours			{black yellow green blue darkred}	;#	{technicolor}
 	.main.delay		0					;#	{mS delay per cycle}
 	.main.toroid		1					;#	{1 if toroidal world}
 	.main.startstop	0					;#	{0 when Stopped, 1 when Started}
 	.main.minbirth		3					;#	{operating params...}
 	.main.maxbirth		3					;#	{}
 	.main.minlife		2					;#	{}
 	.main.maxlife		3					;#	{}
 }
 set Config(cell)		[expr {$Config(size)/$Config(side)}]  	;# pixels per cell
 
 wm title . "Conway's Life"
 catch {destroy .main}
 frame 	.main		
 button	.main.startstop	-text Start	-command startstop
 canvas	.main.world		-width [expr {$Config(size)+1}] -height [expr {$Config(size)+1}] -bg [lindex $Config(colours) 0]
 text .main.initial 		-font -*-courier-medium-r-normal--*-80-* -width 60 -height 16 -wrap none
 pack .main .main.startstop .main.world .main.initial

''Four Glider Guns'' - paste this into the text box and press Start:

 \n\n\n\n\n\n\n\n\n\n\n\n\n\n
                        ##                       ##                        
                        # #                     # #                        
            #            ###                   ###            #            
         ####   ##        ###      ## ##      ###        ##   ####         
        ####   ##        ###       ## ##       ###        ##   ####        
 ##     #  #   ## # ##  # #                     # #  ## # ##   #  #     ## 
 ##     ####    # # ##  ##                       ##  ## # #    ####     ## 
         ####   # ##                                   ## #   ####         
            #                                                 #            
 \n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
            #                                                 #            
         ####   # ##                                   ## #   ####         
 ##     ####    # # ##  ##                       ##  ## # #    ####     ## 
 ##     #  #   ## # ##  # #                     # #  ## # ##   #  #     ## 
        ####   ##        ###       ## ##       ###        ##   ####        
         ####   ##        ###      ## ##      ###        ##   ####         
            #            ###                   ###            #            
                        # #                     # #                        
                        ##                       ##                        

''Wild Animals'' - paste this into the text box and press Start:

        # #
         ##
         #
 \n\n\n\n\n\n\n\n
         #
         #                      ##########                ###
         #
 \n\n\n\n\n
  #  #         ####
      #       #   #
  #   #           #
   ####       #  #
 \n\n\n\n\n\n
   #          #####
 #   #       #    #
      #           #
 #    #      #   # 
  #####        #
 \n\n\n\n\n\n
   ##        ######
 #    #     #     #
       #          #
 #     #    #    #
  ######      ##
 \n\n\n\n\n\n\n\n\n
                                         #
                                        ###                 #
        ###                             # #                 #
                                        ###                 #
                                         #
 \n\n\n\n\n\n\n\n\n\n\n
  #
  ##
 # #

Bob Clark

----
[TV] Scientific correctness dictates that the introduction be amended by making clear the idea is at least decades old, and never caught on very much as relevant science because there are more powerfull theoretical automaton constructions which existed long ago, and because it is not particularly usefull.

It is fun, of course, that special case of 2 dimensional set transformation rules. Computers, for instance as von Neuman type of game, and turing machines as automatons are an example of longer existing more  genarally applicable automaton models, which of course can be programmed with the kind of image map tranformation rules.

Bob Clark - Theo, if you're suggesting cellular automata are uninteresting because all the work was done 30 years ago, then I think you're wrong. CAs gained their place in history as the proving ground for ideas about "emergent behaviour" (simple rules, complex outcomes) that have since had applications all over.

[TV] Not at all, it was just factually uncorrect to suggest or state they were invented recently, or that they are some mainstream fashion in serious main stream mathematics of the kind lets say quantum physics is in already a hundred years. When you know about that sort of math, you wouldn't suggest such things, not taking away that it can be ''fun'', it's just not very important for anything, including simple rules, complex outcomes ideas. In that area probably  one may want to refer to mandelbrot figures as good mathematidal example, or the computation of pi on a turing machine or something, the cellular automaton idea was more for visual feedback I'm sure, and in computer math as in computer graphics software/architecture, and maybe in the fields of neural net examples (emphasizing the term examples).

Probably it has very relevant proof or lets say 'make credible' applications, and maybe has more interesting sides to it than I am aware of, but not much in mainstream fundamental mathematics.

[AM] (3 november 2003) Cellular automata were also studied in the field of hydrodynamics (or fluid mechanics in general) to see whether they could serve as models for the patterns in turbulent flows that can be observed. The big problem was: how to make the conservation laws work (mass, impuls). And I think that certain chemical reactions (particularly reversible ones) are studied with CAs as well - but on this subject I am much less versed. 

[TV] And were they useable?
----
[[
[Category mathematics] |
[Category games] |
[Category application]
]]