Крускалов алгоритам Мазе Генератор
Објављено: 16. фебруар 2025. 18:09:25 UTC
Генератор лавиринта који користи Крускалов алгоритам за креирање савршеног лавиринта. Овај алгоритам тежи да креира лавиринте са ходницима средње дужине и много ћорсокака, као и прилично право решење.Kruskal's Algorithm Maze Generator
Крускалов алгоритам је минимални алгоритам разапињућег стабла који се може прилагодити за генерисање лавиринта. Посебно је ефикасан за стварање савршених лавиринта. Алтернатива Крускаловом алгоритму је Примов алгоритам, који је такође алгоритам минималног разапињућег стабла, али пошто они генеришу идентичне лавиринте и Крускалов алгоритам ради брже, нисам се трудио да применим Примов алгоритам.
Савршен лавиринт је лавиринт у коме постоји тачно један пут од било које тачке у лавиринту до било које друге тачке. То значи да не можете завршити да се вртите у круг, али ћете често наићи на ћорсокак, приморавајући вас да се окренете и вратите назад.
Мапе лавиринта генерисане овде укључују подразумевану верзију без икаквих почетних и завршних позиција, тако да можете сами да их одлучите: постојаће решење од било које тачке у лавиринту до било које друге тачке. Ако желите инспирацију, можете омогућити предложену почетну и циљну позицију - па чак и видети решење између њих.
О Крускаловом алгоритму
Крускалов алгоритам креирао је Џозеф Бернард Крускал, млађи, амерички математичар, статистичар и информатичар. Он је први пут описао алгоритам 1956. године у свом раду „О најкраћем распонском подстаблу графа и проблему трговачког путника“.
Алгоритам је дизајниран да пронађе минимално разапињуће стабло (МСТ) графа, обезбеђујући да су сви врхови повезани са минималном могућом укупном тежином ивице уз избегавање циклуса.
Како Крускалов алгоритам функционише за генерисање лавиринта
Корак 1: Иницијализација
- Третирајте сваку ћелију у лавиринту као посебан скуп (јединствена компонента).
- Наведите све зидове између суседних ћелија као потенцијалне ивице.
Корак 2: Сортирајте зидове
- Промешајте или насумично поређајте зидове. Ако га имплементирате као прави Крускалов алгоритам, сортирајте зидове насумичним редоследом (пошто генерисање лавиринта не захтева тежине).
Корак 3: Обрадите зидове
- Итерирајте кроз измешане зидове.
- Ако две ћелије подељене зидом припадају различитим скуповима (тј. још увек нису повезане у лавиринту), уклоните зид и спојите скупове.
- Ако су већ у истом сету, прескочите зид (да бисте избегли циклусе).
Корак 4: Наставите до завршетка
- Понављајте овај процес док се све ћелије не повежу, формирајући једно разапињуће стабло.
- На крају, свака ћелија је повезана са осталима без петљи или изолованих делова.
Пошто се Крускалов алгоритам ослања на спајање скупова, може се оптимизовати коришћењем Унион-Финд алгоритма, који обезбеђује ефикасан начин за праћење повезаних ћелија током генерисања лавиринта. Можете видети моју ПХП имплементацију алгоритма Унион-Финд овде: Дисјунктни скуп (Алгоритам Унион-Финд) у ПХП-у