Вилсонов алгоритам генератор лавиринта
Објављено: 16. фебруар 2025. 19:38:15 UTC
Генератор лавиринта који користи Вилсонов алгоритам за креирање савршеног лавиринта. Овај алгоритам генерише све могуће лавиринте дате величине са истом вероватноћом, тако да у теорији може да генерише лавиринте многих мешовитих распореда, али пошто постоји више могућих лавиринта са краћим ходницима него дужим, чешће ћете их видети.Wilson's Algorithm Maze Generator
Вилсонов алгоритам је метода случајног хода са брисањем петље која генерише једнообразна стабла која се протежу за креирање лавиринта. То значи да су сви могући лавиринти дате величине једнако вероватно да ће бити генерисани, што га чини непристрасном техником генерисања лавиринта. Вилсонов алгоритам се може сматрати побољшаном верзијом Алдоус-Бродеровог алгоритма, пошто генерише лавиринте са идентичним карактеристикама, али ради много брже, тако да се овде нисам трудио да применим Алдоус-Бродер алгоритам.
Савршен лавиринт је лавиринт у коме постоји тачно један пут од било које тачке у лавиринту до било које друге тачке. То значи да не можете завршити да се вртите у круг, али ћете често наићи на ћорсокак, приморавајући вас да се окренете и вратите назад.
Мапе лавиринта генерисане овде укључују подразумевану верзију без икаквих почетних и завршних позиција, тако да можете сами да их одлучите: постојаће решење од било које тачке у лавиринту до било које друге тачке. Ако желите инспирацију, можете омогућити предложену почетну и циљну позицију - па чак и видети решење између њих.
О Вилсоновом алгоритму
Вилсонов алгоритам за генерисање уједначених раздвојених стабала користећи насумични зид обрисан кроз петљу креирао је Давид Бруце Вилсон.
Вилсон је првобитно увео овај алгоритам 1996. док је истраживао насумична стабла и Марковљеве ланце у теорији вероватноће. Иако је његов рад био првенствено у математици и статистичкој физици, алгоритам је од тада широко прихваћен за генерисање лавиринта због своје способности да произведе савршено уједначене лавиринте.
Како Вилсонов алгоритам функционише за генерисање лавиринта
Вилсонов алгоритам осигурава да је коначни лавиринт у потпуности повезан без икаквих петљи тако што се итеративно урезују путање из непосећених ћелија користећи насумичне шетње.
Корак 1: Иницијализација
- Почните са мрежом испуњеном зидовима.
- Дефинишите листу свих могућих ћелија пролаза.
Корак 2: Одаберите насумично почетну ћелију
- Изаберите било коју насумично одабрану ћелију и означите је као посећену. Ово служи као почетна тачка лавиринта током генерације.
Корак 3: Насумично ходање са брисањем петље
- Изаберите непосећену ћелију и започните насумично шетњу (крећући се у насумичним правцима).
- Ако шетња дође до већ посећене ћелије, обришите све петље на путу.
- Када се шетња повеже са посећеним регионом, означите све ћелије на стази као посећене.
Корак 4: Понављајте све док се не посете све ћелије :
- Наставите да бирате непосећене ћелије и изводите насумичне шетње док свака ћелија не постане део лавиринта.