Maze Algorithm Visualizations

Algorithms Used

• Recursive Backtracking
  1. Create a walker, starting from a random spot on the grid
  2. Walk to a random unvisited neighbor and carve a wall in between
  3. If all neighbors are visited, backtrack to the last cell and try again
  4. The maze is finished when we backtrack all the way back to the start
  • Creates long, winding corridors
  • Few branches - can only create branches when a dead-end is reached
• Recursive Division
  1. Collect all of the cells into a chamber
  2. Split the chamber with a wall horizontally or vertically, then cut a hole in the wall
  3. Repeat for each subchamber until a region cannot be split anymore or a size threshold is reached
  • Very quick - Can quickly split large spaces into smaller chambers
  • Has obvious walls and bottlenecks due to how recursively cut rectangles into smaller and smaller rectangles within itself
• Blobby Recursive Division
  Algorithm from Jamis Buck's blog
  1. Collect all the cells in the maze into a single region.
  2. Split the region into two, using the following process:
     1. Choose two cells from the region at random as “seeds”. Identify one as subregion A and one as subregion B. Put them into a set S.
     2. Choose a cell at random from S. Remove it from the set.
     3. For each of that cell's neighbors, if the neighbor is not already associated with a subregion, add it to S, and associate it with the same subregion as the cell itself.
     4. Repeat 2.2 and 2.3 until the entire region has been split into two.
  3. Construct a wall between the two regions by identifying cells in one region that have neighbors in the other region. Leave a gap by omitting the wall from one such cell pair.
  4. Repeat 2 and 3 for each subregion, recursively.
  • Based off of the recursive division algorithm, but avoid the issue of straight lines by creating more natural walls
  • Much slower than the original algorithm
• Aldous-Broder algorithm
  1. Create a walker, starting from a random spot on the grid
  2. Walk to a random neighbor, carving a hole in between if that neighbor is unvisited
  3. Repeat until all cells are visited
  • Creates a uniformly spanning tree, ie. corridors, dead-ends, and junctions are completely random, and the maze has no distinguishable features unlike Recursive Division's chambers
  • Very slow - Fast in the beginning but slows down by the end, as there are less cells to carve
  • Not guaranteed to finish - Could keep generating for forever!
• Wilson's algorithm
  1. Create a walker, starting from a random spot on the grid. Initialize one of the cells as part of the maze
  2. Randomly walk around the grid, keeping track of the direction taken when leaving a cell
  3. When the walker arrives at a part of the maze, return to the walker's start and follow the directions taken at each cell
  4. Move the walker to a random unvisited cell and repeat the walk until all cells are visited
  • Creates a uniformly spanning tree
  • Very slow - Slow at the start, but gets faster as it creates more cells for it to path back to
  • Not guaranteed to finish - Could keep generating for forever!
• Aldous-Broder + Wilson's hybrid algorithm
  • A mix of the Aldous-Broder and Wilson's algorithm, using the former at the start to create a large amount of visited cells for the latter to path back to
  • May not create a uniformly spanning tree (Haven't researched that yet)
  • Average to slow - Faster than its constituent algorithms but still takes longer than other algorithms due to its randomness
  • Not guaranteed to finish - Could keep generating for forever!
• Binary Tree
  1. Start at the corner of the grid opposite to a chosen directional bias (eg. south-east, north-west)
  2. For each cell, carve a wall randomly in one of the chosen directions (horizontal or vertical). If a direction is blocked, choose the other.
  3. When the last cell is reached, the maze is complet
  • Creates a binary tree, as the name suggests
  • Has a strong diagonal bias, as well as long corridors at the two end edges
  • Memory efficient - Its main selling point. As it only looks at the current cell, it needs very little state. If using a seedable PRNG, instead of keeping the maze in memory, it can just regenerate the maze when needed. This allows for absolutely massive mazes that don't use too much memory
• Kruskal's
  1. Make a set E of all edges in the maze
  2. While E is not empty:
     1. Set A as a random edge from E and remove it from the set
     2. If the sets at each side of A are disjoint, remove/carve A from the maze.
  • Slow - the number of edges are directly proportional to the width and height of the grid
  • Creates many short dead-ends
• Prim's
  1. Choose a random cell as the starting point, and add its neighbors to the set F
  2. While set F is not empty:
     1. Set C as a random cell in F and remove it from the set
     2. Carve a wall from C to any adjacent visited cell
     3. Add all unvisited neighbors of C to F
  • Creates many short dead-ends
  • All paths tend to go back to the algorithm's starting point, which may be undesirable
• Eller's
  1. Initialize the first row by adding each cell into their own set
  2. For each row except the last:
     1. Merge some of the sets together
     2. For each set, pick a random cell in the set and carve down to the next row.
     3. Initialize the next row's remaining cells in their own set
  3. On the last row, connect every disjoint cell together
  • Slow/Quick - Can be fast if set operations are fast and went row-by-row instead cell by cell
  • Can create infinitely long or tall mazes
  • Usually creates a long corridor at the end where most paths pass through
• Sidewinder
  1. Start from the corner cell, and create set R
  2. For each cell C:
     1. Add C to R
     2. Decide whether to carve to the next cell or not
     • If on the first row, carve to the next cell
     • If at the end of the column, do not carve
     • Otherwise, pick randomly
     3. If we did not carve, pick a random cell to carve vertically from. Empty set R
  • The Sidewinder is called so because you can solve the maze from bottom to top by winding side to side and going up when possible
  • Creates a long corridor at the top where most paths pass through
  • It is impossible for northern dead-ends to occur with this algorithm
• Hunt And Kill
  1. Create a walker, starting from a random spot on the grid
  2. Walk to a random unvisited neighbor and carve a wall in between
  3. If all neighbors are visited, "hunt" for an unvisited cell neighboring a visited cell and start the walker from there
  4. The maze is finished when we can no longer find any unvisited cells
  • Very similar to the recursive backtracking in features and generation, the only difference is that instead of backtracking, it searches through the maze instead.
  • My implementation includes an optimization where it remembers the row it last found an unvisited cell, which speeds up the later phases when most of the maze is already visited
  • Slow - Only updates one cell per step and can take some time to find an unvisited cell when in the hunt phase
• Growing Tree
  1. Create list S and initialize it with a random cell
  2. While S is not empty:
     1. Pick cell C from the list
     2. Select a neighbor of C to carve to and add it to the S. If there are no unvisited neighbors, remove C from S
  • While simple, the fun of this algorithm comes from how you pick cells from the list
    • Picking the newest/last leads it to act like the Recursive Backtracking Algorithm
    • Picking randomly leads it to act like Prim's
    • Picking the oldest/first leads it to create long straight corridors
    You can also mix these picking styles to create interesting and varied mazes
EXTRA: Maze Solver algorithms
• Flood-Fill Algorithm
  1. Create a list L of all dead-ends in the maze
  2. While L is not empty:
     1. Pick a random dead-end D and fill it in
     2. If D has a neighbor with a wall count (including filled in cells) greater than 1, add it to L
  • If a maze is imperfect (has loops, multiple solutions), it will feature multiple unfilled paths. BFS, A*, or a similar algorithm could then be used to find the shortest route among them
  • Requires full knowledge of the maze, unlike other algorithms that use walkers
• A*
  Better explanation: Wikipedia
  1. Create the following:
     • Set O containing the set of all open/fringe/frontier nodes
     • Map G containing the cost of traveling to a node
     • Function H that calculates the hueristic for any given cell, which can be the distance from the node to the end node
     • Map F to store the sum of a node's G and H
     • Map P to store a nodes parent
     Let start be the start of the maze, and initialize O, G[start], and F[start] with start, 0 and H(start), respectively
  2. While O is not empty:
     1. Let N be the node in O with the lowest F, and remove it from the set
     2. If N is the destination, end the search and trace the path by following P[goal] until start is reached
     3. For each of N's neighbors M:
        1. Let New_G be the cost of going from N to M
        2. If New_G < G[M], then:
           1. Add M to O
           2. Set P[M] to N
           3. Set G[M] to New_G
           4. Set F[M] to New_G + H(M)
  3. If O is empty, the search has failed
  • Used to trace the path from the dead-end filling or to solve mazes with rooms, as is the case with blobby recursive division