Length of the Solution Path

Currently, our maze solvers show the path they found, but they don't say how long it is. That's not a huge deal as you can get the job done with standard Unix tools like this:

./amaze -n -o mazes/maze-201x201-solved.txt mazes/maze-201x201.txt
tr -cd 'o' < mazes/maze-201x201-solved.txt | wc -c

But it might be nice if the solver just told you how long the path was. You could add a countState() member function to the Maze class that counts how many cells are in a given state. And then print that value out at the end of solveMazeDFS() and solveMazeBFS() (i.e., send it to std::cerr).

Number of Cells Explored

Another interesting statistic is how many cells the solver explored, which is a measure of how much work the algorithm did, and can be quite different from the length of the solution path. You would need to add a bit of extra bookkeeping in the solver functions, but not much.

Make Your Own Mazes #1 (The Easiest Way)

Rather than writing code to make mazes, you can just create your own maze text files. The format is simple: Walls are #, paths are spaces. You've seen plenty of examples in the mazes/ directory. Just make sure your maze has walls around the edges, and a single start and end point (two gaps in the rectangular outer wall).

Make Your Own Mazes #2 (An Easy-ish Way)

It's fairly easy to turn any text file into a possible maze.

• Read all the lines of the file.
• Find the longest line, and pad all the other lines with spaces to make them the same length.
• Change all non-space characters to #.
• Add a line of # characters to the top and bottom.
• Add a # character to the start and end of each line.

That's it. You could code this in whatever language you like. It's pretty straightforward in C++, but you could use Python or any other language you're comfortable with.

To keep the autograder happy, put your program and any mazes you make in the mazes/ directory.

Make Your Own Mazes #3 (Challenge Mode)

For a bigger challenge, you could implement a maze-generation algorithm. Wikipedia has a whole page on this topic, with links to many different algorithms. In particular, the randomized depth-first search algorithm has a lot in common with the DFS maze solver we implemented, so it might be a good place to start.

Implement your algorithm using the generateMaze function stub in solver.cpp.

A Simpler Solver

Another way to solve perfect mazes is to use the “right-hand rule”: Keep your right hand on the wall, and follow it. This is a simple algorithm that doesn't require any extra data structures like stacks or queues. It won't work for mazes with loops, but it will work for perfect mazes like the ones we're using.

Add a new solveMazeRightHandRule function to solver.cpp that implements this algorithm. Add code to amaze.cpp to call it when the -r or --right-hand flag is given.

Math Fun with Resizing Strategies

Here's a mathy one!

Let’s compare how many total element moves (copies) happen after inserting n items, assuming we copy all existing elements on each resize.

To keep things simple, let's assume we start with an empty vector and only consider the copies that happen during resizing (not the initial insertions).

• For doubling, start with capacity 1 and double whenever the array is full.
• For add-K, start with capacity K and grow by +K whenever the array is full.

Doubling (capacity: 1, 2, 4, 8, …)

Every time we resize from capacity \(2^i\) to \(2^{i+1}\), we copy \(2^i\) elements. If we have inserted \(n\) items total, the resizes happen at capacities \(1,2,4,\dots\) up to the largest power of two less than \(n\).

\[ \text{Total copies}(n) = \sum_{i=0}^{\left\lfloor \log_2(n-1) \right\rfloor} 2^i = 2^{\left\lfloor \log_2(n-1) \right\rfloor + 1} - 1 \;\le\; 2n - 1. \]

Add-K (capacity: K, 2K, 3K, …)

Let \(m = \left\lceil \frac{n}{K} \right\rceil - 1\) be the number of resizes. At the \(j\)-th resize \(for (j=1,\dots,m)\), the current size is \(jK\), so we copy \(jK\) elements.

\[ \text{Total copies}(n) = \sum_{j=1}^{m} jK = K \cdot \frac{m(m+1)}{2} \approx \frac{n^2}{2K} \]

Your Turn

Given these formulas, what's the average number of copies per insertion for each strategy? Which strategy is better for large \(n\)? What happens if you change \(K\)?

Graphical Maze Output

Our Maze class is very ASCII-centric. But we could make bitmap graphics instead. There is a neat format called PBM/PGM/PPM that is very simple to write. You can create a PPM file by writing a text file with this format:

P3
# This is a comment
width height
max_color_value
R G B R G B R G B ...
R G B R G B R G B ...
...

Where

• P3 is a magic piece of text that identifies the file type
• width and height are the dimensions of the image in pixels
• max_color_value is the maximum value for each color channel (usually 255)
• The rest of the file is a list of RGB color values for each pixel, in row-major order (i.e., left-to-right, top-to-bottom).

You could add a writePPM() member function to the Maze class that writes the maze to a PPM file. You could use different colors for walls, paths, the solution path, and visited cells.

You can then convert the PPM file to a PNG file using the Netpbm tools,

ppmtopng maze.ppm > maze.png

and view it in your editor or browser.

Make a Heat Map

Our BFS solver actually finds the shortest path from the start to every cell in the maze. Using the same ideas as the Graphical Maze Output section above, you could create a heat map that shows how far each cell is from the start. Cells that are closer to the start could be colored blue, and cells that are farther away could be colored red, with a gradient in between.

Characterizing Mazes

You might think that one “random maze” is just like any other. But that’s not really true. Some mazes are “easier” than others. You could try to come up with some metrics to characterize how “hard” a maze is. For example, think about

• Size: Larger mazes might be harder simply because they have more paths to explore.
• Branching Factor: Mazes with more branches (i.e., more choices at each step) can be more complex.
• Dead Ends: A maze with many dead ends might be harder to solve, as it requires more backtracking.
• Path Length: The length of the shortest path from start to finish could be a measure of difficulty.
• Wall Density: More walls might mean fewer paths, increasing difficulty.

You could write a program that computes these (or other!) metrics for a given maze and then see how they correlate with how long it takes your solver to find a solution.

Advent of Code

Advent of Code is an annual set of programming puzzles that are released every December. Many of the puzzles involve maps where # are walls and . are open spaces, similar to our mazes. In addition, many of the puzzles are designed to be solved using search strategies like DFS and BFS.

As an example,

• Day 6 of Advent of Code 2024 working out how many positions a patrol guard will visit on a grid, given a set of obstacles.
• Day 12 of Advent of Code 2022 involves finding the shortest path on a heightmap, which is very similar to our maze problem but generalized.

You'll likely have to make significant changes to your code to solve these problems, so if you choose this option, copy the entire maze/ directory to a new directory (e.g., aoc/) and work there.