Генератор на лабиринт на алгоритъма на Уилсън
Публикувано: 16 февруари 2025 г. в 19:30:46 ч. UTC
Генератор на лабиринт, използващ алгоритъма на Уилсън за създаване на перфектен лабиринт. Този алгоритъм генерира всички възможни лабиринти с даден размер с еднаква вероятност, така че на теория може да генерира лабиринти с много смесени оформления, но тъй като има повече възможни лабиринти с по-къси коридори, отколкото по-дълги, ще ги виждате по-често.Wilson's Algorithm Maze Generator
Алгоритъмът на Уилсън е метод за случайно ходене, който генерира еднакви обхващащи дървета за създаване на лабиринт. Това означава, че всички възможни лабиринти с даден размер са еднакво вероятно да бъдат генерирани, което го прави безпристрастна техника за генериране на лабиринти. Алгоритъмът на Уилсън може да се счита за подобрена версия на алгоритъма на Олдъс-Бродър, тъй като генерира лабиринти с идентични характеристики, но работи много по-бързо, така че не съм си направил труда да имплементирам алгоритъма на Олдъс-Бродер тук.
Перфектен лабиринт е лабиринт, в който има точно един път от всяка точка в лабиринта до всяка друга точка. Това означава, че не можете да се въртите в кръг, но често ще срещате задънени улици, което ще ви принуди да се обърнете и да се върнете обратно.
Генерираните тук карти на лабиринта включват версия по подразбиране без начални и крайни позиции, така че можете да ги определите сами: ще има решение от всяка точка в лабиринта до всяка друга точка. Ако искате да получите вдъхновение, можете да активирате предложена начална и крайна позиция - и дори да видите решението между двете.
За алгоритъма на Уилсън
Алгоритъмът на Уилсън за генериране на еднакви обхващащи дървета с помощта на случайна стена е създаден от Дейвид Брус Уилсън.
Уилсън първоначално въвежда този алгоритъм през 1996 г., докато изследва произволно обхващащи дървета и вериги на Марков в теорията на вероятностите. Въпреки че работата му е предимно в областта на математиката и статистическата физика, оттогава алгоритъмът е широко приет за генериране на лабиринти поради способността му да създава идеално еднородни лабиринти.
Как работи алгоритъмът на Уилсън за генериране на лабиринт
Алгоритъмът на Уилсън гарантира, че крайният лабиринт е напълно свързан без никакви цикли чрез итеративно издълбаване на пътеки от непосещавани клетки с помощта на случайни разходки.
Стъпка 1: Инициализиране
- Започнете с решетка, пълна със стени.
- Определете списък с всички възможни клетки за преминаване.
Стъпка 2: Изберете произволна начална клетка
- Изберете произволна клетка и я маркирайте като посетена. Това служи като отправна точка на лабиринта по време на поколението.
Стъпка 3: Произволна разходка с изтриване на цикъл
- Изберете непосетена клетка и започнете произволна разходка (движеща се в произволни посоки).
- Ако разходката достигне вече посетена клетка, изтрийте всички бримки по пътеката.
- След като разходката се свърже с посетения регион, маркирайте всички клетки в пътеката като посетени.
Стъпка 4: Повторете, докато всички клетки бъдат посетени:
- Продължете да избирате непосетени клетки и да извършвате произволни разходки, докато всяка клетка стане част от лабиринта.