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

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

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

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

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

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

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

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

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

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

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

Корак 3: Прекид

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

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

Кључна карактеристика алгоритма „Растуће дрво“ је начин на који бирате коју ће ћелију следеће обрадити. Овај избор драматично утиче на изглед лавиринта:

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

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

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

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

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

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

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

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

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

Даље читање

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

• Еллеров алгоритам генератор лавиринта
• Рекурзивни Бацктрацкер Мазе Генератор
• Хунт анд Килл Мазе Генератор