Відкрити головне меню

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

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

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

Формальний опис алгоритмуРедагувати

  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