Life, Cellular Automata, and Map Algebra

Introduction

The game of Life is a cellular automaton (CA) invented by John Horton Conway. The CA is a rectangular array of cells. Each cell is either "occupied" (has the value 1) or "unoccupied" (has the value 0). The array is replaced by a new "generation" according to simple local rules; namely,

	An occupied cell with two occupied neighbors remains occupied.
	An unoccupied cell with two or three occupied neighbors becomes occupied.
	All other cells become unoccupied.

The neighbors of a cell are the eight cells immediately adjoining it horizontally, vertically, or diagonally.


Three successive Life generations (left to right) on a 32 x 32 grid. Occupied cells are dark.

"Map algebra," the quasi-formal language of manipulations with raster (gridded) data, enable the rules of Life to be written in a single expression; namely,

g = (g.FocalStats(#GRID_STATYPE_SUM, NbrHood.MakeRectangle(3,3,false), false)*2 - g - 6).Abs <= 1

(This is the syntax of ESRI's Spatial Analyst extension for ArcView 3.x desktop GIS software. The cumbersome "FocalStats(#GRID_STATYPE_SUM, NbrHood.MakeRectangle(3,3,false), false)" expression just sums the occupancy numbers of all nine cells in a 3 x 3 rectangle surrounding each cell. The "Abs" expression is the usual absolute value, where x.abs = x when x > 0 and otherwise x.abs = -x. The value "g", of course, represents the current generation. By convention, a true value is represented as 1 and a false value by 0. The map algebra expression replaces one generation with the next.)

How it works

A reader writes,

"I was going through the script of your CA extension for ArcView and was puzzled by the (*2-g-6) bit in the main line of the Life script."

At any grid location, the result of the FocalStats request is the total number of cells occupied either at that location or among its eight immediate neighbors, so it is some integral value between 0 and 9. Let's call that value n for convenience, so (writing || for absolute value) the Life expression is

|n*2 - g - 6| <= 1.

By the definition of absolute value, this will be true (that is, equal to 1) if and only if

-1 <= n*2 - g - 6 <= 1.

Equivalently, adding 6 + g to all sides,

5 + g <= n*2 <= 7 + g.

Division by 2 gives

2.5 + g/2 <= n <= 3.5 + g/2.

There are two cases: the original cell is unoccupied (g=0) or occupied (g=1). Thus, the Life expression equals 1 whenever either

g = 0 and 2.5 <= n <= 3.5; i.e., n = 3, or

g = 1 and 3 <= n <= 4; i.e., n is 3 or 4;

otherwise, it equals 0 ("false").

Observe that the number of occupied neighbors of the cell is n-g, not n, because n includes the occupancy of the cell itself. This leads us to write the expressions as

g = 0 and n-g = 3 or

g = 1 and n-g is 2 or 3.

These expressions, in words, are:

"A cell will become occupied (equal to 1) whenever either (a) it is unoccupied (equal to 0) and has exactly three neighbors (n-g=3) or (b) it is already occupied and has two or three neighbors (n-g is 2 or 3)."

That describes the game of Life.

How to find map algebra expressions for a CA

It would be fair to ask how one derives a map algebra expression from a Life-like description of a CA. One approach is to make a table of possibilities. For Life, it is clear that two values describe the future of each cell: its occupancy (g) and the sum of the occupancies of its neighbors (m = n-g). Here, g is either 0 or 1 and m ranges from 0 through 8, so there are only 2*9 = 18 possibilities. The Life rules tell us what to put in the table:

g	n	m	Next state(z)
0	0-2	0-2	0
0	3	3	1
0	4-8	4-8	0
1	1-2	0-1	0
1	3-4	2-3	1
1	5-9	4-8	0

You can use curve-fitting techniques to approximate the next generation's value as a function of g and m. For example, you could use least squares to find an expression of the form a + b*g + c*m + d*g*g + e*g*m + f*m*m + ... that merely approximates z; if the approximation is always better than 1/2, then rounding its value will give the exact expression.

That approach will be inefficient. You will get some insight by plotting z versus (m, g). This shows that the values z=1 are clustered at (m, g) = (3, 0), (2, 1), and (3, 1). The graph of the line 2*m + g = 6 passes closely through this cluster, so we might try a formula of the form:

"Occupy a cell for the next generation if (g, m) is sufficiently close to the graph of 2*m + g = 6."

The filled blocks (3, 0), (2, 1), and (3, 1) show the combinations of (m, g) that will produce occupied cells in the next Life generation. The line shown is one of many that intersect only these three blocks.

(The coordinates correspond to the centers of the blocks.)

Now do the algebra: write m = n-g and express "close" in terms of absolute value. You will reverse the process sketched above and arrive at the original map algebra formula.

This is a neat solution, but it is not necessary to be clever to find some solution. For instance, the cluster in (m, g) coordinates can be described by a circle of radius sqrt(5)/3 centered at (8/3, 2/3). Its equation is therefore

(g - 2/3)^2 + (m-8/3)^2 <= 5/9.

The circle contains the coordinates (3, 0), (2, 1), and (3, 1). It does not contain the centers of any of the other blocks. Therefore it determines whether or not a block will be occupied in the next generation.

Substituting m = n-g as before gives

2*g*(g + 2) + n*(n - 2*g - 16/3) <= -7

as the expression for the Life CA. It's messy, and even more mysterious, but it will work. (Incidentally, this can be put in the polynomial form above with a=7, b=4, c=-16/3, d=2, e=-2, and f=1, showing that the brute-force least squares method will succeed in finding an expression.)

Generalizations

Generalizations to automata that have more than two possible states per cell can be made by representing those states as integers 0, 1, 2, ..., k. For instance, the number of neighbors with value j (0 <= j <= k) is given by

([g]=j).FocalStats(#GRID_STATYPE_SUM, NbrHood.MakeRectangle(3,3,false), false)

Thus you can construct grids [N0], [N1], ..., [Nk] representing the total number of cells with values 0, 1, ..., k, respectively, within a neighborhood. (The neighborhood need not be just 3 x 3 either: it can be arbitrary in shape and size.) The next generation can then be expressed as an arithmetic function of [N0], [N1], ..., [Nk]. I have successfully used this approach for simulating and analyzing Markov models and hierarchical entropy models of images, for example.

The most useful Spatial Analyst requests for this kind of work, besides the FocalStats request and the integer arithmetic requests such as %, abs, and int, are the LocalStats, Pick, EqualTo, GridsGreaterThan/GridsLessThan, Con, and Lookup requests. Once you understand these well, the possibilities should be apparent. See the help on "Grid(class)" for a guide to all the requests. Many of these are explained on our Map Algebra pages.

I recommend taking a look at the latest release of Idrisi32: it contains a lot of CA support and can be programmed, albeit crudely, with VBA. Idrisi supports many grid file formats, so it is possible to work within your favorite GIS program but still use Idrisi for selected calculations. For more information, see my review at Directions Magazine.

(Bill Huber, 22 May 2001)

ColorRamp, Memorized Calculations, and Sample are trademarks of Quantitative Decisions. All other products mentioned are registered trademarks or trademarks of their respective companies.