Вилсоновиот алгоритам генератор на лавиринт
Објавено: 5 март 2025, во 19:51:14 UTC
Генератор на лавиринт користејќи го Вилсоновиот алгоритам за да создаде совршен лавиринт. Овој алгоритам ги генерира сите можни лавиринти со дадена големина со иста веројатност, така што теоретски може да генерира лавиринти со многу мешани распореди, но бидејќи има повеќе можни лавиринти со пократки коридори отколку подолги, тие почесто ќе ги гледате.Wilson's Algorithm Maze Generator
Вилсоновиот алгоритам е метод на случајно одење избришан со јамка кој генерира униформни дрвја за создавање лавиринт. Ова значи дека сите можни лавиринти со дадена големина се подеднакво веројатно да се генерираат, што го прави непристрасна техника за генерирање на лавиринт. Алгоритмот на Вилсон може да се смета за подобрена верзија на алгоритмот Алдос-Бродер, бидејќи генерира лавиринти со идентични карактеристики, но работи многу побрзо, па затоа не се мачев овде да го имплементирам алгоритмот Алдос-Бродер.
Совршен лавиринт е лавиринт во кој има точно една патека од која било точка во лавиринтот до која било друга точка. Тоа значи дека не можете да завршите да одите наоколу во кругови, но често ќе наидете на ќорсокак, што ќе ве принуди да се свртите и да се вратите назад.
Мапите на лавиринтот генерирани овде вклучуваат стандардна верзија без никакви позиции за почеток и крај, така што можете сами да ги решите тие: ќе има решение од која било точка во лавиринтот до која било друга точка. Ако сакате инспирација, можете да овозможите предложена почетна и завршна позиција - па дури и да го видите решението помеѓу двете.
За Вилсоновиот алгоритам
Вилсоновиот алгоритам за генерирање униформни дрвја со користење на случаен ѕид избришан со јамка е создаден од Дејвид Брус Вилсон.
Вилсон првично го воведе овој алгоритам во 1996 година додека истражуваше случајни опфатени дрвја и Маркови синџири во теоријата на веројатност. Иако неговата работа беше првенствено во математиката и статистичката физика, оттогаш алгоритмот е широко прифатен за генерирање на лавиринт поради неговата способност да произведува совршено униформни лавиринти.
Како функционира алгоритмот на Вилсон за генерацијата на лавиринтот
Алгоритмот на Вилсон осигурува дека последниот лавиринт е целосно поврзан без никакви јамки со итеративно резбање патеки од непосетени ќелии користејќи случајни прошетки.
Чекор 1: Иницијализирајте
- Започнете со решетка исполнета со ѕидови.
- Дефинирајте листа на сите можни ќелии за премин.
Чекор 2: Изберете случајна почетна ќелија
- Изберете која било случајна ќелија и означете ја како посетена. Ова служи како почетна точка на лавиринтот за време на генерирањето.
Чекор 3: Случајно одење со бришење со јамка
- Изберете непосетена ќелија и започнете случајно одење (движете се во случајни насоки).
- Ако прошетката стигне до веќе посетена ќелија, избришете ги сите јамки на патеката.
- Откако прошетката ќе се поврзе со посетениот регион, означете ги сите ќелии на патеката како посетени.
Чекор 4: Повторете додека не се посетат сите ќелии :
- Продолжете да избирате непосетени ќелии и да изведувате случајни прошетки додека секоја клетка не стане дел од лавиринтот.