Рекурзивни Бацктрацкер Мазе Генератор

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

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

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

Рекурзивни алгоритам бацктрацкер-а је метода претраге у дубину за генерисање савршених лавиринта (лавиринт без петљи и једне путање између било које две тачке). Једноставан је, ефикасан и ствара визуелно привлачне лавиринте са дугим, кривудавим ходницима.

Упркос свом имену, не мора нужно да се имплементира помоћу рекурзије. Често се имплементира у итеративном приступу користећи ЛИФО ред (тј. стек). За веома велике лавиринте, коришћење рекурзије ће вероватније довести до прекорачења стека позива, у зависности од програмског језика и доступне меморије. ЛИФО ред се може лакше прилагодити за руковање великим количинама података, чак и чување реда на диску или у бази података ако је расположива меморија недовољна.

Како то ради

Алгоритам ради користећи приступ претрази у дубину заснован на стеку. Ево детаљног прегледа:

1. Изаберите почетну ћелију и означите је као посећену.
2. Док постоје непосећене ћелије:
   • Погледајте суседне ћелије које још нису посећене.
   • Ако постоји бар један непосећени сусед:
     • Насумично изаберите једног од непосећених суседа.
     • Уклоните зид између тренутне ћелије и изабраног суседа.
     • Пређите на изабраног суседа и означите га као посећеног.
     • Гурните тренутну ћелију на стек.
   • Ако нема непоходених комшија:
     • Вратите се тако што ћете искочити последњу ћелију из стека.
3. Наставите са овим процесом док се стек не испразни.

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

Ја заправо имам две верзије овог алгоритма у игри на овом сајту: ону засновану на ЛИФО реду за генерисање лавиринта на овој страници и ону засновану на рекурзији за решавање лавиринта, такође лавиринта генерисаних другим алгоритмима (тако се праве карте са решењима). Имати две различите верзије је само за спорт јер сам штребер коме је то занимљиво, и једна и друга би могла да упали за обе ;-)