Maze Algorithms

Eller

Main feature of Eller algorithm is the linear time complexity. It can generate really complex mazes in a short time comparing to the different algorithms. The algorithm itself can be implemented in two ways. First one where whole grid is initialized with walls placed and they are removed in the further iterations. Second one where grid is empty and the walls are placed in the further iterations. Given document will cover the first implementation scenario starting with all walls placed.

The whole process launches from the first maze's row. Each of the nodes are assigned to the unique group. In the given example each of the groups will be represented as separate color.

Next step involves iterating over all cells in the current row and making eastern passages. The passages are created basing on random chance. Starting from the first cell the random 50% chance is checked. If it is fulfilled the wall between first cell and the eastern one is destroyed and the eastern cell is assigned to the first cell's group.

The same situation appears for another cell, the random chance is met so the wall between second and third cells is removed. The third cell is also assigned to the first group.

During the check for third cell the random chance wasn't fulfilled. The wall between third and foruth cell will persist and the algorithm will move to the next cell leaving the fourth cell in its current group.

Then the process moves forward with the same assumptions until it reaches the final cell in the current row. The node won't have any neighbour on the east so the processing for the current row is completed.

When the horizontal passages are created there is time to make the vertical ones. In order to achieve that we need to iterate over all of the groups and build random number of passages. The minimum amount of them for each group equals 1 and the maximum is the count of the nodes assigned to the given group from the most recent row. In the given example the fourth group has only 1 southern passage so it's the reason why one of the cells in the second row is gray.

After finishing the southern passages build process the algorithm repeats the steps with assigning each of the nodes from the second row to the unique groups. Nodes being already assigned to any group aren't modified. In the current row there was only one node without any group assigned so the new one was created and assigned to it.

As the next step the whole process of building the eastern walls repeats with additional condition. If the two neighbouring cells are assigned to the same group then the wall between them persists. In the case where they are assigned to the different groups the random chance is checked and when fulfilled the wall is destroyed, otherwise the wall is left.

After making the eastern passages, again the southern ones are created.

Then the whole process with making the eastern and southern passages repeats until it reaches the last row. For this one we need to update the condition for making the eastern passages. If the cells are in the same group the wall is left, otherwise the passage must be created. We no longer check the random chance for that. Also we skip the step with making the southern passages as there are no more nodes on the south.

Finishing last iteration of making eastern passages results with complete maze.