Крускалов алгоритамски генератор на лавиринт
Објавено: 5 март 2025, во 19:50:51 UTC
Генератор на лавиринт користејќи го Крускаловиот алгоритам за да создаде совршен лавиринт. Овој алгоритам има тенденција да создава лавиринти со коридори со средна должина и многу мртви краеви, како и прилично директно решение.Kruskal's Algorithm Maze Generator
Крускаловиот алгоритам е алгоритам за минимално опфатено дрво што може да се прилагоди за генерирање на лавиринт. Тој е особено ефикасен за создавање совршени лавиринти. Алтернатива на алгоритмот на Крускал е Примовиот алгоритам, кој исто така е алгоритам со минимално опфатено дрво, но бидејќи тие генерираат идентични лавиринти и Крускаловите работи побрзо, не се мачев да го имплементирам Прим.
Совршен лавиринт е лавиринт во кој има точно една патека од која било точка во лавиринтот до која било друга точка. Тоа значи дека не можете да завршите да одите наоколу во кругови, но често ќе наидете на ќорсокак, што ќе ве принуди да се свртите и да се вратите назад.
Мапите на лавиринтот генерирани овде вклучуваат стандардна верзија без никакви позиции за почеток и крај, така што можете сами да ги решите тие: ќе има решение од која било точка во лавиринтот до која било друга точка. Ако сакате инспирација, можете да овозможите предложена почетна и завршна позиција - па дури и да го видите решението помеѓу двете.
За Крускаловиот алгоритам
Алгоритмот на Крускал е создаден од Џозеф Бернард Крускал, Џуниор, американски математичар, статистичар и компјутерски научник. Тој за прв пат го опиша алгоритмот во 1956 година во својот труд „За најкраткото опфатено поддрво на графикот и проблемот со патувачкиот продавач“.
Алгоритмот е дизајниран да го пронајде минималното опфатено стебло (MST) на графикот, осигурувајќи дека сите темиња се поврзани со минималната можна вкупна тежина на рабовите додека се избегнуваат циклуси.
Како функционира алгоритмот на Крускал за генерација на лавиринт
Чекор 1: Иницијализирајте
- Третирајте ја секоја клетка во лавиринтот како посебен сет (уникатна компонента).
- Наведете ги сите ѕидови помеѓу соседните ќелии како потенцијални рабови.
Чекор 2: Сортирање ѕидови
- Измешајте ги или по случаен избор нарачајте ги ѕидовите. Ако го имплементирате како вистински Крускалов алгоритам, подредете ги ѕидовите по случаен редослед (бидејќи за создавањето на лавиринтот не се потребни тежини).
Чекор 3: Обработка на ѕидови
- Повторете низ измешаните ѕидови.
- Ако двете ќелии поделени со ѕидот припаѓаат на различни групи (т.е. сè уште не се поврзани во лавиринтот), отстранете го ѕидот и спојте ги множествата.
- Ако веќе се во истиот сет, прескокнете го ѕидот (за да избегнете циклуси).
Чекор 4: Продолжете до завршување
- Повторете го овој процес додека не се поврзат сите ќелии, формирајќи едно дрво кое се протега.
- На крајот, секоја ќелија е поврзана со другите без јамки или изолирани делови.
Бидејќи алгоритмот на Крускал се потпира на спојување множества, може да се оптимизира со користење на алгоритмот Union-Find, кој обезбедува ефикасен начин за следење на поврзаните ќелии за време на генерирањето на лавиринтот. Можете да ја видите мојата PHP имплементација на алгоритмот Union-Find овде: Disjoint Set (Union-Find Algorithm) во PHP