HTML5 Maze generator and solverPosted on 1 October 2012 in Techstuff
I came across this website which is about mazes and the algorithms there are to generate and solve them. It is an interesting site and i wondered if i could translate the algorithms textual explanation to a program. I also wanted to display animations so you can see how the different algorithms do their work.
Backtracker The backtracker algorithm picks a random starting cell and starts to randomly
carve passages in random directions. The cells that are carved into are marked as visited. When no unvisited
cells are left to carve into, go back to the previous visited cell, this is why its called the backtracker.
The algorithm is done when you have backtracked to the starting cell. I compare this to a hungry snake that
wants to eat all the cells in the entire maze. Steps:
 Pick a rondom starting cell, mark it as visited and put it on the stack.
 Peek (not pop) a cell from the stack and get its unvisited neighbours.
 Randomly select a unvisited neighbour, break down the wall and push it to the stack. Go to 2.
 If there are no unvisited neighbours, pop the cell of the stack and go to 2.
Prims algorithm Cells have 3 statusus: IN, OUT or FRONTIER. At the start all cells are
OUT and all walls are raised. This algorithm expands like a explosion around a single starting point,
adding cells to the maze one at the time using the 3 possible status markers. The maze is done when all
cells are IN. Steps:
 Pick a rondom starting cell and mark it as IN.
 Get all neigbouring cells with status OUT and mark them as FRONTIER.
 Pick a random frontier cell and break the wall between a random IN neigbour. Go to 2.
Binary tree algorithm The most simple algorithm i have seen. It just iterates all cells from left to right, top to bottom and randomly decides per cell: do i remove the wall north of me or west of me. Exceptions are the first row and first column. Its called the binary tree algorithm because the resulting maze will look like a binary tree.
Sidewinder algorithm Another algorithm that build the maze from top to bottom. It makes the
first row one long corridor and starts at the second row. It generates horizontal corridors of random lengths and
connects them vertically to the allready finished part of the maze by removing a wall. Steps:
 Make the first row one long corridor and move to the next row.
 Devide the current row in corridors of random lengths.
 Connect the corridors vertically.
 Repeat for next row if this is not the last row.
Ellers algorithm My favourite algorithm and hardest to implement. This algorithm builds the
maze row by row and does not produce a maze with a weird looking structure like binary tree or sidewinder.
I think its a verry cool algorithm. It puts all cells in sets, where cells in the same set have a path between
them. This way the algorithm can randomly connect cells with the one rule that cells in the same set cannot be
connected, as this would make a loop. Steps:
 Put each cell wich is not in a set in a new set.
 Make random horizontal connections in the row, merging sets when forming a connection.
 Carve vertically down from each set atleast once.
 Move to next row and Repeat from step 1.
Breadth first search The BFS algorithm is a algorithm to find the shortest
path in a graph, and can be used to solve a maze. It works by going through the graph one
layer at the time. This is why its called breadth first unlike depth first search. Steps:
 Start at the maze entrance and put it in the queue.
 Pop a cell of the queue and mark it as visited.
 If this cell is the maze exit we are done. If not go to step 4.
 Get all unvisited neighbours of the cell and put them in the queue. Go to step 2.
a look here. Enjoy!