Editing Maze generation algorithm (section)

=== Wilson's algorithm ===
{{Main|Loop-erased random walk}}

[[File:WilsonMazeGen.gif|thumb|right|Maze generation animation using Wilson's algorithm (gray represents an ongoing random walk). Once built the maze is solved using depth first search.]]
All the above algorithms have biases of various sorts: depth-first search is biased toward long corridors, while Kruskal's/Prim's algorithms are biased toward many short dead ends. Wilson's algorithm,<ref>{{cite conference
| title = Generating random spanning trees more quickly than the cover time
| first = David Bruce
| last = Wilson
| date = May 22–24, 1996
| conference = Symposium on Theory of Computing
| book-title = Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing
| publisher = ACM
| location = Philadelphia
| pages = 296–303
| isbn = 0-89791-785-5
| doi = 10.1145/237814.237880
|citeseerx = 10.1.1.47.8598}}</ref> on the other hand, generates an ''unbiased'' sample from the [[discrete uniform distribution|uniform distribution]] over all mazes, using [[loop-erased random walk]]s.

We begin the algorithm by initializing the maze with one cell chosen arbitrarily. Then we start at a new cell chosen arbitrarily, and perform a random walk until we reach a cell already in the maze—however, if at any point the random walk reaches its own path, forming a loop, we erase the loop from the path before proceeding. When the path reaches the maze, we add it to the maze. Then we perform another loop-erased random walk from another arbitrary starting cell, repeating until all cells have been filled.

This procedure remains unbiased no matter which method we use to arbitrarily choose starting cells. So we could always choose the first unfilled cell in (say) left-to-right, top-to-bottom order for simplicity.