Building a Maze Generator (and learning Go)

Building a Maze Generator (and learning Go)

What is it?

It’s a maze generator built in Golang, featuring a user interface powered by rivo/tview and tcell. You can pick from a list of maze generation algorithms and then watch them being solved using either Breadth-First Search (BFS) or Depth-First Search (DFS) immediately or my sequence. No more squinting at your code trying to figure out what this loop, recursive function, and if condition do!

Why Build It?

Over the Christmas break, I decided to revisit algorithms a bit to polish my skills. But as I dove into some of the more complex ones, my brain started to drift off more as I became less interest in how it function and more in what side project I should work on next. The hard part of it, is visualizing how to program the workflow of the said algorithm, for example, Graphs - BFS. I thought, “Okay, let’s take a break, regroup, and come back later when I have a fresher mindset.” Spoiler: that didn’t happen. Instead, I jumped back into learning Golang, and then it hit me: What if I built a visualizer to untangle the complexities of graph algorithms, and did it in Go? Two birds, one stone, kinda situation. I could continue to master a cool new language and get a tool to help me not feel so dumb about graph algorithms. Plus, I got to play with Goroutines.

How it started

This little contraption of mine started of with me doing a bunch of research on Youtube, Wikipedia, and articles about graph algorithm and how it is use to generate unpredictable maze and predictable maze alike. Prim's, Kruskal, Wilson's, and Depth First Search to name a few, and a lot was contributed by researcher to understand how all these work in a beautiful way.After I did enough research to understand the process behind the creation of the maze, I move on to solving a bigger problem. How do I draw the maze? I work as a Full Stack developer for about 3+ years now and during that time I have built countless web and mobile interfaces, and I started to get bored of doing it, but then I remember my countless time spend pimping my laptop to work with Arch Linux and favouriting any UNIXPorn I came across. It hit me, what if I built it in a Terminal user interface (TUI).

After a bit of searching online, I found 2 packages that can help me build out the UI, tview and tcell which both work wonder in structuring the application in the terminal.

The Struggle

I hit a few roadblock along the way when I build out the interface for the maze.

Carving the 2D array in

This was the first roadblock I hit, carving a marble slab stone for me to draw my maze on. The difficult part was getting the character to align correctly so that a horizontal wall and a vertical wall look perfectly in-sync with each other to make a corner. Now I could just use "|" and "_" and that would simplify things much for me, but I'm a snob at making thing harder for myself sometime.

Solving this problem resolve around me having to double up every wall I have in my maze that mean for a wall it will have double the block character of U+2588 █

This ensure that I have a perfect block style maze. The only problem I need to worry about is remember that everything is double now, couldn't be that hard right? Right...?

Double Trouble

After deciding on the strategy to double the character when creating the wall, you would imagine it be a set and forget kinda thing, but that would soon haunt me forward when I start applying the algorithm to create a maze.

Take a look at the code snippet bellow for reference as to how I would double or divide by 2 to get the correct pointer or path.

The creation of the maze marble require me to double it up

    mazeRows := (totalRows/2)*2 + 1
	mazeCols := (totalCols/2)*2 + 1

Random Entrance and Exit calculation

    entranceCol := 1 + 2*rand.Intn((mazeCols-1)/2)
	exitCol := 1 + 2*rand.Intn((mazeCols-1)/2)

And the funnest part of creating the maze

func (m *MazeGenerator) generateDFSMaze(maze [][]bool, mazeRows, mazeCols int) {
	startCol, startRow := 1, 1
	maze[startRow][startCol] = false
	stack := []Point{{startCol, startRow}}

	dCol := []int{2, 0, -2, 0} // double the step I need to take for each cell
	dRow := []int{0, 2, 0, -2} // double the step I need to take for each cell

	for len(stack) > 0 {
		current := stack[len(stack)-1]

		var unvisited []int
		for dir := 0; dir < 4; dir++ {
			newCol := current.col + dCol[dir]
			newRow := current.row + dRow[dir]

			if newCol > 0 && newCol < mazeCols-1 && newRow > 0 && newRow < mazeRows-1 && maze[newRow][newCol] {
				unvisited = append(unvisited, dir)
			}
		}

		if len(unvisited) == 0 {
			stack = stack[:len(stack)-1]
			continue
		}

		dir := unvisited[rand.Intn(len(unvisited))]
		newCol := current.col + dCol[dir]
		newRow := current.row + dRow[dir]

		maze[newRow][newCol] = false
		maze[current.row+dRow[dir]/2][current.col+dCol[dir]/2] = false

		stack = append(stack, Point{newCol, newRow})
	}
}

After getting everything line up correctly and the maze created, the next huddle I need to solve is solving the maze itself and communication it through the log with goroutine.

Solving the Maze with Style

After conquering the maze generation, the next challenge was implementing the solving algorithms and making them visually engaging. This meant not just finding a path from start to finish, but showing the exploration process in real-time.

The solution involved three main components:

The solving algorithms (DFS and BFS)
A logging system to show progress
Goroutines for non-blocking UI updates

func (s *Solver) SolveMaze(m *MazeGenerator, mazeStr string, searchType SearchType) string {
	if mazeStr != "" {
		m.originalMaze = mazeStr
	}
	m.clearMaze()

	maze, start, end, err := s.parseMaze(m.originalMaze)

	if err != nil {
		return err.Error()
	}

	visited := make([][]bool, len(maze))
	parent := make(map[Point]Point) // for BFS
	for i := range visited {
		visited[i] = make([]bool, len(maze[0])/2)
	}

	if m.fastMode {
		m.isSolving = false
		path := make(map[Point]bool)
		var success bool
		if searchType == DFSSearchType {
			success = s.dfs(m, maze, start, end, visited, path, nil, nil)
		} else {
			success = s.bfs(m, maze, start, end, visited, path, parent, nil, nil)
		}
		if success {
			return s.visualizeExploration(m, maze, path)
		}
		return "No solution found"
	}

	path := make(map[Point]bool)
	updates := make(chan string)
	var finalSolution string

	// Printing out the steps and log in seperate of the main thread
	go func() {
		defer close(updates)
		defer func() {
			m.isSolving = false
		}()

		stepCount := 0

		var success bool
		if searchType == DFSSearchType {
			m.logger.LogStart("DFS")
			success = s.dfs(m, maze, start, end, visited, path, updates, func() {
				stepCount++
				m.logger.LogStep(stepCount, start.col, start.row, false)
			})
			m.logger.LogComplete(stepCount, 0)
		} else {
			m.logger.LogStart("BFS")
			success = s.bfs(m, maze, start, end, visited, path, parent, updates, func() {
				stepCount++
				m.logger.LogStep(stepCount, start.col, start.row, false)
			})
			m.logger.LogComplete(stepCount, 0)
		}

		if !success {
			m.logger.LogNoSolution()
		}
	}()

	for update := range updates {
		finalSolution = update
	}

	return finalSolution
}

One of the trickiest parts of building this interactive and visual maze solver was ensuring that the UI remained responsive while processing the maze generation and solving algorithms. Go's concurrency model through Goroutines proved to be the perfect solution for this challenge. By leveraging Goroutines, I could run the maze solving algorithms in separate threads, allowing the UI to stay snappy and responsive while displaying real-time updates of the solving process. This meant users could watch the exploration unfold without any freezing or stuttering in the interface.

End Result

After tackling all these technical challenges - from perfecting the wall rendering to implementing concurrent visualization - the end result exceeded my initial expectations. The maze generator now supports three powerful generation algorithms: Prim's, Kruskal, and Depth-First Search (DFS). Each algorithm brings its own unique characteristics to the maze patterns it creates. Users can not only generate these diverse mazes but also watch them being solved in real-time using either Breadth-First Search (BFS) or DFS, with the solving process beautifully visualized step by step in the terminal interface.

Credit

Huge thank you to all these articles and Github repo that made it possible for me to understand the problem, the patterns and the solution. If you want to take a closer look at the project, visit here Crete

https://www.freecodecamp.org/news/prims-algorithm-explained-with-pseudocode/ https://www.algosome.com/articles/maze-generation-depth-first.html https://medium.com/swlh/maze-generation-with-depth-first-search-and-recursive-backtracking-869f5c4496ad https://professor-l.github.io/mazes/ https://weblog.jamisbuck.org/2011/1/10/maze-generation-prim-s-algorithm

Reading time