Maze generation algorithm

The purpose of the maze generation algorithm can then be considered to be making a subgraph in which it is challenging to find a route between two particular nodes.

Loops, which can confound naive maze solvers, may be introduced by adding random edges to the result during the course of the algorithm.

Second, the computer traverses F using a chosen algorithm, such as a depth-first search, coloring the path red.

Frequently implemented with a stack, this approach is one of the simplest ways to generate a maze using a computer.

As given above this algorithm involves deep recursion which may cause stack overflow issues on some computer architectures.

As a solution, the same backtracking method can be implemented with an explicit stack, which is usually allowed to grow much bigger with no harm.

An efficient implementation using a disjoint-set data structure can perform each union and find operation on two sets in nearly constant amortized time (specifically,

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.

Wilson's algorithm,[1] on the other hand, generates an unbiased sample from the uniform distribution over all mazes, using loop-erased random walks.

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.

This procedure remains unbiased no matter which method we use to arbitrarily choose starting cells.

This method results in mazes with long straight walls crossing their space, making it easier to see which areas to avoid.

Most maze generation algorithms require maintaining relationships between cells within it, to ensure the result will be solvable.

To create a binary tree maze, for each cell flip a coin to decide whether to add a passage leading up or left.

Always pick the same direction for cells on the boundary, and the result will be a valid simply connected maze that looks like a binary tree, with the upper left corner its root.

A related form of flipping a coin for each cell is to create an image using a random mix of forward slash and backslash characters.

This doesn't generate a valid simply connected maze, but rather a selection of closed loops and unicursal passages.

[6] For a random starting pattern, these maze-generating cellular automata will evolve into complex mazes with well-defined walls outlining corridors.

[6] Since these cellular automaton rules are deterministic, each maze generated is uniquely determined by its random starting pattern.