Maze Generation & Solving

Generating and solving a 2D maze is a surprisingly simple task. In order to first create a maze with a single unique solution, we define a maze, A, with dimensions m by n, to be an array of “cells”, which have four “sides”. Each side is a set of parameters:

  • Border: whether or not that side is part of the outlying border surrounding the maze.
  • Wall: whether or not that side is a wall which cannot be traversed.
  • Solution: whether or not that side is an open area which is part of the path one takes to reach the end up the maze successfully.
  • Backtrack: whether or not that size is an open area which has been traversed, but is not part of the “solution” path.
  • Coordinates: the [x,y] coordinates of the cell.

With these definitions in place, generating a maze is quite simple.

  • Create a stack structure to hold a set of type “cell”.
  • For each cell
    • For each side
      • Set all walls.
      • Clear all solutions and backtracks.
      • Set the coordinates appropriately.
      • Set the borders appropriately.
    • Create an index to keep track of the number of “visited” cells, v, and set it to zero.
    • Calculate the total number of cells, T=mn.
    • Pick an arbitrary starting point in the maze, [i,j].
    • Define the current cell under analysis, C, as the cell located at [i,j].
    • While v \le T:
      • Push the coordinates of C onto the stack.
      • Mark C as “visited”.
      • Generate a list of all the neighbouring cells of C with all four of their own walls untouched, L.
      • If \|L\| \geq 1
        • Randomly pick an element of L.
        • Push C onto the stack.
        • Smash down just the one wall between C and L.
        • Set C to be L.
      • Else
        • Pop the top item off of the stack, and set C to be equal to it.
      • EndIf
    • EndWhile

The end result is a long winding maze where there is only a single unique path between any two points. Solving it is also very straight forward. We pick a start and end point, and repeat the depth-first search while keeping track of cells we’ve already visited. When we finally find the destination, we backtrack to the starting point, indicating whether part of our backtrack is part of the solution path.

A final note: the depth-first search tends to generate long paths that are easy to solve even by hand. If you wish to generate more complicated mazes, consider doing a breadth-first search in the maze generation. Doing so is just a matter of swapping out the stack with a queue, and the majority of the pseudo code described above remains unchanged.

An animation demonstrating this algorithm is shown below, along with the original source code used to generate it. The animated GIF was generated by printing the entire maze to a series of text files and using ImageMagick to create the individual frames of animation and combine them into a GIF.

Maze generation and solving animation

Maze generation and solving animation

 

 

 

 

 

 

2 thoughts on “Maze Generation & Solving

Leave a Reply

Your email address will not be published. Required fields are marked *