Example of a Two-Dimensional Cellular Automaton, the "Game of Life"
Introduction to 2D Cellular Automata and the "Game of Life"
Whereas a single row, or array, of cells constitutes the state of a 1-D cellular automaton at a certain moment or “tick of the clock”, a series of rows, or array of arrays, constitutes a 2-D CA. So if a 2-D CA consists of 5 rows of 10 cells in each row, and each cell can exist in a state 0 or state 1, the overall state of the CA at a certain moment might look like this:
Just as with a 1D CA, we can display the 0’s and 1’s as colored pixels, which will be one of two colors. But whereas we can watch the evolution of a 1-D CA universe on a single screen, with each row presenting the state of the universe at the next tick of the clock, each tick of the clock of a 2-D CA requires a screen of its own, to be replaced by a new screen at the next click the CA evolves.
We can treat each row and column as continuous so that the left-most cell of each row is the left neighbor of the right-most cell, and the top-most cell in each column is the lower neighbot of the bottom-most cell. It is interesting to consider what form this takes if considered three dimensionally. You might instinctively think this would make a sphere, but in fact it forms a toroid, a donut.
In addition to deciding whether the cells at the left/right and top/bottom edges connect, we must also consider which cells are neighbors of any cell. We could decide that the cells left and right, and above and below are the neighbors (four neighbors in a neighborhood of five cells), or we might also include the cells that touch a cell only at the corner (making a total of eight neighbors in a neighborhood of nine cells).
And, whereas a 1-D CA with a 3-cell neighborhood (2 neighbors) might have any of just 256 different rules (or universes), a 2D CA with a 5-cell neightborhood (four neighbors) can have 2 to the power of 2 to the power of 5 rules, which is 2 the power of 32, which is 4,294,967,296 different possible rules, and a 2D CA with a 9-cell neighborhood (eight neigbors) can have 2 to the power of 2 to the power of 9, which is 2 the power of 512, which is 1.340781e+154, a number so large it is unimaginable! That’s a LOT of different universes! And remember we’re talking about universes that each contain just a grid of cells each of which can only have 2 different states, and universal rules that defined by just a small neighborhood of cells. It is very humbling.
Clearly we cannot define all of these possible rules, so what does this mean when it comes to defining the rules for a 2-D CA universe? It means we must take a statistical approach and explore this universe by experiment rather than exhaustively. For example we might make a rule that states: “if exactly 5 neighbors are 1’s or exactly 8 neighbors are 0’s then the cell evolves to state 1, otherwise the cell evolves to state 0. We can try out different rules in this way and see what happens, and gradually get a feel for what rules might be more or less interesting.
The Game of Life, developed by John Conway in 1970 is a 2-D CA of 2-state cells (0 or 1), with a neighborhood of 5 (that is, four neighbors) that displays some interesting, even fascinating, behaviors. The rules for this particular CA are as follows: