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).

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.

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

  1. Buck, Jamis. Mazes for Programmers: Code Your Own Little Twisty Passages, Pragmatic Bookshelf, 2015: https://www.amazon.com/dp/B013HA1UY4
  2. Listings for this article: ftp://ftp.linux-magazine.com/pub/listings/linux-magazine.com/245/
  3. Maze generation algorithm: https://en.wikipedia.org/wiki/Maze_generation_algorithm
  4. Maze solving algorithms: https://en.wikipedia.org/wiki/Maze_solving_algorithm
  5. Go GitHub project for creating and solving mazes: https://github.com/itchyny/maze

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.

Buy this article as PDF

Express-Checkout as PDF
Price $2.95
(incl. VAT)

Buy Linux Magazine

SINGLE ISSUES
 
SUBSCRIPTIONS
 
TABLET & SMARTPHONE APPS
Get it on Google Play

US / Canada

Get it on Google Play

UK / Australia

Related content

  • Free Software Projects

    Python inventor Guido van Rossum is known to have a good sense of humor and probably had a good laugh when he heard about the Guido van Robot project. If you are learning how to program, or would like to teach others, this software gives you a light-hearted introduction.

  • Gifts for Gamers: Some End-of-Year Recommendations, Part 3

    In part 3 of our gamers recommandations we present more strategy games, puzzles, card games, language skill training and more. To be continued.

  • Top Coder

    Springtime is application time! Mike Schilli, who has experience with job application procedures at companies in Silicon Valley, digs up a question asked at the Google Engineering interview and explains a possible solution in Go.

  • Treasure Hunt

    A geolocation guessing game based on the popular Wordle evaluates a player's guesses based on the distance from and direction to the target location. Mike Schilli turns this concept into a desktop game in Go using the photos from his private collection.

  • Firefox Phone Apps

    Cooking up an app for the Firefox OS is in no way difficult. All you need is a good measure of HTML and a dash of CSS. A few drops of JavaScript will bring it all to life.

comments powered by Disqus
Subscribe to our Linux Newsletters
Find Linux and Open Source Jobs
Subscribe to our ADMIN Newsletters

Support Our Work

Linux Magazine content is made possible with support from readers like you. Please consider contributing when you’ve found an article to be beneficial.

Learn More

News