Random Explorations in Automata Theory
Gary J. Shannon
Mar. 2, 2003

Space Filling Grids

Cellular automata are built in grids made by dividing space into cells. The simplest example is the 1-dimensional cellular automaton. Here a line is divided into sections, although since it is easier to see what's happening if those sections are drawn as square rather than as pieces of a line.  The drawing is 2-dimensional but the grid is called 1-dimensional because it stretches out in only one dimension.

Fig. 1. A 1-dimensional grid.

The grid is called space-filling because it fills all of the space available to it without leaving any gaps between the cells. This grid can be of a definite length or it can be thought of as extending infinitely in both directions.  Another way of dealing with the ends of the grid is to wrap the strip around into a loop so that the first cell on the left touches the last cell on the right.

We observe that for every cell in the grid there are two neighboring cells. A cell along with its two neighbors is refered to as the neighborhood of the grid.  This particular neighborhood, illustrated in figure 2, is sometime refered to as the Wolfram neighborhood after physicist Stephan Wolfram who has studied 1-dimensional automata in considerable detail. In the illustration the cell being updated is colored red and the two neighboring cells are colored red. (For more information on neighborhoods see Cellular Neighborhoods.)

Fig. 2. The Wolfram neighborhood.

Moving up to 2-dimensional spaces we have many more choices of how to divide space into cells.  The most familiar is probably the square grid of the chess board. Figure 3 shows the square grid with what is called the Moore neighborhood highlighted.

Fig. 3. Square grid with Moore neighborhood.

Several different kinds of neighborhoods are popular in the square grid automaton and more information about them can be found on the page Cellular Neighborhoods.

Triangles will also fill space and they have frequently been used in cellular automata.  Each cell has three natural neighbors, but several other neighborhoods have been applied to the triangular grid as well.

Fig. 4. A triangular grid.

By taking clusters of 6 triangles at a time this grid can be turned into the hexagonal grid.  Each cell in the hex grid has 6 natural neighbors but again, other neighborhoods have been used.

Fig. 5. The hexagonal grid.

One nice feature of the hexagonal grid is that if you wish to work out hex grid automata by hand the hexagonal grid is exactly equivalent to a square grid with the cells stacked like brickwork. This is easier to sketch than a hex grid but works the same way.

Fig 6. Hex grid to brickwork.

== UNDER CONSTRUCTION. More coming soon ==