Генератор на лавиринт на алгоритам на Елер

Елеровиот алгоритам е алгоритам за генерирање на лавиринт кој ефикасно произведува совршени лавиринти (лавиринти без јамки и единствена патека помеѓу кои било две точки) користејќи пристап ред до ред. Тој произведува лавиринти слични на алгоритмот на Крускал, но тоа го прави со генерирање само еден ред во исто време, без потреба од складирање на целиот лавиринт во меморија. Тоа го прави корисен за генерирање на многу големи лавиринти на многу ограничени системи и за процедурално генерирање содржина.

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

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

За Елеровиот алгоритам

Алгоритмот на Елер беше воведен од Дејвид Елер.

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

Како функционира алгоритмот на Елер за генерација на лавиринт

Алгоритмот на Елер обработува еден ред во исто време, одржувајќи и менувајќи множества поврзани ќелии. Обезбедува поврзување притоа избегнувајќи јамки и ефикасно го продолжува лавиринтот надолу.

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

Чекор 1: Иницијализирајте го првиот ред

• На секоја ќелија во редот назначете уникатен ID на множество.

Чекор 2: Хоризонтално приклучете се на некои соседни ќелии

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

Чекор 3: Создадете вертикални врски до следниот ред

• За секој сет што се појавува во редот, најмалку една ќелија мора да се поврзе надолу (за да се обезбеди поврзување).
• Случајно изберете една или повеќе ќелии од секој сет за да се поврзете со следниот ред.

Чекор 4: Преместете се на следниот ред

• Пренесете ги напред вертикалните врски со доделување на истиот сет ID на соодветните ќелии подолу.
• Доделете нови идентификатори за множество на кои било неподелени ќелии.

Чекор 5: Повторете ги чекорите 2-4 додека не се достигне последниот ред

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

Чекор 6: Обработете го последниот ред

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