Генератор на лабиринт на алгоритъма на Уилсън

Алгоритъмът на Уилсън е метод за случайно блуждаене с изтриване на цикъл, който генерира равномерни обхващащи дървета за създаване на лабиринти. Това означава, че всички възможни лабиринти с даден размер са с еднаква вероятност да бъдат генерирани, което го прави безпристрастна техника за генериране на лабиринти. Алгоритъмът на Уилсън може да се счита за подобрена версия на алгоритъма на Алдус-Бродър, тъй като генерира лабиринти с идентични характеристики, но работи много по-бързо, така че не съм си направил труда да го имплементирам тук.

Перфектен лабиринт е лабиринт, в който има точно един път от всяка точка в лабиринта до всяка друга точка. Това означава, че не можете да се въртите в кръг, но често ще срещате задънени улици, което ще ви принуди да се обърнете и да се върнете обратно.

Генерираните тук карти на лабиринта включват версия по подразбиране без начални и крайни позиции, така че можете да ги определите сами: ще има решение от всяка точка в лабиринта до всяка друга точка. Ако искате да получите вдъхновение, можете да активирате предложена начална и крайна позиция - и дори да видите решението между двете.

Относно алгоритъма на Уилсън

Алгоритъмът на Уилсън за генериране на равномерни обхващащи дървета, използвайки случайна стена с изтрит цикъл, е създаден от Дейвид Брус Уилсън.

Уилсън първоначално въвежда този алгоритъм през 1996 г., докато изследва случайни обхващащи дървета и вериги на Марков в теорията на вероятностите. Въпреки че работата му е предимно в областта на математиката и статистическата физика, алгоритъмът оттогава е широко възприет за генериране на лабиринти поради способността си да създава идеално еднородни лабиринти.

Как работи алгоритъмът на Уилсън за генериране на лабиринти

Алгоритъмът на Уилсън гарантира, че крайният лабиринт е напълно свързан без никакви цикли чрез итеративно издълбаване на пътища от непосетени клетки, използвайки случайни разходки.

Стъпка 1: Инициализиране

• Започнете с решетка, запълнена със стени.
• Дефинирайте списък с всички възможни клетки за пасаж.

Стъпка 2: Изберете произволна начална клетка

• Изберете произволна клетка и я маркирайте като посетена. Това служи като начална точка на лабиринта по време на генерирането.

Стъпка 3: Случайно блуждаене с изтриване на цикъл

• Изберете непосетена клетка и започнете произволно разходка (движене в произволни посоки).
• Ако разходката достигне вече посетена клетка, изтрийте всички цикли в пътя.
• След като разходката се свърже с посетения регион, маркирайте всички клетки в пътя като посетени.

Стъпка 4: Повтаряйте, докато не бъдат посетени всички клетки:

• Продължете да избирате непосетени клетки и да извършвате произволни разходки, докато всяка клетка стане част от лабиринта.

Допълнително четене

Ако ви е харесала тази публикация, може да ви харесат и тези предложения:

• Рекурсивен генератор на лабиринт за обратно проследяване
• Генератор на лабиринт за лов и убиване
• Генератор на лабиринт за алгоритъм за отглеждане на дървета