Mazes for Programmers

Dead Ends

A dead end is defined as a cell that is linked to only a single neighbor. Fewer dead ends and a long path might suggest lengthy side roads that can take someone far astray.

The following figure shows how the number of dead ends per maze compared across algorithms.

Aldous-Broder and Wilson’s tend to produce mazes where around 30% of the cells are dead ends. True Prim’s produces about 50% more than that, and Hunt-and-Kill and Recursive Backtracker produce significantly fewer.