Experimenting with some maze generation and search algorithms. The small implementation is written in the browser in Javascript with visualisation on an HTML5 canvas.

Maze size:

Generator:


Solver:


Show route
Show explored area
Show maze walls


In this implementation, the “start” is the top left corner of the maze, and the “goal” the bottom right corner. The colour in the heatmap varies by the number of steps from the start of the maze.

All generators start with an empty maze, and initally consider every square or cell closed off (surrounded by 4 walls). Walls are chosen at random to open up spaces and join all the cells together, forming pathways.

In the randomised DFS, a random unvisited neighbouring cell is chosen at each recursive search step, and a wall “opened” if necessary. Both the Prim & Kruskal-based generators are similar to the process of building a minimum spanning tree in a weighted graph. The Kruskal implementation is a bit slow here on larger mazes due to a not very efficient implementation of the disjoint sets data structure (used to track which areas of the maze are connected). For more about the algorithms, see the relevant sections in the maze generation algorithm Wikipedia article.

In both solvers, when given a choice of neighbouring cells with same priority, the cell is chosen at random (e.g. over following a fixed order of directions). So running the solver again on the same maze will mean the explored area may be different.

It is interesting to see how much of the maze is explored by the different algorithms. For example, a breadth-first search of the Prim-based generator explores much of the maze. The inital point chosen to generate by the Prim-inspired generator is the mid-point of the maze, yielding the radial pattern in the heatmap when combined with the BFS search.