Генератор на лабиринти с алгоритъм на Kruskal

Алгоритъмът на Крускал е алгоритъм с минимално обхващащо дърво, който може да бъде адаптиран за генериране на лабиринти. Той е особено ефективен за създаване на перфектни лабиринти. Алтернатива на алгоритъма на Крускал е алгоритъмът на Прим, който също е алгоритъм с минимално обхващащо дърво, но тъй като те генерират идентични лабиринти и този на Крускал работи по-бързо, не съм си правил труда да имплементирам алгоритъма на Прим.

Перфектен лабиринт е лабиринт, в който има точно един път от всяка точка в лабиринта до всяка друга точка. Това означава, че не можете да се въртите в кръг, но често ще срещате задънени улици, което ще ви принуди да се обърнете и да се върнете обратно.

Генерираните тук карти на лабиринта включват версия по подразбиране без начални и крайни позиции, така че можете да ги определите сами: ще има решение от всяка точка в лабиринта до всяка друга точка. Ако искате да получите вдъхновение, можете да активирате предложена начална и крайна позиция - и дори да видите решението между двете.

Относно алгоритъма на Крускал

Алгоритъмът на Крускал е създаден от Джоузеф Бернард Крускал-младши, американски математик, статистик и компютърен учен. Той описва алгоритъма за първи път през 1956 г. в своята статия „Върху най-късото обхващащо поддърво на граф и задачата на пътуващия търговец“.

Алгоритъмът е проектиран да намери минималното обхващащо дърво (MST) на граф, като гарантира, че всички върхове са свързани с минималното възможно общо тегло на ребрата, като същевременно се избягват цикли.

Как работи алгоритъмът на Крускал за генериране на лабиринти

Стъпка 1: Инициализиране

• Третирайте всяка клетка в лабиринта като отделен набор (уникален компонент).
• Избройте всички стени между съседни клетки като потенциални ръбове.

Стъпка 2: Сортиране на стените

• Разбъркайте или подредете стените на случаен принцип. Ако го имплементирате като истински алгоритъм на Крускал, сортирайте стените в случаен ред (тъй като генерирането на лабиринт не изисква тегла).

Стъпка 3: Обработка на стени

• Преминете през разместените стени.
• Ако двете клетки, разделени от стената, принадлежат към различни множества (т.е. все още не са свързани в лабиринта), премахнете стената и обединете множествата.
• Ако вече са в един и същи комплект, пропуснете стената (за да избегнете цикли).

Стъпка 4: Продължете до завършване

• Повторете този процес, докато всички клетки бъдат свързани, образувайки едно обхващащо дърво.
• В края всяка клетка е свързана с останалите без бримки или изолирани секции.

Тъй като алгоритъмът на Крускал разчита на сливане на множества, той може да бъде оптимизиран с помощта на алгоритъма Union-Find, който предоставя ефикасен начин за проследяване на свързани клетки по време на генериране на лабиринт. Можете да видите моята PHP имплементация на алгоритъма Union-Find тук: Връзка

Допълнително четене

Ако ви е харесала тази публикация, може да ви харесат и тези предложения:

• Генератор на лабиринт на алгоритъма на Уилсън
• Генератор на лабиринт за алгоритъм за отглеждане на дървета
• Генератор на лабиринт за лов и убиване