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

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

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

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

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

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

Како функционише

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

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

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

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

Даље читање

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

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