<> **Introduction** [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. **Program 1** ---- ====== # 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... **WireWorld** ''[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 {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} olours)] ;# {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 ize)/$Config(side)}] ;# pixels per cell 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 fe" 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 useful. 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? [AM] Probably not. I have not seen much of them since then in that field :) Bob Clark - One last attempt to rehabilitate CA :) - I think the ideas about Emergent Behaviour that CA helped to illustrate are still very much informing current technology. For examples, Google for: "emergent behaviour" network EB does have applications, and I'm fond of these 2D automata because they visualise EB so brilliantly, they can turn sceptics into believers. [Larry Smith] At this point, having seen this mentioned twice, that I must point out that cellular automata can have ''any number'' of dimensions, and that quite a few with three or four have been studied extensively. At this point in our hardware evolution, cellular automata are interesting for demonstrating emergent behavior in complex systems using simple rules, but are not hugely useful as a computing paradigm. This is basically because we are still using the Von Neumann architecture. As systems grow more and more massively parallel, cellular automata and their derivatives may find new traction. In point of fact, it is now over 20 years since "Content Addressable Parallel Processors" was published which talked about an engine with no central CPU - just intelligent memory responding in arrays to instructions fed into the memory control. I am not aware that any commercial systems were ever built on it, but if there were (or if this idea should be retrieved from the dustbin of history to deal with some new issue) something like cellular automata may very well ''be'' the programming paradigm of such a system. [JK] Cellular Automata turn up in the field of Computational Fluid Dynamics with the name of 'Lattice Gas' models. Essentially particles moving about on a lattice and colliding with each other. As long as the rules are implemented correctly they can be shown to behave as solutions of the Navier Stokes equations for fluid flow. If interested, I would also suggest looking up 'Lattice Boltzmann' methods. These are similar but instead of particles on lattices you deal with distributions of particles on the lattice. [TV] Ah, sounds like a computer iterative solution aimed scheme, Bolzman equations are not like cellular automatons, unless you maybe call all partitioned problems such? I guess you take a logical map transformation which happens to deal with an iterative matrix solution in an attractive way. Or an image processing related technique applied to solver scheduling. [EKB] -- [JK] explained the connection between lattice gases and cellular automomata: some CAs obey the Navier-Stokes equations (the equations for fluid flow), if you look at a large enough spatial scale (much larger than the lattice spacing). This offers a computationally efficient technique for modeling fluid flow, and is a contemporary application of CAs. A text describing the method was published in 2004, "Lattice-Gas Cellular Automata: Simple Models of Complex Hydrodynamics" [http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521607604], so it's very ''au courant''. Also, as Bob Clark pointed out, cellular automata were, indeed, important in giving rise to today's agent-based models, which have sparked interest because they are said to feature emergent behavior. In any case, the disclaimer at the start that, 'A few years ago cellular automata were "in vogue"' seems to convey the idea that CAs are not as "hot" as they once were. [AM] What I meant with "in vogue" was that such constructs were discussed in popular magazines like Scientific American. They seem to have disappeared from such publications ... but I am glad there is a more serious interest in them (the site http://mathworld.wolfram.com has quite a lot of information on their behaviour and general characteristics.) ---- <> Mathematics | Games | Toys | Application