Programming Snapshot – Go Mazes

In Europe, mazes are said to have come into fashion during the 15th century, mostly on manorial estates where guests were politely invited to "lose themselves" in gardens segregated by high hedges. However, winding paths (some of which even lead you in circles), where you need to make it from a starting point to an endpoint, can also be drawn on paper or simulated on computers. Algorithms usually represent a maze's path system internally as a graph along the edges of which the virtual explorer traverses from one node to the next, discarding dead ends, breaking out of endless loops, and eventually arriving at the destination node.

Computational handling of mazes is divided into two tasks: creating mazes and traversing them as effectively as possible by using a solver. You wouldn't think it possible, but on Amazon you can actually find a book entitled Mazes for Programmers [1]. The Kindle version of this book is a total failure due to font problems, but the paper edition shows some useful methods for creating and solving mazes.

From Cell to Cell

A maze consists of a matrix of MxN cells. In Figure 1, red arrows show the directions in which a traveler advances from cell to cell. These options then define the walls that are drawn to separate a cell from its neighbors.

Figure 1: A computer-generated 5x4 maze including the permitted moves between cells.

For example, the starting cell at coordinates (0, 0) defines that there's only one path to exit the cell in an eastward direction. Based on this restriction, the algorithm for drawing the maze concludes that the cell's east wall is missing and only draws in the south wall as a thick line. The program later defines the allowed direction changes as North, South, East, and West. Note that travelers are allowed to walk the maze in either direction, so if a cell specifies East, the cell to its right has to allow at least West.

The algorithm's internal representation of the maze as a graph is shown in Figure 2. Only one path leads away from the starting node (0, 0), and that is to the node (0, 1), going east from the starting node. The first element of the coordinate is the y value that determines the row, the second is the x value for the column – this is how programs usually store two-dimensional arrays.

Figure 2: A maze as a graph: the cells as nodes and permitted paths as edges.

The main program shown in Listing 1 [2] creates a new maze model with newMaze() in line 37. This is followed by the definition of the start and finish coordinates, with the cells top left and bottom right. makeMaze() in line 41 fires up the random generator and builds the walls. The call to Solve() in line 43 finds a path from the start to the finish. The result is an array slice of cells to be traversed along this path. The for loop starting in line 44 marks them in the internal representation that Print() later prints onto the terminal in line 47.

01 package main
02
03 import (
04   "fmt"
05   "math/rand"
06   "time"
07 )
08
09 const (
10   North = 1 << iota
11   South
12   West
13   East
14 )
15
16 type Cell struct {
17   X, Y     int
18   Options  int
19   Visited  bool
20   Solution bool
21 }
22
23 type Maze struct {
24   Cells  [][]Cell
25   Width  int
26   Height int
27   Start  *Cell
28   Finish *Cell
29 }
30
31 var Turns = []int{North, South, West, East}
32
33 func main() {
34   width := 5
35   height := 4
36   rand.Seed(time.Now().UnixNano())
37   maze := newMaze(width, height)
38   maze.Start = &maze.Cells[0][0]
39   maze.Finish = &maze.Cells[height-1][width-1]
40
41   makeMaze(maze)
42
43   solution := maze.Solve()
44   for _, step := range solution {
45     step.Solution = true
46   }
47   fmt.Print(maze.toString())
48 }

The remaining functions, summarized in Listing 2, help both the generator and later the solver to work their way through the cells. For example, each cell has a Boolean Visited field that algorithms set to true once they have processed a cell. The Reset() function, starting in line 24, resets all the fields in the matrix to their original state after the work is done.

001 package main
002
003 import (
004     "errors"
005     "math/rand"
006 )
007
008 func newMaze(width int, height int) *Maze {
009   var cells [][]Cell
010   for y := 0; y < height; y++ {
011     row := make([]Cell, width)
012     for x := 0; x < width; x++ {
013       row[x].X = x
014       row[x].Y = y
015     }
016     cells = append(cells, row)
017   }
018   return &Maze{
019     Width:  width,
020     Height: height,
021     Cells:  cells}
022 }
023
024 func (maze *Maze) Reset() {
025   for x := 0; x < maze.Width; x++ {
026     for y := 0; y < maze.Height; y++ {
027       maze.Cells[y][x].Visited = false
028     }
029   }
030 }
031
032 func (maze Maze) Neighbors(cell *Cell) []*Cell {
033   neighbors := []*Cell{}
034   for _, direction := range Turns {
035     tcell, err := maze.Move(cell, direction)
036     if err != nil || tcell.Visited {
037       continue
038     }
039     neighbors = append(neighbors, tcell)
040   }
041   return neighbors
042 }
043
044 func (maze Maze) Move(cell *Cell, turn int) (*Cell, error) {
045   var dx, dy int
046
047   switch turn {
048   case North:
049     dy = -1
050   case South:
051     dy = 1
052   case West:
053     dx = -1
054   case East:
055     dx = 1
056   }
057
058   if cell.X+dx > maze.Width-1 ||
059     cell.X+dx < 0 ||
060     cell.Y+dy > maze.Height-1 ||
061     cell.Y+dy < 0 {
062     return cell, errors.New("Stepped outside")
063   }
064
065   return &maze.Cells[cell.Y+dy][cell.X+dx], nil
066 }
067
068 func makeMaze(maze *Maze) {
069   stack := []*Cell{}
070
071   maze.Start.Options = East
072
073   stack = append(stack, maze.Start)
074   for len(stack) > 0 {
075     lastIdx := len(stack) - 1
076     cur := stack[lastIdx]
077     stack = stack[:lastIdx]
078
079     ncells := maze.Neighbors(cur)
080
081     if len(ncells) > 0 {
082       stack = append(stack, cur)
083       idx := rand.Intn(len(ncells))
084       rcell := ncells[idx]
085
086       rcell.Visited = true
087       cellConnect(cur, rcell)
088       stack = append(stack, rcell)
089     }
090   }
091 }
092
093 func cellConnect(c1 *Cell, c2 *Cell) {
094   if c1.X == c2.X {
095     if c1.Y < c2.Y {
096       c1.Options |= South
097       c2.Options |= North
098     } else {
099       c1.Options |= North
100       c2.Options |= South
101     }
102   }
103
104   if c1.Y == c2.Y {
105     if c1.X < c2.X {
106       c1.Options |= East
107       c2.Options |= West
108     } else {
109       c1.Options |= West
110       c2.Options |= East
111     }
112   }
113 }

The Neighbors() function starting in line 32 returns all direct neighbors of a cell in all four cardinal directions as an array slice of pointers to Cell types. Move() starting in line 44 starts traversing from a given cell in the specified cardinal direction and returns a pointer to the target cell. If the move ends up outside the matrix universe, an error is returned instead.

Figure 3 shows three successive calls to the compiled binary maze generated from the listings. The algorithm generates a different maze each time, and the solver always finds a way from the start to the finish.

Figure 3: Three different 5x4 mazes with paths from the start, located top left, to the finish, at bottom right.

Creator

So how do you go about creating a computer-generated maze? Most of the algorithms for this were developed more than 50 years ago. Wikipedia lists the best-known generators [3] and solvers [4]. The listings presented in this issue implement the iterative algorithm.

Listing 1 defines a maze of the Maze type with a two-dimensional array slice of cells of the Cell type in line 23 for this purpose. In addition to the dimensions of the cell matrix, the structure also stores the starting point and endpoint of the solution path we are looking for.

The maze's cells, in turn, in line with their definition in line 16, consist of the x and y coordinates of the cell, the path options, and markers stating whether the algorithm has already traversed them and whether they form part of the path to the solution.

Beginning at the starting point, the program works its way to neighboring cells, randomly changing direction as it goes. If it reaches a dead end where it cannot find any more cells that have not been visited previously as neighbors, it backtracks and starts searching for new candidates that are attached to cells that it has already traversed. In Listing 2, makeMaze() pushes all the cells that still need to be processed onto a stack, from where it later picks them up to traverse the cell neighbors and search for new candidates.

Line 83 takes a random neighbor of the current cell to be examined, calls cellConnect() to tear down the separating wall, and then allows connections in the respective cardinal direction thanks to the Options cell variable. In doing so, both cells go through changes that reflect the direction. For example, to set up a connection between two cells stacked on top of each other, the lower cell is given the option North as a viable path, while the upper cell receives the South option.

Complicated Pop

Removing the last element from an array slice in Go and storing it in a variable (as shown in line 75-77 of Listing 2) takes a surprising number of steps. Scripting languages like Python do this in a snap with pop().

However, Go insists on first addressing the last index of the array (len(slice)-1) and fetching the value there. Then it is a matter of reassigning the partial slice from index numbers   to len(slice)-1 (exclusively, that is, without the last element) to the same slice variable (Listing 3). Thanks to Go's internal slice arithmetic, which only moves pointers but does not recopy elements, the whole thing is very efficient – but not that easy to read in the program code.

last = slice[len(slice)-1]
slice = slice[:len(slice)-1]