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

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

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

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

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

Алгоритъмът на Елър е представен от Дейвид Елър.

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

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

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

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

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

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

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

• Случайно обединете съседни клетки, като им зададете един и същ идентификатор на набор. Това гарантира наличието на хоризонтални проходи.

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

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

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

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

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

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

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

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

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

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

• Генератор на лабиринт за алгоритъм за отглеждане на дървета
• Генератор на лабиринти с алгоритъм на Kruskal
• Генератор на лабиринт на алгоритъма на Уилсън