Хунт анд Килл Мазе Генератор
Објављено: 16. фебруар 2025. 21:04:21 UTC
Генератор лавиринта који користи алгоритам Хунт анд Килл за креирање савршеног лавиринта. Овај алгоритам је сличан Рецурсиве Бацктрацкер-у, али има тенденцију да генерише лавиринте са нешто мање дугим, кривудавим ходницима.Hunt and Kill Maze Generator
Алгоритам Хунт анд Килл је заиста модификована верзија рекурзивног бацктрацкера. Модификација се састоји од систематског скенирања (или "лова") за наставак нове ћелије од када не може да иде даље, за разлику од праве рекурзивне претраге, која ће се увек вратити на претходну ћелију на стеку.
Због тога, овај алгоритам се лако може прилагодити да генерише лавиринте са различитим изгледом и осећајем, само одабиром да уђете у режим „лова“ чешће или према одређеним правилима. Верзија која је овде имплементирана улази у режим „лова“ само када не може да иде даље од тренутне ћелије.
Савршен лавиринт је лавиринт у коме постоји тачно један пут од било које тачке у лавиринту до било које друге тачке. То значи да не можете завршити да се вртите у круг, али ћете често наићи на ћорсокак, приморавајући вас да се окренете и вратите назад.
Мапе лавиринта генерисане овде укључују подразумевану верзију без икаквих почетних и завршних позиција, тако да можете сами да их одлучите: постојаће решење од било које тачке у лавиринту до било које друге тачке. Ако желите инспирацију, можете омогућити предложену почетну и циљну позицију - па чак и видети решење између њих.
О алгоритму Хунт анд Килл
Алгоритам Хунт анд Килл је једноставан, али ефикасан метод за генерисање лавиринта. То је донекле слично претрази у дубину (тј. алгоритам рекурзивног праћења назад), осим када не може да оде даље од тренутне позиције, систематски скенира (или „лови“) преко лавиринта да пронађе нову ћелију из које ће наставити. Алгоритам се састоји од две главне фазе: ходања и лова.
Како функционише алгоритам Хунт анд Килл за генерацију Мазе
Корак 1: Почните од насумичне ћелије
- Пронађите насумичну ћелију у мрежи и означите је као посећену.
Корак 2: Фаза ходања (насумично ходање)
- Изаберите насумично непосећеног комшију.
- Пређите до тог суседа, означите га као посећеног и урезујте пут између претходне и нове ћелије.
- Понављајте све док не остане ниједног непосећеног суседа.
Корак 3: Фаза лова (повратак путем скенирања)
- Скенирајте мрежу ред по ред (или колону по колону).
- Пронађите прву непосећену ћелију која има бар једног посећеног комшију.
- Повежите ту ћелију са посећеним суседом да бисте наставили фазу ходања.
- Понављајте све док не посетите све ћелије.