Алгоритм Еллера генерації лабіринтів

Алгоритм Еллера — це математичний генератор, що дозволяє створювати лабіринти, у яких між кожними двома точками існує єдиний шлях, тобто лабіринти не містять циклів.

У порівнянні з іншими генераторами, цей алгоритм є одним із найшвидших та потребує незначну кількість пам'яті — пропорційну довжині рядка лабіринту.

Потрібно зберігати в пам'яті лише останній створений рядок — це дозволяє генерувати лабіринти з необмеженою кількістю рядків.

Як відбувається генерація

Алгоритм являє собою цикл додавання нових рядків. Рядок містить одну і ту саму кількість клітинок, яка довільно задається на початку. Клітинки належать до множин, що слугують для контролю можливості проходу між клітинками. На момент генерації поточного рядка клітини однієї множини з'єднані між собою, водночас клітини з різних множин знаходяться в ізольованих між собою частинах лабіринту. У кожної клітинки може бути або не бути права та нижня стінка. Загалом, стінки генеруються випадковим чином, але при дотриманні певних правил, які гарантують відсутність циклів у лабіринті.

Формальний опис алгоритму

1. Створити перший рядок. Жодна клітинка не належить жодній множині
2. Присвоїти кожній з клітинок, що не мають множини, свою унікальну множину
3. Створити праві стінки, рухаючись зліва направо:
   1. Випадково вирішити, чи додавати стінку:
      1. Якщо поточна клітинка та клітинка справа належать одній множині, додати стінку (для запобігання зацикленням)
      2. Якщо вирішено не додавати стінку, об'єднати множини поточної та наступної клітинки
4. Створити стінки знизу, рухаючись зліва направо:
   1. Випадково вирішити, чи додавати стінку знизу. При додаванні переконатися, що кожна множина має хоча б одну клітинку без нижньої стінки — це гарантуватиме відсутність ізольованих областей
5. Вирішити, чи додавати рядки після поточного
   1. Якщо вирішено додати рядок, то:
      1. Вивести поточний рядок
      2. Видалити всі праві стінки
      3. Видалити клітинки з нижніми стінками з їх множин
      4. Видалити всі нижні стінки
      5. Продовжити з кроку 2
   2. Якщо вирішено закінчити лабіринт, то:
      1. Додати нижню стінку до кожної клітинки
      2. Рухаючись зліва направо:
         1. Якщо поточна клітинка та клітинка справа належать до різних множин, то:
            1. Видалити праву стінку
            2. Об'єднати множини цих клітинок

Приклад генерації

Проілюструємо процес створення лабіринту покроково. Для початку визначимося з довжиною рядка — нехай вона дорівнюватиме 6. (Оскільки лабіринт має бути оточений стінками з усіх боків, перший рядок зробимо з верхніми, останній — з нижніми, усі перші клітинки — з лівими, а останні в кожному рядку — з правими стінками).

1. Створимо перший рядок.

       __ ___ __ ___ __ ___
      |                       |

2. Присвоїмо всім клітинкам унікальну множину

       __ ___ __ ___ __ ___
      | 1   2   3   4   5   6 |

3. Рухаючись зліва направо, випадковим чином вирішимо, чи додавати стінки між клітинками(Оскільки на даному кроці всі клітинки належать до різних множин, наш вибір ніщо не обмежує)

       __ ___ __ ___ __ ___
      |(1 | 2)  3   4   5   6 | - додаємо праву стінку після першої клітинки
       __ ___ __ ___ __ ___
      | 1 |(2   3)  4   5   6 | - не додаємо стінку після другої
       __ ___ __ ___ __ ___
      | 1 | 2   2   4   5   6 | - об'єднуємо множини, до яких належать 2 та 3 клітинки
       __ ___ __ ___ __ ___
      | 1 | 2  (2   4)  5   6 | 
       __ ___ __ ___ __ ___
      | 1 | 2   2   2   5   6 |
       __ ___ __ ___ __ ___
      | 1 | 2   2  (2 | 5)  6 |
       __ ___ __ ___ __ ___
      | 1 | 2   2   2 |(5 | 6)|
       __ ___ __ ___ __ ___
      | 1 | 2   2   2 | 5 | 6 | 

4. Додамо нижні стінки

       __ ___ __ ___ __ ___
      |(1)| 2   2   2 | 5 | 6 | - не додаємо стінку, це - остання клітинка у множині з індексом 1, що не має нижньої стінки.
       __ ___ __ ___ __ ___
      | 1 |_2_  2   2 | 5 | 6 | 
       __ ___ __ ___ __ ___
      | 1 |_2_  2  _2_| 5 | 6 |

5. Вітаю! Ми отримали перший завершений рядок нашого лабіринту. Додамо наступний. Для цього виведемо поточний іще раз:

       __ ___ __ ___ __ ___
      | 1 |_2_  2  _2_| 5 | 6 |        
      | 1 |_2_  2  _2_| 5 | 6 |

5. 1. 1. Видалимо всі праві стінки

       __ ___ __ ___ __ ___
      | 1 |_2_  2  _2_| 5 | 6 |        
      | 1  _2_  2  _2_  5   6 |

5. 1. 2. Усі клітинки, що містять нижні стінки, видалимо з їх множин

       __ ___ __ ___ __ ___
      | 1 |_2_  2  _2_| 5 | 6 |        
      | 1  _ _  2  _ _  5   6 |

5. 1. 3. Видалимо нижні стінки

       __ ___ __ ___ __ ___
      | 1 |_2_  2  _2_| 5 | 6 |        
      | 1       2       5   6 |

Повернемося до пункту 2. Присвоїмо клітинкам, що не належать до множин, унікальні множини

       __ ___ __ ___ __ ___
      | 1 |_2_  2  _2_| 5 | 6 |        
      | 1   3   2   4   5   6 |

3. Створимо праві стінки

       __ ___ __ ___ __ ___
      | 1 |_2_  2  _2_| 5 | 6 |        
      | 1   1 | 2   2 | 5   5 |

4. Створимо нижні стінки

       __ ___ __ ___ __ ___
      | 1 |_2_  2  _2_| 5 | 6 |        
      | 1  _1_|_2_  2 | 5   5 |

5. 1. 1. Продублюємо останній рядок

       __ ___ __ ___ __ ___
      | 1 |_2_  2  _2_| 5 | 6 |        
      | 1  _1_|_2_  2 | 5   5 |
      | 1  _1_|_2_  2 | 5   5 |

5. 1. 2. Витремо праві стінки

       __ ___ __ ___ __ ___
      | 1 |_2_  2  _2_| 5 | 6 |        
      | 1  _1_|_2_  2 | 5   5 |
      | 1  _1_ _2_  2   5   5 |

5. 1. 3. Видалимо клітинки з нижніми стінками

       __ ___ __ ___ __ ___
      | 1 |_2_  2  _2_| 5 | 6 |        
      | 1  _1_|_2_  2 | 5   5 |
      | 1  _ _ _ _  2   5   5 |

5. 1. 4. Видалимо нижні стінки

       __ ___ __ ___ __ ___
      | 1 |_2_  2  _2_| 5 | 6 |        
      | 1  _1_|_2_  2 | 5   5 |
      | 1           2   5   5 |

Повернемося до пункту 2. Присвоїмо порожні клітинки множинам

       __ ___ __ ___ __ ___
      | 1 |_2_  2  _2_| 5 | 6 |        
      | 1  _1_|_2_  2 | 5   5 |
      | 1   3   4   2   5   5 |

3. Створимо праві стінки

       __ ___ __ ___ __ ___
      | 1 |_2_  2  _2_| 5 | 6 |        
      | 1  _1_|_2_  2 | 5   5 |
      | 1   1 | 4   4   5   5 |

       __ ___ __ ___ __ ___
      | 1 |_2_  2  _2_| 5 | 6 |        
      | 1  _1_|_2_  2 | 5   5 |
      | 1   1 | 4  (4   5)  5 |

Зверніть увагу: ми об'єднуємо множини клітинок, тобто остання клітинка також стане належати до множини 4 після даного кроку.

       __ ___ __ ___ __ ___
      | 1 |_2_  2  _2_| 5 | 6 |        
      | 1  _1_|_2_  2 | 5   5 |
      | 1   1 | 4   4   4   4 |

Тут обов'язково поставити стінку після 5 клітинки — наступна з тієї самої множини

       __ ___ __ ___ __ ___
      | 1 |_2_  2  _2_| 5 | 6 |        
      | 1  _1_|_2_  2 | 5   5 |
      | 1   1 | 4   4  (4 | 4)|

4. Додамо нижні стінки

       __ ___ __ ___ __ ___
      | 1 |_2_  2  _2_| 5 | 6 |        
      | 1  _1_|_2_  2 | 5   5 |
      | 1  _1_| 4  _4_ _4_| 4 |

5. Більше не додаватимемо рядків

5. 2. 1.

       __ ___ __ ___ __ ___
      | 1 |_2_  2  _2_| 5 | 6 |        
      | 1  _1_|_2_  2 | 5   5 |
      |_1_ _1_|_4_ _4_ _4_|_4_|

5. 2. 2. Праву стінку після 2 клітинки потрібно видалити та об'єднати множини 2 та 3 клітинок(після завершення проходження по рядку усі клітинки мають належати одній множині).

       __ ___ __ ___ __ ___
      | 1 |_2_  2  _2_| 5 | 6 |        
      | 1  _1_|_2_  2 | 5   5 |
      |_1_ _1_ _1_ _1_ _1_|_1_|

І от, наш лабіринт нарешті завершено. Вхід та вихід можна зробити з будь-якої зовнішньої стінки лабіринту.

       __ ___ __ ___ __ ___
          |_ _     _ _|   |   |        
      |    _ _|_ _    |       |
      |_ _ _ _ _ _ _ _ _ _|_ _

Приклад згенерованого лабіринту

  _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
   | |_ _ _ _  | | | | |  _| | |       | |_  |_ _  | |_  | | | | | |_  |_ _  |   |
 | | | |  _ _    |_  |  _| | | |_| |_|_ _|_  |_  |    _ _  |  _ _|_          | | |
 | |   |_| | | |_| | | | |  _ _ _|  _|_  | |  _|_  |  _| |  _ _ _ _| |_| |_|_ _|_|
 | |_| |   |      _| |_ _  |_  | |       | | | | |_|_  |  _| |   | | | |_|   | | |
 | | |_ _| |_|_|   | |  _  | |   |_|_| |_|_  | | | | |_|     |_| | |   | |_| | | |
 |_  |_   _ _|   | | |_ _|_ _  |_ _   _| |_  |_  | | |_  | |_ _| | | | |     |  _|
 |        _| | |_|_   _   _| |_|_  |   | | |   | | |_   _|_|  _| |_ _| | |_| | | |
 |_|_| |_|   | | | |_| |_|_    |_    |  _|_  | |_     _|   |     |  _|     |  _ _|
 |  _   _| |_|_  | | | | | |_| |   | | | |_ _| | |_|_  | | | |_|    _|_| |_|_| | |
 |_ _|  _   _  | | |   | |_  | |_| |_| |_ _  | |    _ _| | |   | |    _   _| |  _|
 |_   _|_ _| |_ _  | |_   _| |    _ _|_  |_  | |_|_  | |_|  _|_|_|_|   |_  |_  | |
 | |_ _| | | | |_   _  |  _| |_|  _|_  |_ _ _ _| | |    _|_|  _|_  |_|_ _| |  _ _|
 |    _| |  _| |    _| |_| |_  |_   _ _|  _| |  _|   |_   _ _|  _ _| | | | | |_  |
 | |  _   _| | | |_|_ _|  _|_  |_ _     _| | | | |_|_| |_ _  | | | |_ _ _  | | | |
 |_| | |  _|   |  _| | | | | |     | |_  | |_  |_  |  _ _| | |  _| | |  _| | | | |
 |   | |_| |_| | | | |_   _| |_| |     |_   _ _ _|       | | | |    _| |  _ _|   |
 | |_|_  |_   _| | |_  |_   _ _ _| |_|_| |_   _| | | | |_ _|  _| |  _|_  | |   | |
 |     | | |_  |_  | | | |   |  _|_ _| | |_  | |  _| |   |_  | |_| | |_  | | |_|_|
 | | | |_ _  | |  _|  _  |_|_| | | |  _|_  | |_   _| |_| | | | |   |       | | | |
 |_|_|_ _ _ _ _ _ _ _ _|_ _ _ _ _ _ _ _ _ _ _ _ _ _|_ _|_ _ _ _ _|_ _|_|_|_ _ _ _ 

Посилання

http://www.neocomputer.org/projects/eller.html [Архівовано 3 жовтня 2013 у Wayback Machine.]