Eller’s Algorithm
Eller’s algorithm was invented by Marlin Eller in 1982. It shares some remarkable similarities with Sidewinder (here), and yet manages to avoid the striking bias of that algorithm by incorporating some of the features of Kruskal’s (here) as well.
Like Sidewinder, it works by considering only a single row at a time, while building up sets (Kruskal-style) to keep track of which cells are reachable from which other cells. Let’s work through an example.
We’ll start at the top row (for convenience’s sake), and we’ll highlight the current row in yellow, to keep track of where we’re at.
The first thing we do is assign each cell in that ...
Get Mazes for Programmers now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
