Basem is a graduate student in Electrical Engineering at Stanford University and can be contacted via e-mail at bnayfeh@leland.stanford.edu.
Many of us were introduced to cellular automata (CA for short) through Conway's game of Life, in which "creatures" living in a grid of cells are born, live, and die depending on their current state and the states of creatures in neighboring cells. Each creature is subject to a rule that defines its existence in terms of that of its neighbors, and the "community" at large is defined by the collective states of the individual creatures. The implication is that to model the "community" or a collective system, it may be sufficient to regard it as a collection of similar simple systems interacting only locally.
This concept is powerful when applied to many physical systems. For example, in studying particle simulations, we can discretize the system into grid cells that may or may not contain an individual particle. In grid cells containing a particle, the particle's momentum (or in a simpler case, direction) is adjusted due to collisions with any other particles in immediate neighboring cells. Thus, only local interactions are taken into account and, by looking at the momentum of the individual particles, the properties of the system as a whole can be determined. This provides an attractive alternative to solving sets of complex differential equations; and in fact, CA simulations scale very well on parallel systems.
In addition to a wide variety of applications in fluid dynamics, astrophysics, neural networks, and other fields, a potentially interesting application for CAs is in the solution of mazes. Maze-solving algorithms have long been of interest to computer scientists and engineers because of their use in routing problems. This article presents a CA-based algorithm for solving mazes which requires no more memory than that to store the original maze, provides all possible solutions at the same time, and can determine if a solution doesn't exists.
Conventional maze-solving algorithms have revolved around the "rat in the maze" approach in which a "rat" effectively runs through the maze according to set rules, backtracking only when reaching a dead end. The implication is that the rat has only a local knowledge of the maze relative to its position since it cannot "see" around corners. These algorithms are inherently recursive in nature since they require that, upon encountering an intersection of paths in the maze, one path is selected at a time while "remembering" the intersection. If the selected path leads to a dead end, the rat returns to the last intersection and follows another path until it reaches either a dead end or the end goal. This is essentially a depth-first search on a tree with maximal degree N, where N is the number of adjacent locations the rat can move to next from any given location. For example, in a two-dimensional maze where only north, east, west, and south (NEWS) moves are valid, N = 4. If diagonal moves are also allowed, N = 8. These can easily be extended to higher dimensions where, for a three-dimensional maze, N = 6 for NEWS and up and down moves, and N = 26 if all diagonal moves are allowed as well. For a large maze, the memory requirements to store such a potentially large tree and/or a stack used in traversing it in a depth-first manner can be substantial.
It may seem natural at this point to abandon the concept of a single "rat" with only a local knowledge of the maze and its corresponding depth-first search, and consider instead the implications of a global knowledge of the maze due to simultaneous local interactions throughout the maze--being able to "see" the whole maze at one time.
Let's assume that we want to solve a two-dimensional maze with only NEWS moves allowed, although the algorithm can be extended to higher-dimensioned mazes with other allowable moves in a straightforward manner. The maze is represented by a two-dimensional array or grid Maze[Xsize][Ysize], where Maze [x][y]== 1 denotes a wall at location (x,y) and Maze[x][y]== 0 indicates that location (x,y) is free (0<=x<Xsize, 0<=y< Ysize). A location that is "free" at a particular time during the algorithm's execution means that it can potentially be part of the solution path or paths, with all free paths being one unit wide. Likewise, a "wall" location cannot be part of the solution path. In addition, the maze is bounded by walls except for the start and end positions, which lie on the boundary and are considered to be permanent free locations; thus, only locations (x,y) with 0<x<Xsize - 1 and 0<y<Ysize - 1 need to be evaluated.
The heart of the algorithm is really quite simple. First, a two-dimensional array of cells is defined with each cell representing a location in the maze. A cell can change its "state" during each iteration according to a state transition rule which depends upon its current state and the current state of its NEWS adjacent cells. This is, in effect, the definition of a CA.
Next, two different states are defined for each cell in the CA. A cell in the FREE state, or a "free cell," corresponds to a free location, as described previously. Likewise, a cell in the WALL state (or "wall cell") corresponds to wall location.
In determining the state transition rule, the following observation can be made: A dead-end condition may be characterized by a free cell surrounded by at least N - 1 wall cells, where again N denotes the number of allowable adjacent moves. In our case, N = 4, so a dead-end condition occurs if a free cell is surrounded by either three or four wall cells in the NEWS directions. The case where a cell is surrounded by N wall cells is trivial since it implies that because the cell is completely surrounded by walls, it could never be accessed. The important point to note is that a free cell in a dead-end condition can never be part of the solution path since it has one entry point and no exit points. Thus, the free cell can be changed to a wall cell. Changing the free cell to a wall cell will now cause free cells that are not on a solution path and that immediately precede the former free cells to exhibit the dead-end condition themselves. The former free cells are subsequently changed to wall cells and so on down the line. As the process continues iteratively, dead-end paths become blocked off, and a steady-state condition is reached if no free cells change during the iteration into a wall cell. At this point, the free cells will denote the solution path or paths through the maze. In the case where all the internal cells have become wall cells, then no path exists from the start to end of the maze.
The rule applied to each cell in the CA during each iteration can then be expressed as follows:
A cell needs to store only its current state. Thus, no additional memory beyond the original cell (maze) array is required if the original maze can be over-written. This implies that the algorithm may be stopped and restarted after any iteration using only the current states in the cell array. This is unlike other recursive algorithms, which would require saving the entire search stack in order to restart.
The C code in Example 1 illustrates how this might be implemented. Although the code demonstrates how the algorithm may be implemented on a serial machine, CAs are easily adaptable to parallel programming on distributed and massively parallel architectures. This results from the single-rule and nearest-neighbor data-dependency characteristics of CAs, which enable them to map easily onto SIMD (single-instruction multiple-data) architectures.
#define FALSE 0
#define TRUE 1
#define FREE 0
#define WALL 1
. . .
do {
steadystate = TRUE;
/* scan the entire CA */
for (x=1;x<Xsize-1;x++) {
for (y=1;y<Ysize-1;y++) {
if (cell[x][y] == FREE) {
/* addition can be used here to determine if */
/* a cell is surrounded by 3 or more walls */
if ((cell[x+1][y] + cell[x-1][y]
+ cell[x][y+1] + cell[x][y-1]) >= 3) {
cell[x][y] = WALL;
steadystate = FALSE;
}
}
}
}
/* keep scanning the CA until */
/* a steady state condition is reached */
} while(!steadystate);
/* the cell array now contains the correct solution(s) */
/* denoted by the remaining free cells */
/* no solution if all cells are now wall cells */
. . .
CAs have come a long way from the game of Life and are considered valuable tools for simulating various complex systems. Parallel systems provide an almost ideal platform for CA simulations. In turn, CAs may prove to be the best method of simulation on massively parallel systems. As research in parallel computing continues and as new algorithms for CAs are introduced, cellular automata will play an important role in computing in years to come.
Copyright © 1993, Dr. Dobb's Journal