Вилсонов алгоритам генератор лавиринта

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

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

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

О Вилсоновом алгоритму

Вилсонов алгоритам за генерисање униформних обухватних стабала коришћењем случајног зида обрисаног петљом креирао је Дејвид Брус Вилсон.

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

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

Вилсонов алгоритам осигурава да је коначни лавиринт потпуно повезан без икаквих петљи итеративним креирањем путања из непосећених ћелија коришћењем случајних шетњи.

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

• Почните са мрежом испуњеном зидовима.
• Дефинишите листу свих могућих ћелија пролаза.

Корак 2: Изаберите случајну почетну ћелију

• Изаберите било коју насумичну ћелију и означите је као посећену. Ово служи као почетна тачка лавиринта током генерисања.

Корак 3: Случајно шетње са брисањем петље

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

Корак 4: Понављајте док се не посете све ћелије:

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

Даље читање

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

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