Генератор лабіринтів алгоритму Еллера

Алгоритм Еллера — це алгоритм генерації лабіринтів, який ефективно створює ідеальні лабіринти (лабіринти без петель та з одним шляхом між будь-якими двома точками), використовуючи рядковий підхід. Він створює лабіринти, подібні до алгоритму Краскела, але робить це, генеруючи лише один рядок за раз, без необхідності зберігати весь лабіринт у пам'яті. Це робить його корисним для генерації дуже великих лабіринтів на дуже обмежених системах та для генерації процедурного контенту.

Ідеальний лабіринт - це лабіринт, в якому існує рівно один шлях з будь-якої точки лабіринту в будь-яку іншу точку. Це означає, що ви не можете ходити по колу, але часто будете стикатися з глухими кутами, що змусить вас розвернутися і повернутися назад.

Карти лабіринту, згенеровані тут, включають версію за замовчуванням без стартових і фінішних позицій, тому ви можете визначити їх самостійно: з будь-якої точки лабіринту в будь-яку іншу точку буде знайдено шлях. Якщо вам потрібне натхнення, ви можете ввімкнути запропоновані позиції старту і фінішу - і навіть побачити рішення між ними.

Про алгоритм Еллера

Алгоритм Еллера був запропонований Девідом Еллером.

Цей алгоритм відрізняється ефективним порядковим підходом до генерації лабіринтів, що робить його ідеальним для нескінченних лабіринтів або лабіринтів, що генеруються в режимі реального часу. Його часто згадують у літературі з процедурної генерації контенту та генерації лабіринтів, але мені не вдалося знайти першоджерела з детальним описом його оригінальної публікації.

Як працює алгоритм Еллера для генерації лабіринтів

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

Теоретично його можна використовувати для генерації нескінченних лабіринтів, проте, щоб переконатися, що згенерований лабіринт насправді розв'язний, необхідно в певний момент переключитися на логіку "останнього рядка", щоб завершити лабіринт.

Крок 1: Ініціалізація першого рядка

• Призначте кожній клітинці в рядку унікальний ідентифікатор набору.

Крок 2: Об'єднайте кілька суміжних комірок горизонтально

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

Крок 3: Створення вертикальних з'єднань з наступним рядом

• Для кожного набору, що з'являється в рядку, принаймні одна клітинка повинна бути з'єднана вниз (для забезпечення зв'язності).
• Випадковим чином виберіть одну або кілька клітинок з кожного набору, щоб з'єднати їх з наступним рядком.

Крок 4: Перехід до наступного рядка

• Перенесіть вертикальні зв'язки, призначивши той самий ідентифікатор набору відповідним клітинкам нижче.
• Призначте нові ідентифікатори наборів будь-яким непризначеним клітинкам.

Крок 5: Повторюйте кроки 2–4, доки не буде досягнуто останнього ряду

• Продовжуйте обробку рядок за рядком.

Крок 6: Обробка останнього ряду

• Переконайтеся, що всі клітинки в останньому рядку належать до одного набору, об'єднавши будь-які інші окремі набори.

Додаткова література

Якщо вам сподобався цей пост, вам також можуть сподобатися ці пропозиції:

• Алгоритм вирощування дерева Генератор лабіринтів
• Генератор лабіринтів алгоритму Вільсона
• Генератор лабіринтів полювання та вбивств