Maze Notepad is a Progressive Web App that lets users quickly and easily build and share grid-based mazes.
Maze Gallery is a website for users to browse Maze Notepad mazes.
For the maze generation algorithm, I wanted to ensure that the following criteria are met:
I decided to represent the maze as a graph, where (possible) intersections are represented by nodes and paths connecting them are represented by edges. I created a “base maze” that contains all physically possible paths, with each path having a random weight.
To generate a maze, I applied Kruskal's algorithm using a disjoint set ADT. The resulting maze is a tree so it will not contain any cycles, ensuring that the path between any two nodes is unique. Assuming that the maze is contiguous, there will be an edge between any two nodes.
Additionally, the random weights in the “base maze” determine which of its paths are present in the generated maze, randomizing its pattern. Paths can also be given low weights to prioritize them in the maze generation algorithm, allowing for users to overwrite existing paths.