Генератор лабіринтів алгоритму Крускала

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

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

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

Про алгоритм Крускала

Алгоритм Крускала був створений Джозефом Бернардом Крускалом-молодшим, американським математиком, статистиком та вченим-інформатиком. Він вперше описав алгоритм у 1956 році у своїй статті «Про найкоротше охоплююче піддерево графа та задачу комівояжера».

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

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

Крок 1: Ініціалізація

• Розглядайте кожну клітинку в лабіринті як окремий набір (унікальний компонент).
• Перелічіть усі стіни між сусідніми клітинками як потенційні ребра.

Крок 2: Сортування стін

• Перетасуйте або випадковим чином упорядкуйте стіни. Якщо реалізовано як справжній алгоритм Краскела, відсортуйте стіни у випадковому порядку (оскільки генерація лабіринту не потребує ваг).

Крок 3: Обробка стін

• Переберіть перетасовані стіни.
• Якщо дві клітини, розділені стіною, належать до різних множин (тобто вони ще не з'єднані в лабіринті), видаліть стіну та об'єднайте множини.
• Якщо вони вже знаходяться в одному наборі, пропустіть стіну (щоб уникнути циклів).

Крок 4: Продовжуйте до завершення

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

Оскільки алгоритм Крускала базується на об'єднанні множин, його можна оптимізувати за допомогою алгоритму Union-Find, який забезпечує ефективний спосіб відстеження пов'язаних комірок під час генерації лабіринту. Ви можете побачити мою PHP-реалізацію алгоритму Union-Find тут: Посилання

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

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

• Генератор лабіринтів алгоритму Вільсона
• Генератор лабіринтів полювання та вбивств
• Генератор рекурсивних лабіринтів Backtracker