Recursive Backtracking Maze Generator & Solver

Project roadmap

1. 01

   Represent the maze

   ~1.5h

   Represent the maze as a width × height grid of cells, each storing which of its four walls are present as bit flags, allocated with malloc based on the size given on the command line (with limits, such as 2 to 100). Start with all walls present. Write helper functions to get a cell, check bounds, and remove the wall between two neighboring cells (on both sides). Done when: a grid is created and freed without leaks.

2. 02

   Generate with recursive backtracking

   ~2h

   Starting from a cell, mark it visited, then visit its unvisited neighbors in random order (shuffled with rand seeded by a --seed option or the time), removing the wall to each before recursing. For large mazes, replace recursion with an explicit stack array to avoid stack overflow. Done when: every cell is reachable, and the same seed always gives the same maze.

3. 03

   Draw the maze

   ~1.5h

   Draw the maze with + for corners, --- for horizontal walls, | for vertical walls and spaces for passages, with the entrance at the top left and the exit at the bottom right opened. Done when: the printed maze looks correct and has an opening at the entrance and exit.

4. 04

   Solve with breadth-first search

   ~2h

   Implement BFS with a queue (a circular array of cell indexes): start at the entrance, visit each reachable neighbor (where there's no wall) once, remembering the cell it was reached from, until the exit is found. Then follow the parents back to build the shortest path. Done when: the solver finds the path, and its length is the shortest possible.

5. 05

   Show and animate the solution

   ~1.5h

   Mark the path on the drawing (for example with dots or a color using ANSI codes), and with --animate redraw the maze as the search explores cells, pausing briefly between steps (with nanosleep) and moving the cursor to the top instead of scrolling. Done when: the solution path is shown clearly, and the animation plays smoothly.

6. 06

   Test it

   ~1h

   Write tests with assert: every cell is reachable after generation (checked with a BFS from the entrance), the number of removed walls is exactly cells minus one (a perfect maze), the same seed gives the same maze, and the solved path is valid (each step goes through an open wall). Run under valgrind. Done when: the tests pass with no memory errors.

Resources

• ArticleMaze generation algorithm (Wikipedia)
• ArticleJamis Buck: recursive backtracking
• ArticleBreadth-first search (Wikipedia)
• ArticleRed Blob Games: introduction to pathfinding
• DocsBeej's Guide to C Programming