Creating and solving mazes with Go
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.
Listing 5
print.go
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).
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.
Listing 6
solve.go
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].
Listing 7
solve.go
$ go build maze.go print.go solve.go manip.go
Infos
- Buck, Jamis. Mazes for Programmers: Code Your Own Little Twisty Passages, Pragmatic Bookshelf, 2015: https://www.amazon.com/dp/B013HA1UY4
- Listings for this article: ftp://ftp.linux-magazine.com/pub/listings/linux-magazine.com/245/
- Maze generation algorithm: https://en.wikipedia.org/wiki/Maze_generation_algorithm
- Maze solving algorithms: https://en.wikipedia.org/wiki/Maze_solving_algorithm
- Go GitHub project for creating and solving mazes: https://github.com/itchyny/maze
« Previous 1 2 3
Buy this article as PDF
(incl. VAT)