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

Крускаловиот алгоритам е алгоритам на минимално опфаќачко дрво што може да се прилагоди за генерирање лавиринти. Особено е ефикасен за создавање совршени лавиринти. Алтернатива на Крускаловиот алгоритам е Примовиот алгоритам, кој е исто така алгоритам на минимално опфаќачко дрво, но бидејќи тие генерираат идентични лавиринти, а Крускаловите работи побрзо, не се потрудив да го имплементирам Примовиот.

Совршен лавиринт е лавиринт во кој има точно една патека од која било точка во лавиринтот до која било друга точка. Тоа значи дека не можете да завршите да одите наоколу во кругови, но често ќе наидете на ќорсокак, што ќе ве принуди да се свртите и да се вратите назад.

Мапите на лавиринтот генерирани овде вклучуваат стандардна верзија без никакви позиции за почеток и крај, така што можете сами да ги решите тие: ќе има решение од која било точка во лавиринтот до која било друга точка. Ако сакате инспирација, можете да овозможите предложена почетна и завршна позиција - па дури и да го видите решението помеѓу двете.

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

Алгоритмот на Крускал е создаден од Џозеф Бернард Крускал помладиот, американски математичар, статистичар и компјутерски научник. Тој првпат го опишал алгоритмот во 1956 година во својот труд „За најкраткото опфатно поддрво на граф и проблемот со патувачкиот продавач“.

Алгоритмот е дизајниран да го пронајде минималното опфаќачко дрво (MST) на графот, осигурувајќи дека сите темиња се поврзани со минималната можна вкупна тежина на работ, а воедно избегнувајќи циклуси.

Како функционира алгоритмот на Крускал за генерирање лавиринти

Чекор 1: Иницијализирај

• Третирајте ја секоја клетка во лавиринтот како посебен сет (уникатна компонента).
• Наведете ги сите ѕидови помеѓу соседните ќелии како потенцијални рабови.

Чекор 2: Сортирајте ги ѕидовите

• Мешајте ги или подредете ги ѕидовите по случаен редослед. Ако го имплементирате како вистински Крускалов алгоритам, подредете ги ѕидовите по случаен редослед (бидејќи генерирањето лавиринт не бара тежини).

Чекор 3: Процесни ѕидови

• Поминете низ измешаните ѕидови.
• Ако двете ќелии поделени со ѕидот припаѓаат на различни множества (т.е. тие сè уште не се поврзани во лавиринтот), отстранете го ѕидот и спојте ги множествата.
• Ако веќе се во истиот сет, прескокнете го ѕидот (за да избегнете циклуси).

Чекор 4: Продолжете до завршување

• Повторете го овој процес сè додека сите ќелии не се поврзат, формирајќи едно опфаќачко дрво.
• На крајот, секоја ќелија е поврзана со другите без јамки или изолирани делови.

Бидејќи алгоритмот на Крускал се потпира на спојување на множества, тој може да се оптимизира со користење на алгоритмот Union-Find, кој обезбедува ефикасен начин за следење на поврзаните ќелии за време на генерирањето на лавиринт. Можете да ја видите мојата PHP имплементација на алгоритмот Union-Find тука: Линк

Дополнително читање

Ако ви се допадна овој пост, можеби ќе ви се допаднат и овие предлози:

• Вилсоновиот алгоритам генератор на лавиринт
• Лови и убиј генератор на лавиринт
• Генератор на лавиринт на алгоритам на Елер