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

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

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

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

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

Крускалов алгоритам је креирао Џозеф Бернард Крускал млађи, амерички математичар, статистичар и рачунарски научник. Први пут је описао алгоритам 1956. године у свом раду „О најкраћем обухватном подстаблу графа и проблему трговачког путника“.

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

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

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

• Сваку ћелију у лавиринту третирајте као засебан скуп (јединствену компоненту).
• Наведите све зидове између суседних ћелија као потенцијалне ивице.

Корак 2: Сортирајте зидове

• Промешајте или насумично поређајте зидове. Ако се имплементира као прави Крускалов алгоритам, сортирајте зидове насумичним редоследом (пошто генерисање лавиринта не захтева тежине).

Корак 3: Обрада зидова

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

Корак 4: Наставите до завршетка

• Понављајте овај поступак док се све ћелије не повежу, формирајући једно обухватно стабло.
• На крају, свака ћелија је повезана са осталима без петљи или изолованих делова.

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

Даље читање

Ако сте уживали у овом посту, можда ће вам се свидети и ови предлози:

• Хунт анд Килл Мазе Генератор
• Вилсонов алгоритам генератор лавиринта
• Алгоритам растућег дрвета Мазе Генератор