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

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

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

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

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

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

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

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

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

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

Крок 1: Ініціалізуйте перший рядок

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

Крок 2: З'єднайте деякі сусідні клітинки по горизонталі

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

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

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

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

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

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

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

Крок 6: Обробляємо завершальний ряд

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