Painting Lessons

To display the maze on screen, the program can either use a graphics library or, in the simplest case, write characters into the terminal as ASCII art. Since individual cells in the maze share their walls with neighboring cells, you don't need to bother with displaying all four walls: Two walls are enough if a cell takes care of its south and east walls, and the missing bits are provided by the neighbors to the north and west.

The algorithm for drawing the maze needs to iterate through the cells of the internal representation from left to right and from top to bottom, as shown in Listing 5. It draws a wall at the bottom of each cell unless the cell is open in the direction of South and draws a wall on the right if East is not an option. If a cell is at the edge of the maze (i.e., at the far left, right, top, or bottom), the algorithm also puts walls in those directions.

01 package main
02
03 func (maze Maze) toString() string {
04   output := ""
05
06   for x := 0; x < maze.Width; x++ {
07     output += "+---"
08   }
09   output += "+\n"
10
11   for y := 0; y < maze.Height; y++ {
12     upper := "|"
13     lower := "+"
14     for x := 0; x < maze.Width; x++ {
15       wall := "|"
16       if (maze.Cells[y][x].Options & East) != 0 {
17         wall = " "
18       }
19       sol := " "
20       if maze.Cells[y][x].Solution {
21         sol = "o"
22       }
23       upper += " " + sol + " " + wall
24
25       wall = "---"
26       if (maze.Cells[y][x].Options & South) != 0 {
27         wall = "   "
28       }
29       lower += wall + "+"
30     }
31     output += upper + "\n"
32     output += lower + "\n"
33   }
34
35   return output
36 }

Figure 5 shows a maze cell with closed east and south walls (shown on the left). Each cell consists of five columns and three rows, but an individual cell is only responsible for its south wall (four columns) and east wall (two rows).

Figure 5: On the left, a maze cell with closed south and east walls; on the right, a closeup of the ASCII characters for each wall.

For a closed south wall, the bottom row contains the string "---+"; if it is open, it contains " +". For a closed east wall, the second line from the top contains the pipe character |; for an open east wall, it contains a space instead. As mentioned previously, the cell does not need to worry about the north and west walls; the south and east walls of the neighboring cells take care of that.

Finding Solutions

Once the maze is defined, following the call to makeMaze() in line 41 of Listing 1, the Solve() function in Listing 6 looks for a solution to traverse the maze from start to finish.

01 package main
02
03 func (maze Maze) Solve() []*Cell {
04   maze.Reset()
05   stack := []*Cell{maze.Start}
06
07   for len(stack) > 0 {
08     cur := stack[len(stack)-1]
09     cur.Visited = true
10
11     if cur.X == maze.Finish.X &&
12        cur.Y == maze.Finish.Y {
13       return stack
14     }
15
16     var moveto *Cell
17     for _, turn := range Turns {
18       if (cur.Options & turn) != 0 {
19         trycell, err := maze.Move(cur, turn)
20         if err == nil && !trycell.Visited {
21           moveto = trycell
22           break
23         }
24       }
25     }
26
27     if moveto == nil {
28       // nowhere to go, backtrack
29       stack = stack[:len(stack)-1]
30       continue
31     }
32
33     stack = append(stack, moveto)
34   }
35
36   return stack
37 }

The solver does a depth-first search (i.e., it first digs down in order to find a solution with a quick path). The alternative would be to try out all possibilities at every turn in order to reach the goal by the shortest path (a breadth-first search).

If some paths in the maze take the explorer in circles, this can pose a challenge to more primitive solvers; they have to avoid getting trapped into running around in circles forever. Our trusty solver, Solve(), on the other hand, is well equipped to avoid this trap; it tags the Visited field of previously processed cells and would never think of looking at any of them again.

This means that the solver dashes forward from the starting point along allowed paths, takes the first available branch in each case, and pushes the corresponding cell onto the stack stack. If it happens to pass the finish point, it cancels the chase and claims victory, using the cells stacked on the stack as the solution path. This is not necessarily the shortest path to the solution, but at least the algorithm finds it quickly.

If, on the other hand, it does not arrive at the end of the maze, but at a dead end, it has to retreat along its own stack. It lopes back to a turnoff taken previously and explores an alternative path from there. In this way, it eventually runs into the endpoint and returns the stack built up to that point to the caller as the solution path.

The main program uses the solution cell array to tag the cells along the path, in each case setting the Solution flag to true. The print function writes an o to these cells.

All Together Now

Listings 1, 2, 5, and 6 are compiled by the command shown in Listing 7 to create a maze binary; this in turn outputs a 5x4 maze, complete with a solution, when called. The dimensions can easily be changed by manipulating the values for width and height in main(). Interested hobbyists are also encouraged to try out different algorithms for generating and solving new exciting mazes [5].

$ go build maze.go print.go solve.go manip.go

The Author

Mike Schilli works as a software engineer in the San Francisco Bay area, California. Each month in his column, which has been running since 1997, he researches practical applications of various programming languages. If you email him at mailto:mschilli@perlmeister.com he will gladly answer any questions.