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

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

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

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

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

Елеровиот алгоритам го воведе Дејвид Елер.

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

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

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

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

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

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

Чекор 2: Спојте неколку соседни ќелии хоризонтално

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

Чекор 3: Креирајте вертикални врски со следниот ред

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

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

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

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

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

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

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

Дополнително читање

Ако ви се допадна овој пост, можеби ќе ви се допаднат и овие предлози:

• Рекурзивен Backtracker Лавиринт Генератор
• Генератор на лавиринт со алгоритам на растечки дрвја
• Крускалов алгоритамски генератор на лавиринт