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)
Buy Linux Magazine
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.
News
-
So Long Neofetch and Thanks for the Info
Today is a day that every Linux user who enjoys bragging about their system(s) will mourn, as Neofetch has come to an end.
-
Ubuntu 24.04 Comes with a “Flaw"
If you're thinking you might want to upgrade from your current Ubuntu release to the latest, there's something you might want to consider before doing so.
-
Canonical Releases Ubuntu 24.04
After a brief pause because of the XZ vulnerability, Ubuntu 24.04 is now available for install.
-
Linux Servers Targeted by Akira Ransomware
A group of bad actors who have already extorted $42 million have their sights set on the Linux platform.
-
TUXEDO Computers Unveils Linux Laptop Featuring AMD Ryzen CPU
This latest release is the first laptop to include the new CPU from Ryzen and Linux preinstalled.
-
XZ Gets the All-Clear
The back door xz vulnerability has been officially reverted for Fedora 40 and versions 38 and 39 were never affected.
-
Canonical Collaborates with Qualcomm on New Venture
This new joint effort is geared toward bringing Ubuntu and Ubuntu Core to Qualcomm-powered devices.
-
Kodi 21.0 Open-Source Entertainment Hub Released
After a year of development, the award-winning Kodi cross-platform, media center software is now available with many new additions and improvements.
-
Linux Usage Increases in Two Key Areas
If market share is your thing, you'll be happy to know that Linux is on the rise in two areas that, if they keep climbing, could have serious meaning for Linux's future.
-
Vulnerability Discovered in xz Libraries
An urgent alert for Fedora 40 has been posted and users should pay attention.