Maze

Find path through a 2D grid maze, or generate a random solvable 2D maze

Input/Output

The generated mazes are specified in a text file using "ascii art".

./dat/maze1.txt
format maze
+---+---+---+---+---+
s   |               |
+   +   +   +---+---+
|   |   |           |
+   +---+---+---+   +
|   |               |
+   +   +---+---+   +
|       |           |
+---+---+   +---+---+
|                   e
+---+---+---+---+---+

'+' represents the corner of a cell
'|' represents a vertical wall between two cells
'---' represents a horizontal wall between two cells
's' start cell
'e' end cell
'*' represents a cell visited on the solution path

Algorithm

The path through the maze is found using breadth first search

Two maze generation algorithms are used:

• binary tree produces simple easily solved mazes. https://en.wikipedia.org/wiki/Maze_generation_algorithm#Simple_algorithms
• recursive division produces more complex mazes. https://en.wikipedia.org/wiki/Maze_generation_algorithm#Recursive_division_method

Command line help

C:\Users\James\code\PathFinder\bin>maze --help

 --cols         count   columns in generated maze
 --gen          bin|rec generate maze with binary or recursive algorithm
 --help                 produce help message
 --rows         count   rows in generated maze
 --solve        fname   solve a maze

Solver Example

C:\Users\James\code\PathFinder\bin>maze --solve ../dat/maze1.txt
5 rows 5 cols
+---+---+---+---+---+
| * |               |
+   +   +   +---+---+
| * |   |           |
+   +---+---+---+   +
| * | *   *   *   * |
+   +   +---+---+   +
| *   * | *   *   * |
+---+---+   +---+---+
|         *   *   * |
+---+---+---+---+---+

Generator Example

C:\Users\James\code\PathFinder\bin>maze --gen bin --rows 5 --cols 5
5 rows 5 cols
+---+---+---+---+---+
                    |
+   +---+---+   +   +
|           |   |   |
+   +---+   +   +   +
|       |   |   |
+   +   +   +---+---+
|   |   |           |
+   +---+---+---+---+
|                   |
+---+---+---+---+---+