Creating and solving mazes with Go
Programming Snapshot – Go Mazes
Mazes fascinated even the ancient Greeks. Mike Schilli uses his Go programming skills to create a maze and then efficiently travel through it.
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.
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.
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.
Listing 1
maze.go
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.
Listing 2
manip.go
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.
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.
Listing 3
Array Slice Pop in Go
last = slice[len(slice)-1] slice = slice[:len(slice)-1]
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
-
Gnome 47.2 Now Available
Gnome 47.2 is now available for general use but don't expect much in the way of newness, as this is all about improvements and bug fixes.
-
Latest Cinnamon Desktop Releases with a Bold New Look
Just in time for the holidays, the developer of the Cinnamon desktop has shipped a new release to help spice up your eggnog with new features and a new look.
-
Armbian 24.11 Released with Expanded Hardware Support
If you've been waiting for Armbian to support OrangePi 5 Max and Radxa ROCK 5B+, the wait is over.
-
SUSE Renames Several Products for Better Name Recognition
SUSE has been a very powerful player in the European market, but it knows it must branch out to gain serious traction. Will a name change do the trick?
-
ESET Discovers New Linux Malware
WolfsBane is an all-in-one malware that has hit the Linux operating system and includes a dropper, a launcher, and a backdoor.
-
New Linux Kernel Patch Allows Forcing a CPU Mitigation
Even when CPU mitigations can consume precious CPU cycles, it might not be a bad idea to allow users to enable them, even if your machine isn't vulnerable.
-
Red Hat Enterprise Linux 9.5 Released
Notify your friends, loved ones, and colleagues that the latest version of RHEL is available with plenty of enhancements.
-
Linux Sees Massive Performance Increase from a Single Line of Code
With one line of code, Intel was able to increase the performance of the Linux kernel by 4,000 percent.
-
Fedora KDE Approved as an Official Spin
If you prefer the Plasma desktop environment and the Fedora distribution, you're in luck because there's now an official spin that is listed on the same level as the Fedora Workstation edition.
-
New Steam Client Ups the Ante for Linux
The latest release from Steam has some pretty cool tricks up its sleeve.