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
-
Canonical Bumps LTS Support to 12 years
If you're worried that your Ubuntu LTS release won't be supported long enough to last, Canonical has a surprise for you in the form of 12 years of security coverage.
-
Fedora 40 Beta Released Soon
With the official release of Fedora 40 coming in April, it's almost time to download the beta and see what's new.
-
New Pentesting Distribution to Compete with Kali Linux
SnoopGod is now available for your testing needs
-
Juno Computers Launches Another Linux Laptop
If you're looking for a powerhouse laptop that runs Ubuntu, the Juno Computers Neptune 17 v6 should be on your radar.
-
ZorinOS 17.1 Released, Includes Improved Windows App Support
If you need or desire to run Windows applications on Linux, there's one distribution intent on making that easier for you and its new release further improves that feature.
-
Linux Market Share Surpasses 4% for the First Time
Look out Windows and macOS, Linux is on the rise and has even topped ChromeOS to become the fourth most widely used OS around the globe.
-
KDE’s Plasma 6 Officially Available
KDE’s Plasma 6.0 "Megarelease" has happened, and it's brimming with new features, polish, and performance.
-
Latest Version of Tails Unleashed
Tails 6.0 is based on Debian 12 and includes GNOME 43.
-
KDE Announces New Slimbook V with Plenty of Power and KDE’s Plasma 6
If you're a fan of KDE Plasma, you'll be thrilled to hear they've announced a new Slimbook with an AMD CPU and the latest version of KDE Plasma desktop.
-
Monthly Sponsorship Includes Early Access to elementary OS 8
If you want to get a glimpse of what's in the pipeline for elementary OS 8, just set up a monthly sponsorship to help fund its continued existence.