Overview

Prim's algorithm can be used to generate random mazes. We aim to have a collection of tiles marked either 'clear' (light) or 'wall' (dark) such that there is a path from every clear cell to any other without crossing a wall (and that long enough paths are not immediately clear to a viewer). The algorithm starts with a grid of wall tiles. We pick a cell in the top left corner to be the starting point and set it to clear. The wall cells at a distance of 2 from the clear cell are stored in a 'frontier' array. One frontier cell is picked randomly, removed from the array and set to be clear. A random clear cell at distance 2 from the frontier is picked as a target. The tile between the newly cleared frontier and the target is set to clear, thereby connecting the new tile with the maze. We add the wall cells at distance 2 from the frontier cell into the array and repeat the algorithm until the frontier array is empty.

After the maze has been generated, we use the Easystar.js library to find a path from the start point to the lower right corner. The library uses A* and the resulting path is highlighted in the end.