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

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

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

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

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

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

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

Како Вилсоновиот алгоритам работи за генерирање лавиринти

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

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

• Започнете со мрежа исполнета со ѕидови.
• Дефинирајте список на сите можни ќелии за премин.

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

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

Чекор 3: Случајно движење со бришење на јамка

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

Чекор 4: Повторете додека не се посетат сите ќелии:

• Продолжете со избирање на непосетени ќелии и изведување случајни прошетки сè додека секоја клетка не стане дел од лавиринтот.

Дополнително читање

Ако ви се допадна овој пост, можеби ќе ви се допаднат и овие предлози:

• Генератор на лавиринт на алгоритам на Елер
• Лови и убиј генератор на лавиринт
• Рекурзивен Backtracker Лавиринт Генератор