ASCII Maze Generator

Project roadmap

1. 01

   Create the project and arguments

   ~1h

   Run cargo new maze and add rand. Read the width and height (each 2 to 60, default 20 and 10) and an optional --seed from std::env::args, parsing numbers with parse and printing a helpful message for invalid input. Use a StdRng created with seed_from_u64 when a seed is given, and a random seed otherwise, and print the seed used so a nice maze can be recreated. Done when: cargo run -- 15 8 --seed 7 parses the values and prints the seed.

2. 02

   Model the grid

   ~1.5h

   Define a Cell struct with four booleans for the walls (north, east, south, west) and a visited flag, and a Maze struct holding width, height and a Vec<Cell> of width × height cells, where index = y × width + x. Write a function that removes the wall between two neighboring cells on both sides. Done when: a new maze has every wall up, and removing a wall updates both cells.

3. 03

   Carve the maze

   ~2h

   Implement the recursive backtracker with a Vec used as a stack instead of recursion, so large mazes can't overflow: push the start cell and mark it visited. While the stack isn't empty, look at the top cell's unvisited neighbors; if there are any, pick one with the RNG, remove the wall between them, mark it and push it. Otherwise, pop. Done when: after generation, every cell is visited.

4. 04

   Draw the maze in ASCII

   ~1.5h

   Write render(&maze) -> String that draws each row as two lines: +---+ for top walls and | for side walls, with spaces for open passages. Open the outer wall at the top-left cell for the entrance and at the bottom-right cell for the exit. Done when: the printed maze looks right in the terminal, and the same seed always prints the same maze.

5. 05

   Solve and draw the path

   ~1.5h

   Add a --solve flag that finds the path from the entrance to the exit with breadth-first search (a VecDeque), moving only through open walls, and draws it with dots in the cells along the path. Done when: --solve draws a path that goes from the entrance to the exit without crossing any wall.

6. 06

   Write tests

   ~1.5h

   Write tests that check: every cell is reachable from the start (with a flood fill), the same seed produces the same rendered maze, the maze has exactly width × height − 1 openings between cells (which means it has no loops), and the solved path starts and ends in the right places. Done when: cargo test passes.

Resources

• DocsThe Rust Programming Language (book)
• DocsThe Rust Rand Book
• ArticleMaze generation algorithms (Wikipedia)
• DocsRust by Example