Maze Solution with CA

I’ve been playing with Cellular Automata (CA) since College. (See QHJ #4 for a more in depth discussion of CA) I’ve seem some articles that talk about how CA can be used in Physics and Chemistry to simulate various chemical reactions and particle simulations. I have not seen any fairly practical applications that can be easy demonstrated to show how useful CA can be.

That was before I read an article in the most recent issue of “Dr Dobb’s Journal.” Basem Nayfeb of Stanford University gives a fresh approach to finding the solution to a maze.

Past algorithms for solving mazes were brute force approaches to solve the maze just like a mouse. Be recursively searching all possible paths the solution will be eventually found. This takes time and lots of memory for stack space. Basem Nayfeb used CA to solve the problem with no extra extra memory needed.

Given a maze stored in an array. Cells with a wall have a value of 1, free cells are 0. In the maze possible moves are north, west, east, and south. This translates to a neighborhood of the 4 cells that share a side with a cell. Basem defines a counting rule that states: A free cell will become a wall cell if there are three or more walls in its neighborhood. The only cells that have 3 or more walls nearby are obviously dead-ends. Over time all dead-ends will convert to walls and only the true path(s) will stay free of walls.

By defining a simple neighborhood and that one simple rule, Basem has defined a CA that will fairly quickly find the solution to the maze.

Below is the a SuperBasic program that implements the algorithm. You can see how short and simple it is. Consider how much code it would take to solve the problem the recursive way.

** Maze_ssb
**   Tim Swenson
**
**   Based on an algorithm by Basem A. Nayfeb
**    Dr Dobb's Journal  January 1993
**

wall = 1
free = 0

** My example maze is 16x16.  Change
**  to what ever you need.
maze_x = 16
maze_y = 16

DIM maze(maze_x,maze_y)

read_file
display

REPeat loop
   eval
   dislay
   IF change = 0 THEN EXIT loop
END REPeat loop


DEFine PROCedure read_file
  OPEN_IN #4,flp1_maze_data
  FOR y = 1 TO maze_y
    INPUT #4,in$
    FOR x = 1 TO maze_x
      maze(x,y) = in$(x)
    END FOR x
  END FOR y
  CLOSE #4
END DEFine read_file

DEFine PROCedure eval
  LOCal count

   change = 0
   FOR y = 2 TO maze_y-1
      FOR x = 2 TO maze_x-1
         count = 0
         IF maze(x,y+1) = wall THEN count=count+1
         IF maze(x+1,y) = wall THEN count=count+1
         IF maze(x,y-1) = wall THEN count=count+1
         IF maze(x-1,y) = wall THEN count=count+1
         IF count >= 3 THEN
            maze(x,y) = wall
            change = 1
         END IF
      END FOR x
   END FOR y

END DEFine eval

DEFine PROCedure display

   CLS
   FOR y = 1 TO maze_y
      FOR x = 1 TO maze_x
         IF maze(x,y) = wall THEN
            PRINT "*";
         ELSE
            PRINT " ";
         END IF
      END FOR x
      PRINT
   END FOR y
   PAUSE 4E4
END DEFine display

Here is an example data file that I used in my testing of the program:

1111111111111111
1000000010000101
1010111010110101
1010101010110101
1010101010110101
1010101010111101
1110101010110001
0000101000110100
1110101010110101
1010101010110101
1010101010110101
1010101010110101
1010100010110101
1011111110111101
1000000000000001
1111111111111111