block by mbostock 1ef3b1fb9eb35ca8ffff

Randomized Depth-First

Full Screen

This maze generation algorithm uses randomized depth-first traversal. Starting in the bottom-left corner, the algorithm keeps an array of the possible directions the maze could be extended (shown in pink). At each step, the maze is extended in a random direction from the previous cell, as long as doing so does not reconnect with another part of the maze.

Compare this algorithm to random traversal, Prim’s algorithm on a randomly-weighted graph, and Wilson’s algorithm for a uniform spanning tree. The global structure of the maze can be more easily seen by flooding it with color.

index.html