Editing Maze generation algorithm (section)

=== Iterative randomized Prim's algorithm (without stack, without sets) ===
[[File:MAZE 30x20 Prim.ogv|thumb|upright=1.6|An animation of generating a 30 by 20 maze using Prim's algorithm]]
This algorithm is a randomized version of [[Prim's algorithm]].

# Start with a grid full of walls.
# Pick a cell, mark it as part of the maze. Add the walls of the cell to the wall list.
# While there are walls in the list:
## Pick a random wall from the list. If only one of the cells that the wall divides is visited, then:
### Make the wall a passage and mark the unvisited cell as part of the maze.
### Add the neighboring walls of the cell to the wall list.
## Remove the wall from the list.

Note that simply running classical Prim's on a graph with random edge weights would create mazes stylistically identical to Kruskal's, because they are both minimal spanning tree algorithms.  Instead, this algorithm introduces stylistic variation because the edges closer to the starting point have a lower effective weight.

==== Modified version ====
Although the classical Prim's algorithm keeps a list of edges, for maze generation we could instead maintain a list of adjacent cells. If the randomly chosen cell has multiple edges that connect it to the existing maze, select one of these edges at random. This will tend to branch slightly more than the edge-based version above.

==== Simplified version ====
The algorithm can be simplified even further by randomly selecting cells that neighbour already-visited cells, rather than keeping track of the weights of all cells or edges.

It will usually be relatively easy to find the way to the starting cell, but hard to find the way anywhere else.