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

Алгоритъмът на Eller е алгоритъм за генериране на лабиринти, който ефективно създава перфектни лабиринти (лабиринти без цикли и единичен път между всеки две точки), използвайки подход ред по ред. Той създава лабиринти, подобни на алгоритъма на Kruskal, но го прави, като генерира само един ред наведнъж, без да е необходимо да съхранявате целия лабиринт в паметта. Това го прави полезен за генериране на много големи лабиринти на много ограничени системи и за процедурно генериране на съдържание.

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

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

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

Алгоритъмът на Eller е въведен от David Eller.

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

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

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

Теоретично може да се използва за генериране на безкрайни лабиринти, но за да се гарантира, че генерираният лабиринт действително е разрешим, е необходимо да превключите към логиката на „последния ред“ в даден момент, за да завършите лабиринта.

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

• Присвоете на всяка клетка в реда уникален набор ID.

Стъпка 2: Свържете някои съседни клетки хоризонтално

• Произволно обединяване на съседни клетки, като им зададете един и същ набор ID. Това гарантира, че има хоризонтални проходи.

Стъпка 3: Създайте вертикални връзки към следващия ред

• За всеки набор, който се появява в реда, поне една клетка трябва да се свърже надолу (за да се осигури свързаност).
• Произволно изберете една или повече клетки от всеки набор, за да се свържете със следващия ред.

Стъпка 4: Преминете към следващия ред

• Пренесете напред вертикалните връзки, като присвоите същия набор ID на съответните клетки по-долу.
• Присвояване на нови идентификатори на набори към всички неприсвоени клетки.

Стъпка 5: Повторете стъпки 2-4, докато не бъде достигнат последният ред

• Продължете да обработвате ред по ред.

Стъпка 6: Обработете последния ред

• Уверете се, че всички клетки в последния ред принадлежат към един и същи набор, като обедините всички останали отделни набори.