# Cellular Automata in MGS

*Cellular Automata* (*CA* for short) is a computing model used in a theoretic perspective in fundamental computer science as well as a modeling/simulating tool. A CA consists of a regular lattice of *cells*, each cell being characterized by its local state. The mapping of a state to each cell of the network (in other words, the global state of the CA) is called a *configuration*. The dynamics of the CA is specified through local rules allowing the evaluation of the next state of cell as function of its current state and the state of a finite number of neighbors. One of the most important point in CA is that cells behave **synchronously**: they all switch to their next state at the same time.

MGS topological collections and transformations can be seen as a weakening of CA (from regular grid to arbitrary neighborhood, from local rules to transformation rules, from synchronicity to a rewriting strategy). This make the language suitable for expressing CA as illustrated by the examples below.

## Fire Spread Modeling

To illustrate the adequacy of MGS to express CA, we propose to focus on the modeling of fire spread in forest. In the following two models are implemented:

- a simple but paradigmatic 3-state CA
- a more elaborated model due to Karafyllidis & Thanailakis

### Three-State Simple Model

In this CA, a cell represents either some plants, or some fire or ashes. The rule are extremely simple:

- a forest cell gets in fire if one of its neighbors is burning
- a fire cell turns to ashes

#### MGS Implementation

Let define the filename for JBView visualization

ofile := "/tmp/ff.jbv" ;;

Cells have three possible states: forest, fire, ash

type cell = `Forest | `Fire | `Ash ;; type configuration = [cell]Moore ;;

Let define a initialization function populating a given grid g with 0 and 1 at random

fun populate_grid(g:Moore, size_x:int, size_y:int) = ( for i = 0 to size_x do for j = 0 to size_y do g.(i * |E> + j * |N>) := if random(10000) < 5 then `Fire else `Forest fi; g ) ;;

Let define the initial state S0

S0 := populate_grid(Moore:(),100,100) ;; configuration(S0);;

The previous code uses the predefined GBF topological collection `Moore`

which corresponds to an infinite square grid with 8 neighbors; to switch to a von Neuman neighborhood (infinite square grid with 4 neighbors, called `NEWS`

in MGS) do

type configuration = [cell]NEWS ;; fun populate_grid(g:NEWS, size_x:int, size_y:int) = ( for i = 0 to size_x do for j = 0 to size_y do g.(i * |East> + j * |North>) := if random(10000) < 5 then `Fire else `Forest fi; g ) ;; S0 := populate_grid(NEWS:(),100,100) ;;

Let define the cellular automaton rules

trans rules = { // Fire propagates to neighbor forest cells `Forest as c / neighbors_exists(equal(`Fire), c) => `Fire; // Extinction of fire `Fire => `Ash; } ;;

Let define a function to save data for the viewer

fun output(S) = ( ofile << " { " ; foreach c @ p in S do begin let (x,y) = sequify(p) in ofile << " { " << x << " " << y; ofile << switch c case `Forest: " 0.6 0.73 0.35 } " case `Fire: " 0.96 0.59 0.27 } " case `Ash: " 0.29 0.27 0.16 } " endswitch end; ofile << " }\n" ; S ) ;;

Let save data during the simulation

rules[fixpoint, prelude = output, interlude = output ](S0) ;;

The whole code follows

- ff.mgs
ofile := "/tmp/ff.jbv" ;; type cell = `Forest | `Fire | `Ash ;; type configuration = [cell]Moore ;; fun populate_grid(g:Moore, size_x:int, size_y:int) = ( for i = 0 to size_x do for j = 0 to size_y do g.(i * |E> + j * |N>) := if random(10000) < 5 then `Fire else `Forest fi; g ) ;; S0 := populate_grid(Moore:(),100,100) ;; configuration(S0);; trans rules = { // Fire propagates to neighbor forest cells `Forest as c / neighbors_exists(equal(`Fire), c) => `Fire; // Extinction of fire `Fire => `Ash; } ;; fun output(S) = ( ofile << " { " ; foreach c @ p in S do begin let (x,y) = sequify(p) in ofile << " { " << x << " " << y; ofile << switch c case `Forest: " 0.6 0.73 0.35 } " case `Fire: " 0.96 0.59 0.27 } " case `Ash: " 0.29 0.27 0.16 } " endswitch end; ofile << " }\n" ; S ) ;; rules[fixpoint, prelude = output, interlude = output ](S0) ;;

### Karafyllidis-Thanailakis Model

I. Karafyllidis and A. Thanailakis^{1)} proposed an elegant but realistic model of fire spread which takes into account some environmental effects like wind (for both speed and direction), type of fuel, and landscape topography. The model is specified as a CA where the state of a cell is characterized by the ratio of burnt area ranging continuously from 0 (wholesome forest) to 1 (burnt forest - ashes) where the interval (0,1) represents burning forest.

#### MGS Implementation

- karafyllidis_thanailakis_ff.mgs
//////////////////////////////////////////////////////////// // DEFINITION OF THE SYSTEM N := 100 ;; SCALE := 10000 ;; rose := |N>,|NE>,|E>,|SE>,<N|,<NE|,<E|,<SE|,():ring ;; trans searchPos[v] = { x / (x==v) => return(^x) } ;; // Wind type wind = [float]Moore ;; fun new_wind(dir:posgbf, force:(`Strong|`Weak|`None)) = ( let (d,md,orth,diag,mdiag) = if (force == `Weak) then (0.9,1.1,1.0,1.0,1.04) elif (force == `Strong) then (0.5,1.8,1.0,0.7,1.3) else (1.0,1.0,1.0,1.0,1.0) fi in let p = searchPos[v=dir](rose) in {| d @ rose.(p), md @ rose.(p+4), orth @ rose.(p+2), orth @ rose.(p-2), diag @ rose.(p+1), diag @ rose.(p-1), mdiag @ rose.(p+3), mdiag @ rose.(p-3) |}:Moore ) ;; // State type system = [cell]Moore and record cell = { wind:wind, burnt:float, height:float, rate:float } and record burnable = cell + { burnt ~= 1.0 } + { rate ~= 0.0 } and record burnt = cell + { burnt = 1.0 } ;; // Specification of a configuration constructor fun new_grid(f) = ( reverse(fold((\i,acc.( reverse(fold((\j,acc.( f(i-1,j-1) :: acc )),seq:(),N)) :: acc )),seq:(),N)) following |E>, |N> ) ;; fun export_grid[ofile="/tmp/toto"](color,g) = ( stdout << "iteration: " << 'iteration << "\n"; ofile << " { " ; fold((\i,acc.( fold((\j,acc.( let c = color(g.((i-1)*|E> + (j-1)*|N>)) in if c <> WHITE then ofile << " { " << (i-1) << " " << (j-1) << " " << c.r << " " << c.g << " " << c.b << " } " fi )),<undef>,N) )),<undef>,N) ; ofile << " } " ; g ) ;; fun color(v) = if burnt(v) then WHITE elif v.burnt == 0.0 then WHITE else mult_color(WHITE,GRAY(1.0-v.burnt)) fi ;; // Definition of an initial state fun init(i,j) = ( let w = new_wind(|E>,`Strong) in let r = if (i > N/5) && (i < 2*N/5) && (j > N/5) && (j < 2*N/5) then 0.01 else 0.1 fi in let b = if (i,j) == (N/2, N/2) then 0.1 else 0.0 fi in let h = let i' = (8.*i)/N in let (c1, c2, c3, c4, c5) = map((\c.((N/2.-abs(N/2.-j))*c/5.)),iota(5,seq:())) in if (0 <= i') && (i' < 1) then c1 elif (1 <= i') && (i' < 2) then (2-i')*c1 + (i'-1)*c2 elif (2 <= i') && (i' < 3) then c2 elif (3 <= i') && (i' < 4) then (4-i')*c2 + (i'-3)*c3 elif (4 <= i') && (i' < 5) then c3 elif (5 <= i') && (i' < 6) then (6-i')*c3 + (i'-5)*c4 elif (6 <= i') && (i' < 7) then c4 //elif (7 <= i') && (i' < 8) then (8-i')*c4 + (i'-7)*c5 else (8-i')*c4 + (i'-7)*c5 fi in !! h >= 0. ; stdout << h << "\n" ; { wind = w, burnt = b, height = h, rate = r } ) ;; g0 := new_grid(init) ;; system(g0) ;; //////////////////////////////////////////////////////////// // SPECIFICATION OF THE DYNAMICS fun moore_coeff(d) = ( if (d == <N|) || (d == |N>) || (d == <E|) || (d == |E>) then 1.0 else 1.0/sqrt(2.0) fi ) ;; trans rules = { x / ((x.burnt != 1.0) && (neighborsexists((\y.(y.burnt != 0.0)),x))) => ( let b = neighborsfold_indexed((\p,y,acc.( if y != <undef> then x.rate * moore_coeff(p-^x) * x.wind.(p-^x) * max(0.0,(1.0 + (x.height - y.height))) * y.burnt + acc else acc fi )),x.burnt,x) in x + { burnt = min(1.0,b) } ); } ;; rules[prelude = export_grid(color), interlude = export_grid(color), fixpoint ](g0) ;;

## Famous CA in 1 and 2D

### Classic 2D: Game of Life

The Game of Life is a 2D CA due to John H. Conway. The CA can be seen as an abstract and qualitative description of how a population populate (or fail to populate) some environment. Cells have two possible states

- living (
*i.e.*, which means populated) - dead (
*i.e.*, empty)

The rules are simple:

- an empty place is populated if it is surrounded by exactly 3 living cells
- a living cell die unless it is surrounded by 2 or 3 living cells (not to low for not being isolated, not to high for not suffocating)

The MGS implementation is straightforward: we use integers 0 and 1 to represent respectively dead and living cells to ease the count of living neighbor cells.

#### MGS Implementation

Let define the filename for JBView visualization

ofile := "/tmp/gol.jbv" ;;

Let define a initialization function populating a given grid g with 0 and 1 at random

fun populate_grid(g:Moore, size_x:int, size_y:int) = ( for i = 0 to size_x do for j = 0 to size_y do g.(i * |E> + j * |N>) := random(2); g ) ;;

Let define the initial state S0

S0 := populate_grid(Moore:(),100,100) ;;

Let define the cellular automaton rules

trans rules = { // An empty cell is populated if it has exactly three alive neighbors 0 as c / neighborsfold(add,0,c) == 3 => 1 ; // A living cell dies if it is not surrounded by two or three living cell 1 as c / let nb_ngh = neighborsfold(add,0,c) in nb_ngh != 3 && nb_ngh != 2 => 0 ; // Implicit default rule: x => x } ;;

Let define a function to save data for the viewer

fun output(S) = ( ofile << " { " ; foreach c @ p in S do if c == 1 then let (x,y) = sequify(p) in ofile << " { " << x << " " << y << " 0 0 0 } " fi; ofile << " }\n" ; S ) ;;

Let save data during the simulation

rules[iter = 200, prelude = output, interlude = output, postlude = output ](S0) ;;

The whole code follows

- game_of_life.mgs
ofile := "/tmp/gol.jbv" ;; fun populate_grid(g:Moore, size_x:int, size_y:int) = ( for i = 0 to size_x do for j = 0 to size_y do g.(i * |E> + j * |N>) := random(2); g ) ;; S0 := populate_grid(Moore:(),100,100) ;; trans rules = { 0 as c / neighborsfold(add,0,c) == 3 => 1 ; 1 as c / let nb_ngh = neighborsfold(add,0,c) in nb_ngh != 3 && nb_ngh != 2 => 0 ; } ;; fun output(S) = ( ofile << " { " ; foreach c @ p in S do if c == 1 then let (x,y) = sequify(p) in ofile << " { " << x << " " << y << " 0 0 0 } " fi; ofile << " }\n" ; S ) ;; rules[iter = 200, prelude = output, interlude = output, postlude = output ](S0) ;;

### Classical 1D: Elementary 1D CA

*Elementary Cellular Automata* (ECA) are 1D CA with two states and radius 1. There are exactly 256 possible specifications for the local rule. Each rule is identified by its *Wolfram code* which corresponds to a binary encoding of the rule. In the following code modify parameter `number`

of transformation `rules`

to consider some particular rule.

- elementary_ca.mgs
ofile := "/tmp/eca.jbv" ;; gbf grid = < d ; 100 d > ;; S0 := map((fun x -> random(2)), iota(100, seq:())) following |d> ;; fun nth_bit(num,n) = if n == 0 then num%2 else nth_bit(num/2,n-1) fi ;; trans rules[number = 90] = { b => nth_bit(number, 4*neighbor(<d|,b) + 2*b + neighbor(|d>,b)) } ;; fun output(S) = ( for i = 0 to 100 do if S.(i * |d>) == 1 then ofile << " { " << i << " " << iteration << " 0 0 0 } " fi; S ) ;; ofile << " { " ;; rules[iter = 100, prelude = output, interlude = output, postlude = output ](S0) ;; ofile << " }\n" ;;

^{1)}I. Karafyllidis and A. Thanailakis.

*A model for predicting forest fire spreading using cellular automata*. Ecological Modelling, 99(1):87 – 97, 1997