visualizing mazes

return to main page

algorithms

  1. binary tree algorithm
  2. growing tree algorithm
  3. sidewinder algorithm
  4. recursive backtracker algorithm
  5. eller's algorithm
  6. hunt and kill algorithm
  7. wilson's algorithm
  8. aldous-broder algorithm

binary tree algorithm

This algorithm follows one rule: every cell randomly connects with its northerly or easterly neighbour.

Speed

growing tree algorithm

This algorithm runs the following rules:

  1. Let 'C' be an empty list of cells. Add any cell to C.
  2. Pick any cell in C and connect it with any of its unvisited neighbours.Add the neighbour to C. If all of cell's neighbours have been visited, remove the cell from C.
  3. Repeat #2 until 'C' is empty.

Speed

sidewinder algorithm

This algorithm runs the following rules:

  1. Start at the top-left corner, working left-to-right on each row. Let 'C' be a list continuous horizontally-linked cells.
  2. Add the current cell to C and choose whether or not to make an easterly connection.
    • If so, make the easterly cell the current cell and repeat step 2.
    • If not, choose any cell in C and connect it with a northerly cell. Clear C and repeat step 2.

  3. Continue until all cells have been visited.

Speed

recursive backtracker algorithm

This algorithm runs the following rules:

  1. Pick any cell.
  2. Connect with any unvisited neighbour and set that neighbour as the current cell.
  3. If all neighbours have been visited, move back to the last cell with unvisited neighbours.
  4. Repeat steps 2-3 until the algorithm moves back at the starting point.

Speed

eller's algorithm

This algorithm runs the following rules:

  1. Put each cell in the first row in its own group.
  2. Randomly connect neighbouring cells of different groups, merging their groups as you go.
  3. For each group, create at least one vertical connection to the next row. Add the newly connected cell to the group.
  4. In the next row, give each unvisited cell its own set.
  5. Repeat steps 2-4 until the last row.

Speed

hunt and kill algorithm

This algorithm runs the following rules:

  1. Pick any cell.
  2. Connect with any unvisited neighbour and set that neighbour as the current cell.
  3. If all neighbours have been visited, scan for unvisited cells with visited neighbours, starting at the top-right corner.
  4. Set the first match as the current cell and perform step 2 .

Speed

wilson's algorithm

This algorithm runs the following rules:

  1. Pick any cell, mark it as visited and set it as an end point.
  2. Pick any cell and set it as a starting point. Move to any neighbour, storing the latest direction of motion.
  3. Repeat step 2 until you reach a visited cell.
  4. Return to the starting point, and follow the stored directions to the end point, marking them as visited and building connections as you go.
  5. Repeat steps 2-4 until every cell has been visited.

Speed