Mazes Mazes Mazes

I'll admit I like random software and this includes maze algorithms!

Mazes are fun to make and solve. Here is everything I know about mazes.

Here's my 3D printed maze using the

Hopefully I'll automate this process a little more so they look better and there are minimal manual steps. If you would like to buy one please email me! I'd love to share!

It could be that this is too elaborate and abstract for readers so feel free to see the code or external resources at the bottom.

Mazes Online

Terminology

• Maze: A 2D array of cells that make a grid of rows and columns.

• Set: A array of unique items.

• Visitor: A common algorithm pattern to visit parts of a Maze reducing redundancy.

• Maker: A Maze generation algorithm.

• Solver: A Maze solver algorithm.

This resource is intended to provide background into how these algorithms work for both making and solving so that means the visitor pattern can be optimized into your specific use case if you're making your own maker/solver.

Maze Visitor - Backtracking

• requireOpening: Used to require unvisited neighbors to have an opening to consider visiting it.

• shortCircuitBacktracking: Used to stop further visitation when the end cell is reached.

1. Visit the start cell.

2. Mark cell as visited.

3. If it is the end cell we've finished visiting the maze. ('backtrack')

4. Get all unvisited neighbors for the cell, check with

   requireOpening
   . If we don't have any we're at a dead-end. ('dead-end', 'backtrack')

5. Visit an unvisited neighbor and repeat from step 2, check with

   shortCircuitBacktracking
   . ('visit')

Maze Visitor - Flood Fill

• cellIdCount: Track cell to it's flood fill count.

1. Visit the end cell starting a count at 0.

2. Iterate cell(s) being visited and collect unvisited neighbors of the cell(s).

3. Mark cell as visited.

4. Mark cell with count. ('count')

5. Consider the cell visited. ('visit')

6. Collect all unvisited neighbors of the cell. If we don't have any we're at a dead-end. ('dead-end')

7. Visit all those collected unvisited neighbors increasing the count and repeat from step 2.

Maze Visitor - Flood Fill Count

• cellIdCount: Track cell to it's flood fill count.

1. Visit the start cell. ('visit')

2. Get the cell count.

3. Get cell neighbors with an opening.

4. If we're at the end cell or don't have neighbors, return.

5. Iterate through cell neighbors finding the cell neighbor with the lowest count.

6. Visit the cell neighbor with the lowest count. ('visit')

Maze Visitor - One Direction

• intersectionDirection: Which direction to follow.

1. Confirm starting and ending cells are on the edge of the maze.

2. Visit starting cell.

3. Follow the cell's intersection direction wall. ('visit_wall')

4. Yield the cell being visited until we find the exit cell. ('visit', 'dead')

Maze Visitor - Prims Randomized

1. Visit any cell.

2. Create a frontier array with the cell.

3. Iterate through the frontier array until it's empty.

4. Select a random cell from the frontier array.

5. Mark cell as visited.

6. Get all unvisited neighbors for the cell. If there are no unvisited neighbors this path reached a dead end. ('dead-end')

7. Consider this cell visited. ('visit')

8. Get a random unvisited neighbor and add it to our frontier array.

Maze Maker - Ellers

1. Yield a row of cells with walls up. ('row_visit')

2. If no sets exist create one for each cell in the first row. Assign each cell to the created set.

3. Iterate through each cell of the row.

   1. If the current cell and the next cell are in different sets, randomly decide to remove the right wall (connecting the cells). ('removal_visit')

   2. If the cells connect, merge the cells' sets together.

4. Yield the next row of cells with walls up. ('row_visit')

5. Iterate through each set of the current row.

   1. Randomly select a single cell from the set to remove the bottom wall, add the bottom neighbor to the set. ('removal_visit')

6. If the next row is the last row join all adjacent cells that do not share a set. ('removal_visit')

Maze Maker - Binary Tree

1. Iterate all rows and columns - removing a top or left wall depending on where the cell is positioned.

   1. If the cell is in the top left corner => yield no direction.

   2. If the cell is on the top row => yield left direction.

   3. If the cell is on the left column => yield top direction.

   4. If the cell is not on the top or left edge => yield a random top or left direction.

Maze Maker - Backtracking

1. Iterate all rows and columns. Yield each cell as we go. ('layer_visit')

2. Iterate the backtracking visitor.

   1. If the result is a normal visit, remove the wall. Yield removed cell. ('removal_visit')

   2. If the result is a dead-end, are we creating a multi-solution maze? If so remove a random wall. ('removal_visit')

Maze Maker - Prims Randomized

1. Iterate all rows and columns. Yield each cell as we go. ('layer_visit')

2. Iterate the prims randomized visitor.

   1. If the result is a normal visit, track the visitation and remove the wall. Yield removed cell. ('removal_visit')

   2. If we are creating a multi-solution maze remove a random wall. ('removal_visit') This is not done in the dead-end result because dead ends are a bit different in prims randomized than, for instance, the backtracking visitor.

Maze Solver - One Direction

1. Iterate the one direction visitor.

Maze Solver - Backtracking

1. Iterate the backtracking visitor.

2. If the result is a visit. Yield cell. ('visit')

3. If the result is a dead-end. Yield cell ('dead')

4. If the result is a backtrack. Yield cell ('solution', 'backtrack')

Maze Solver - Flood Fill

1. Iterate the flood fill visitor.

2. If the result is a count. Yield cell. ('flood_visit')

3. Yield that the maze was flooded. ('flooded')

4. Iterate the flood fill count visitor.

5. If the result is a visit. Yield cell. ('solve_visit')

External Resources

• Blog - Jamis Buck Jamis even has a book called Mazes for Programmers!

Roadmap

• Update this with the maze demos.