The Maze Algorithm

For those interested in how the program creates a random maze, this section is for you!

There are two algorithms used here, a maze generator and a maze solver. The maze consists of a grid of boxes. Each box is numbered sequentially and initially contains 4 walls surrounding each grid. Using a random number generator, a box is selected from the grid and one of the 4 walls is removed making an opening with an adjacent box.  The adjacent box receives the same sequence number as the selected box as well as all the other boxes sharing the same sequence number. This ensures that a maze loop is not created, which will cause a problem with the maze solver algorithm. Also, walls are not removed if the adjacent box has the same sequence number or is on the border. Breaking walls on random boxes continues until all boxes have the same sequence number. This ensures all boxes are connected to each other.

Since the boxes are all connected, any location along the perimeter can act as a start and end location. The algorithm puts the start and end location on opposite sides, but it does not matter which end you start from.

For the maze solver, it traverses through the maze from the start of the maze, making right turns at every intersection, until it reaches the end. This may cause some backtracking when a dead end is encountered, but it eventually finds the end of the maze. After removing the backtracking moves, the solution path is then overlaid on top of the maze.

This guide was first published on Jul 19, 2019. It was last updated on Jul 19, 2019. This page (The Maze Algorithm) was last updated on Sep 17, 2019.