Module maze_generator::ellers_algorithm

source · [−]
Expand description

Ellers algorithm implementation

Fast algorithm for generating arbitrarily large mazes in linear time.

Algorithm rundown

  1. Initialize the fields of the first row to each exist in its own set.
  2. Randomly join fields but only if they are not already in the same set. When joining, merge the two sets (which indicates that the cells are now connected)
  3. For each set, randomly create vertical connections downward to the next row. Each set must have at least one vertical connection created in this way. The cells in the next row share the same set because they are connected.
  4. Flesh out the next row by creating sets for the fields not already vertically connected.
  5. Repeat from 2. until the last row is reached
  6. For the last row, join all adjacent cells which do not yet share a set.

Explanation by example

If the above explanation seems a bit complex, here’s an example for a 4x5 maze:

  1. First, we initialize each field in the row to be in its own set (represented by numbers):

    ·-·-·-·-·-·
|1|2|3|4|5|
·-·-·-·-·-·

  2. Next, we randomly join adjacent fields that belong to different sets. The fields so joined also are merged into the same set:

    ·-·-·-·-·-·
|1 1 1|4 4|
·-·-·-·-·-·

  3. Now we randomly determine the vertical connections, at least one per set. The fields in the next row that we connected to must be assigned to the set of the cell above them:

    ·-·-·-·-·-·
|1 1 1|4 4|
· ·-· ·-· ·
|1| |1| |4|
·-·-·-·-·-·

  4. Next, we flesh out the next row, assigning each remaining field to its own set:

    ·-·-·-·-·-·
|1 1 1|4 4|
· ·-· ·-· ·
|1|6|1|7|4|
·-·-·-·-·-·

  5. Now, we just repeat the previous steps on our new row. We randomly connect adjacent sets that do not share a set. Something like this:

    ·-·-·-·-·-·
|1 1 1|4 4|
· ·-· ·-· ·
|1 1|1 1|4|
·-·-·-·-·-·

  6. Add at east one vertical connection to each set:

    ·-·-·-·-·-·
|1 1 1|4 4|
· ·-· ·-· ·
|1 1|1 1|4|
·-· ·-·-· ·
| |1| | |4|
·-·-·-·-·-·

  7. Flesh out the next row (I’m reusing extinct set numbers for simplicity):

    ·-·-·-·-·-·
|1 1 1|4 4|
· ·-· ·-· ·
|1 1|1 1|4|
·-· ·-·-· ·
|8|1|9|2|4|
·-·-·-·-·-·

  8. Final iteration for the last row now. First, randomly join adjacent cells:

    ·-·-·-·-·-·
|1 1 1|4 4|
· ·-· ·-· ·
|1 1|1 1|4|
·-· ·-·-· ·
|8|1|4 4 4|
·-·-·-·-·-·

  9. Add vertical connections (at least one per set):

    ·-·-·-·-·-·
|1 1 1|4 4|
· ·-· ·-· ·
|1 1|1 1|4|
·-· ·-·-· ·
|8|1|4 4 4|
· · ·-· ·-·
|8|1| |4| |
·-·-·-·-·-·

  10. Flesh out the next row:

    ·-·-·-·-·-·
|1 1 1|4 4|
· ·-· ·-· ·
|1 1|1 1|4|
·-· ·-·-· ·
|8|1|4 4 4|
· · ·-· ·-·
|8|1|3|4|5|
·-·-·-·-·-·

  11. And now the final step. This time, we must connect ALL adjacent (but disjoint) fields. In this case, that means all of them:

    ·-·-·-·-·-·
|     |   |
· ·-· ·-· ·
|   |   | |
·-· ·-·-· ·
| | |     |
· · ·-· ·-·
|         |
·-·-·-·-·-·

Explanation and example credits to Jamis Buck’s Buckblog

Structs

EllersGenerator

Generator implementation which uses Ellers algorithm.