back

## what was the site written in?

node.js, socket.io, and p5.js.

## how are mazes generated?

Mazes are generated using Prim's Algorithm. Prim’s Algorithm is a minimum spanning tree algorithm. An MST of a graph is the subset of edges (with the smallest total weight) where you can reach every node in the graph. For example, in the following diagram, the MST is highlighted in bold. A maze can be thought of as a graph, although not weighted since the distance from each cell to its adjacent cells is always 1. In graph theory terms, you can think of the cells as nodes and the connections from each cell to its neighboring cells as edges. Prim’s Algorithm creates a maze that ensures there’s always a path between the starting and ending point because that is the very definition of an MST. When applied to maze generation, Prim’s Algorithm is still very similar to the original graph version, but instead of continuously adding the closest node to the tree, it just adds a random one, since a maze graph is unweighted. Below is the pseudo-code for the standard graph version and the maze version.

Graph version:
```Choose a random node from the input graph
Initialize the MST (starts with the random node)

While not all of the vertices are in the MST:
Get the last node entered into the set
Retrieve the edges to that node and determine the shortest edge
Add that edge and the node connected to by that edge to the MST
```
Maze version:
```Select a random cell from that maze and mark it as visited
Create a list of walls
Add the walls from the initial cell to the list of walls

While the list of walls isn't empty:
Select a random wall from the list:
Calculate the two cells the wall divides

If one of the cells isn't visited:
Delete the wall from the grid
Mark the unvisited cell as visited
Add the walls of the cell to the list of walls

Remove the random wall from the list
```