Генератор лабіринтів алгоритму Крускала
Опубліковано: 16 лютого 2025 р. о 18:00:54 UTC
Генератор лабіринтів за допомогою алгоритму Крускала для створення ідеального лабіринту. Цей алгоритм тяжіє до створення лабіринтів з коридорами середньої довжини і безліччю тупиків, а також досить прямим рішенням.Kruskal's Algorithm Maze Generator
Алгоритм Крускала — це алгоритм мінімального охоплення дерева, який може бути адаптований для генерації лабіринту. Він особливо ефективний для створення ідеальних лабіринтів. Альтернативою алгоритму Крускала є алгоритм Прима, який також є алгоритмом мінімального охоплюючого дерева, але оскільки вони генерують однакові лабіринти і Крускал працює швидше, я не став перейматися реалізацією Prim's.
Ідеальний лабіринт - це лабіринт, в якому існує рівно один шлях з будь-якої точки лабіринту в будь-яку іншу точку. Це означає, що ви не можете ходити по колу, але часто будете стикатися з глухими кутами, що змусить вас розвернутися і повернутися назад.
Карти лабіринту, згенеровані тут, включають версію за замовчуванням без стартових і фінішних позицій, тому ви можете визначити їх самостійно: з будь-якої точки лабіринту в будь-яку іншу точку буде знайдено шлях. Якщо вам потрібне натхнення, ви можете ввімкнути запропоновані позиції старту і фінішу - і навіть побачити рішення між ними.
Про алгоритм Крускала
Алгоритм Крускала був створений Джозефом Бернардом Крускалом-молодшим, американським математиком, статистиком і вченим-інформатиком. Вперше він описав алгоритм у 1956 році у своїй статті «Про найкоротше охоплююче піддерево графа та проблему комівояжера».
Алгоритм розроблений для знаходження мінімального охопленого дерева (MST) графа, гарантуючи, що всі вершини пов'язані з мінімально можливою загальною вагою ребер, уникаючи циклів.
Як працює алгоритм Крускала для генерації лабіринтів
Крок 1: Ініціалізація
- Розглядайте кожну клітинку в лабіринті як окремий набір (унікальний компонент).
- Перерахуйте всі стінки між сусідніми клітинками як потенційні ребра.
Крок 2: Сортуємо стіни
- Перемішайте або довільно впорядкуйте стіни. Якщо це реалізовано як істинний алгоритм Крускала, сортуйте стіни в довільному порядку (оскільки генерація лабіринту не вимагає ваг).
Крок 3: Обробіть стіни
- Ітеруйте крізь перемішані стіни.
- Якщо дві клітинки, розділені стіною, належать до різних наборів (тобто вони ще не з'єднані в лабіринті), видаліть стіну і об'єднайте множини.
- Якщо вони вже є в одному наборі, пропустіть стіну (щоб уникнути циклів).
Крок 4: Продовжуйте до завершення
- Повторюйте цей процес, доки всі клітини не з'єднаються, утворюючи єдине охоплююче дерево.
- В кінці кожна клітинка з'єднується з іншими без петель або ізольованих ділянок.
Оскільки алгоритм Крускала покладається на об'єднання множин, його можна оптимізувати за допомогою алгоритму Union-Find, який забезпечує ефективний спосіб відстеження з'єднаних комірок під час генерації лабіринту. Ви можете побачити мою реалізацію алгоритму Union-Find на PHP тут: Диз'єднана множина (алгоритм union-find) в PHP