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

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

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

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

О алгоритму растућег дрвета

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

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

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

• Почните са мрежом непосећених ћелија.
• Изаберите насумично почетну ћелију и додајте је на листу.

Корак 2: Петља генерисања лавиринта

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

Корак 3: Раскид

• Алгоритам се завршава када више нема ћелија на листи, што значи да је цео лавиринт исклесан.

Стратегије селекције ћелија (флексибилност алгоритма)

Дефинишућа карактеристика алгоритма растућег дрвета је начин на који бирате коју ћелију ћете обрадити следећу. Овај избор драматично утиче на изглед лавиринта:

Најновија ћелија (понашање налик стеку) – Рекурзивно праћење уназад:

• Увек изаберите последњу додату ћелију.
• Ствара дугачке, уврнуте ходнике са много ћорсокака (попут лавиринта за претрагу у дубину).
• Лабиринти имају дуге пролазе и лако их је решити.

Случајна ћелија (Рандомизовани Примов алгоритам):

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

Најстарија ћелија (понашање попут реда):

• Увек изаберите најстарију ћелију на листи.
• Генерише лавиринте са уједначенијим ширењем, као образац претраге у ширину.
• Кратки, жбунасти пролази са густим везама.
• (Ово је верзија имплементирана овде)

Хибридни приступи:

Комбинујте стратегије за различите карактеристике лавиринта. на пример:

• 90% најновије, 10% насумично: Углавном личи на рекурзивни лавиринт, али са повременим гранама које разбијају дугачке ходнике.
• 50% најновији, 50% најстарији: Уравнотежује дуге ходнике са густим растом.