Eller's Algorithm Maze Generator

Eller's algorithm is a maze generation algorithm that efficiently produces perfect mazes (mazes with no loops and a single path between any two points) using a row-by-row approach. It produces mazes similar to Kruskal's algorithm, but it does so by generating just one row at a time, without the need for storing the entire maze in memory. That makes it useful for generating very large mazes on very limited systems and for procedural content generation.

A perfect maze is a maze in which there is exactly one path from any point in the maze to any other point. That means you can't end up going around in circles, but you will often encounter dead ends, forcing you to turn around and go back.

The maze maps generated here includes a default version without any start and finish positions, so you can decide those for yourself: there will be a solution from any point in the maze to any other point. If you want inspiration, you can enable a suggested start and finish position - and even see the solution between the two.

About Eller's Algorithm

Eller's Algorithm was introduced by David Eller.

The algorithm is notable for its efficient row-by-row approach to maze generation, making it ideal for infinite mazes or mazes generated in real-time. It is commonly cited in procedural content generation and maze-generation literature, but I have not been able to find primary sources detailing its original publication.

How Eller's Algorithm Works for Maze Generation

Eller’s algorithm processes one row at a time, maintaining and modifying sets of connected cells. It ensures connectivity while avoiding loops, and it efficiently extends the maze downward.

It can theoretically be used to generate infinite mazes, however in order to ensure that the generated maze is actually solvable, it is necessary to switch to the "final row" logic at some point to finish the maze.

Step 1: Initialize the First Row

• Assign each cell in the row a unique set ID.

Step 2: Join Some Adjacent Cells Horizontally

• Randomly merge adjacent cells by setting them to the same set ID. This ensures that there are horizontal passages.

Step 3: Create Vertical Connections to the Next Row

• For each set that appears in the row, at least one cell must connect downward (to ensure connectivity).
• Randomly pick one or more cells from each set to connect to the next row.

Step 4: Move to the Next Row

• Carry forward the vertical connections by assigning the same set ID to the corresponding cells below.
• Assign new set IDs to any unassigned cells.

Step 5: Repeat Steps 2–4 Until the Last Row is Reached

• Continue processing row by row.

Step 6: Process the Final Row

• Ensure all cells in the last row belong to the same set by merging any remaining separate sets.