Understanding Eller’s Algorithm
Explore Eller's algorithm to understand its unique approach to maze generation. Learn how it efficiently builds mazes by processing one row at a time, linking cells while managing cell sets, and combining strategies from Sidewinder and Kruskal’s algorithms to avoid biases and loops. This lesson guides you through creating connected, loop-free mazes with this clever technique.
We'll cover the following...
Background
So many algorithms! From the Binary Tree and Sidewinder to Kruskal’s and Prim’s and Growing Tree, we’ve learned a lot about the different methods of generating random mazes. If we’re counting Dijkstra’s, there are 11 in total.
There are only two more left to cover!
The first, called Eller’s algorithm, is a fast, efficient, and clever technique that seems born of the unlikely union of the Sidewinder algorithm and Kruskal’s.
Eller’s algorithm explained and illustrated
Marlin Eller invented Eller’s algorithm in 1982. It shares some remarkable similarities with the Sidewinder algorithm and yet manages to ...