The first example of cellular automata was the game of Life by J.H. Conway. This game inspired all later cellular automata research. The game earned the name Life because it vaguely mimics population dynamics. But don't dig too deep into the metaphor. In reality, most uses of cellular automata borrow just a few salient points from the original game, then create an entirely different context. In particular, the most important ideas behind cellular automata are: the division of space into cells, the state of the cell depending only on the state of its neighbors, and the iteration of these cells over time.For example, an atmospheric cellular simulation might divide a three-dimensional volume into cubes. Each cube has several degrees of freedom involving temperature and mass exchange through the cube walls. Each cube has 6 immediate neighbors that directly affect the state of the cube. By setting up complex rules of cellular interaction based on physical laws, it is possible to study simulations of cloud formation and propagation. One valuable advantage to cellular automata is their localization and simultaneity. This means they work great on parallel processing systems.
How Life Works
Take a sheet of standard graph paper and a pencil, and fill a number of squares. Darken squares based on some spatial model, such as text characters on a page. Take a second piece of graph paper and lay it near the first. For each square on the first graph, look at the neighbors surrounding the square. Count them. What happens next will depend on this count. There are four possible outcomes. If the number of neighbors around a filled square is below some magic value, the square starves to death. If the number of neighbors around a filled square is above some level, the square dies of overcrowding. If the number of neighbors lies between starvation and crowding, the filled square continues to exist. If the square is empty and the number of neighbors is just right, the square becomes pregnant.On the second sheet of graph paper, mark the results of applying these rules to the squares on the first sheet. Either a full square dies and becomes empty, an empty square births and is filled, or a square continues like it was. After visiting the squares of the first graph, counting neighbors and using the transformation rules, you have a new population of squares on the second graph. You can take this new population as a starting point for yet another graph and repeat the loop, ad infinitum. Each new generation will reflect the original distribution of squares and the cumulative effect of the transformation rules.
Why two sheets of paper? Why not just mark it in place on one sheet? Because the transformation must be instantaneous and parallel. If you mark changes and count on the same sheet, the marked squares will influence the partially-completed transformation. This creates a different result from that obtained by marking the changes on a second sheet. The life in each square needs to evolve simultaneously with its neighbors. Because of this, most cellular-automata techniques use a pair of toggle buffers. One holds the current generation and another holds the future state under construction. Once you finish constructing the future state, you display it. Then you clear out the initial buffer and proceed anew, building the next iteration. Alternatively, you can use only one buffer but have some form of bit flagging to tell the difference between current and future states.
Another point to consider is the edge. If you glance at the corners and edges you will count fewer than eight neighbors for each pixel. How do you handle this? In the original Conway game the best solution is a closed universe. Bend the left side of the graph around to the right side and tape them. You now have a tube of paper without a left or right edge. Similarly, bend the top of the tube down to the bottom and tape them. You have a closed torus with no edges. The next most popular solution to the edge problem is an invisible pseudo edge, one square wide, which acts as a sentinel boundary encircling the graph. It provides the proper number of neighbors for cells on the graph but never appears on the display. Cellular propagation, into and beyond this boundary, falls off the edge of the world.