Mazes for Programmers

Appendix 2Comparison of Maze Algorithms

It’s one thing to stare at a maze and try to decide whether the aesthetics of it work for you or not. It’s much harder to look at the implementation of an algorithm and compare it quantitatively with other algorithms. How likely is the algorithm to generate dead ends? How does its average longest path compare with that of other algorithms? How can we even know these things?

For this, we turn to statistics. It’s really pretty straightforward to do: you run each algorithm a set number of times, on a grid of fixed size; pick out the numbers you care about; and analyze them. It’s probably not going to win you any PhDs, and the numbers by themselves certainly won’t tell you the whole story, but we can still ...