Page contents
Introduction edit
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.
Program 1 edit
# 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
#
mainDKF - 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 edit
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.
"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] edit
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 [1]. # 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 ClarkLangton's Other Ants edit
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.worldThis 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 ClarkConway in Colour edit
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 [2]. 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... edit
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 generally 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" networkEB 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" [3], 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.)