Getting lost and found with the C# Maze Generator and Solver | Coding4Fun Blog | Channel 9

Getting lost and found with the C# Maze Generator and Solver | Coding4Fun Blog | Channel 9

The Maze Generation

Depth-First Search and Breadth-First Search are very useful approaches in many applications. One of them is creating/solving mazes. To generate a maze with DFS, we have this simple algorithm:

• Have all walls in your maze intact (not broken).
• Choose a random start point, push it into the stack. Call this initial square 'current square'.
• Repeat while the stack is not empty:
  • Get list of all neighboring squares to the current square where those neighbors have all their walls intact (unvisited).
  • If there are neighbors (i.e., List.Count > 0):
    • Choose one of the neighbors at random. Call it 'temp'.
    • Knock the wall between 'temp' and the current square.
    • Push the current square into the stack.
    • Make the current square equals 'temp'.
  • Else if there are no neighbors, pop a square from the stack. Make current square equal to it.

After executing this algorithm, you will have a 'prefect maze' which indicates that your maze doesn't have 'dead ends' (i.e., unreachable squares) and has a single solution.

BFS generation is the same except the stack that will be replaced with a queue.

If the generation is with DFS, the program will choose a random wall and knock it, then it moves to the new square. When it reaches an edge (or visited cell), it backs again to the nearest "UNVISITED" square.

When generation is with BFS, program will knock the wall in a way similar to DFS, but BFS uses queue, causing to finish near squares first before the far ones. In contrast, DFS uses stack, which causes it to finish far first then back to near.

Read full article from Getting lost and found with the C# Maze Generator and Solver | Coding4Fun Blog | Channel 9