HTML5 Maze generator and solver

Posted on 1 October 2012 in Techstuff

Introduction

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.

I did this a few years ago and wrote the program in csharp and used GDI+ to draw the mazes on the screen. I had never used HTML5 and the new canvas element so decided to port the old code to javascript to learn how to use it.

Algorithms

The most fun part is to compare the different algorithms to each other and the different approaches they take to solve the problem: how to generate a perfect maze. A perfect maze is a maze with no loops or isolated areas. Below a list of algorithms and a short description on how they work. Check out my javascript demo to see the algorithms in action!

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:

[1] Pick a rondom starting cell, mark it as visited and put it on the stack.
[2] Peek (not pop) a cell from the stack and get its unvisited neighbours.
[3] Randomly select a unvisited neighbour, break down the wall and push it to the stack. Go to 2.
[4] 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:

[1] Pick a rondom starting cell and mark it as IN.
[2] Get all neigbouring cells with status OUT and mark them as FRONTIER.
[3] 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:

[1] Make the first row one long corridor and move to the next row.
[2] Devide the current row in corridors of random lengths.
[3] Connect the corridors vertically.
[4] 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:

[1] Put each cell wich is not in a set in a new set.
[2] Make random horizontal connections in the row, merging sets when forming a connection.
[3] Carve vertically down from each set atleast once.
[4] 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:

[1] Start at the maze entrance and put it in the queue.
[2] Pop a cell of the queue and mark it as visited.
[3] If this cell is the maze exit we are done. If not go to step 4.
[4] Get all unvisited neighbours of the cell and put them in the queue. Go to step 2.

Javascript algorithm demos

1300+ lines of javascript/jQuery code make the algorithms come to life, animated step by step. Please take a look here. Enjoy!

maze thumb 1 maze thumb 2 maze thumb 3 maze thumb 4 maze thumb 5
Screenshots of mazes being generated and solved

Links