Хунт анд Килл Мазе Генератор

Алгоритам „Потражи и убиј“ је заправо модификована верзија рекурзивног алгоритма за праћење уназад. Модификација се састоји од систематског скенирања (или „ловљења“) нове ћелије за наставак одакле се више не може, за разлику од правог рекурзивног претраживања, које ће се увек вратити на претходну ћелију на стеку.

Због тога се овај алгоритам може лако прилагодити за генерисање лавиринта са различитим изгледом и осећајем, једноставним избором чешћег уласка у режим „лова“ или према одређеним правилима. Верзија имплементирана овде улази у режим „лова“ само када не може даље од тренутне ћелије.

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

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

О алгоритму за лов и убијање

Алгоритам „Лови и убиј“ је једноставан, али ефикасан метод за генерисање лавиринта. Донекле је сличан претраживању у дубину (тј. алгоритму рекурзивног праћења уназад), осим што када не може даље од тренутне позиције, систематски скенира (или „лови“) лавиринт како би пронашао нову ћелију из које ће наставити. Алгоритам се састоји од две главне фазе: ходања и лова.

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

Корак 1: Почните од насумичне ћелије

• Пронађите случајну ћелију у мрежи и означите је као посећену.

Корак 2: Фаза ходања (Случајно ходање)

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

Корак 3: Фаза лова (враћање уназад путем скенирања)

• Скенирајте мрежу ред по ред (или колону по колону).
• Пронађите прву непосећену ћелију која има барем једног посећеног суседа.
• Повежите ту ћелију са посећеним комшијом да бисте наставили фазу ходања.
• Понављајте док се не посете све ћелије.

Даље читање

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

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