Генератор на лабиринти с алгоритъм на Kruskal
Публикувано: 16 февруари 2025 г. в 17:56:28 ч. UTC
Генератор на лабиринти, използващ алгоритъма на Kruskal за създаване на перфектен лабиринт. Този алгоритъм има тенденция да създава лабиринти със средно дълги коридори и много задънени улици, както и сравнително право решение.Kruskal's Algorithm Maze Generator
Алгоритъмът на Kruskal е алгоритъм за минимално обхващащо дърво, който може да бъде адаптиран за генериране на лабиринти. Той е особено ефективен за създаване на перфектни лабиринти. Алтернатива на алгоритъма на Kruskal е алгоритъмът на Prim, който също е алгоритъм с минимално обхващащо дърво, но тъй като те генерират идентични лабиринти и Kruskal работи по-бързо, не съм си правил труда да внедря Prim.
Перфектен лабиринт е лабиринт, в който има точно един път от всяка точка в лабиринта до всяка друга точка. Това означава, че не можете да се въртите в кръг, но често ще срещате задънени улици, което ще ви принуди да се обърнете и да се върнете обратно.
Генерираните тук карти на лабиринта включват версия по подразбиране без начални и крайни позиции, така че можете да ги определите сами: ще има решение от всяка точка в лабиринта до всяка друга точка. Ако искате да получите вдъхновение, можете да активирате предложена начална и крайна позиция - и дори да видите решението между двете.
Относно алгоритъма на Крускал
Алгоритъмът на Крускал е създаден от Джоузеф Бърнард Крускал, младши, американски математик, статистик и компютърен учен. Той описва за първи път алгоритъма през 1956 г. в статията си „За най-късото покриващо поддърво на графика и проблема с пътуващия търговец“.
Алгоритъмът е проектиран да намира минималното обхващащо дърво (MST) на граф, като гарантира, че всички върхове са свързани с минималното възможно общо тегло на ръба, като същевременно се избягват цикли.
Как работи алгоритъмът на Kruskal за генериране на лабиринт
Стъпка 1: Инициализиране
- Третирайте всяка клетка в лабиринта като отделен набор (уникален компонент).
- Избройте всички стени между съседни клетки като потенциални ръбове.
Стъпка 2: Сортирайте стените
- Разбъркайте или произволно подредете стените. Ако го прилагате като истински алгоритъм на Kruskal, сортирайте стените в произволен ред (тъй като генерирането на лабиринт не изисква тегла).
Стъпка 3: Обработка на стени
- Преминете през разбърканите стени.
- Ако двете клетки, разделени от стената, принадлежат към различни комплекти (т.е. все още не са свързани в лабиринта), премахнете стената и слейте комплектите.
- Ако вече са в един комплект, пропуснете стената (за да избегнете цикли).
Стъпка 4: Продължете до завършване
- Повторете този процес, докато всички клетки бъдат свързани, образувайки едно обхващащо дърво.
- В края всяка клетка е свързана с останалите без примки или изолирани секции.
Тъй като алгоритъмът на Kruskal разчита на обединяване на набори, той може да бъде оптимизиран с помощта на алгоритъма Union-Find, който осигурява ефективен начин за проследяване на свързани клетки по време на генериране на лабиринт. Можете да видите моята PHP реализация на алгоритъма Union-Find тук: Disjoint Set (алгоритъм за намиране на съюз) в PHP