Generator labirinta Ellerovog algoritma

Ellerov algoritam je algoritam za generiranje labirinta koji učinkovito proizvodi savršene labirinte (labirinte bez petlji i s jednim putem između bilo koje dvije točke) korištenjem pristupa red po red. Proizvodi labirinte slične Kruskalovom algoritmu, ali to čini generiranjem samo jednog reda u isto vrijeme, bez potrebe za pohranjivanjem cijelog labirinta u memoriju. To ga čini korisnim za generiranje vrlo velikih labirinta na vrlo ograničenim sustavima i za proceduralno generiranje sadržaja.

Savršen labirint je labirint u kojem postoji točno jedan put od bilo koje točke u labirintu do bilo koje druge točke. To znači da se ne možete vrtjeti u krug, ali ćete često naići na slijepe ulice, zbog čega ćete se morati okrenuti i vratiti.

Ovdje generirane karte labirinta uključuju zadanu verziju bez ikakvih početnih i završnih pozicija, tako da ih možete sami odlučiti: postojat će rješenje od bilo koje točke u labirintu do bilo koje druge točke. Ako želite inspiraciju, možete omogućiti predloženu početnu i ciljnu poziciju - pa čak i vidjeti rješenje između ta dva.

O Ellerovom algoritmu

Ellerov algoritam predstavio je David Eller.

Algoritam je poznat po svom učinkovitom pristupu red po red generiranju labirinta, što ga čini idealnim za beskonačne labirinte ili labirinte generirane u stvarnom vremenu. Obično se navodi u proceduralnom stvaranju sadržaja i literaturi o stvaranju labirinta, ali nisam uspio pronaći primarne izvore koji opisuju njegovu izvornu publikaciju.

Kako Ellerov algoritam radi za stvaranje labirinta

Ellerov algoritam obrađuje red po red, održavajući i mijenjajući skupove povezanih ćelija. Osigurava povezanost uz izbjegavanje petlji i učinkovito proširuje labirint prema dolje.

Teoretski se može koristiti za generiranje beskonačnih labirinta, no kako bi se osiguralo da je generirani labirint stvarno rješiv, potrebno je u nekom trenutku prijeći na logiku "konačnog reda" kako bi se labirint završio.

Korak 1: Inicijalizirajte prvi red

• Svakoj ćeliji u retku dodijelite jedinstveni ID skupa.

Korak 2: Spojite neke susjedne ćelije vodoravno

• Nasumično spojite susjedne ćelije tako da im postavite isti ID skupa. To osigurava postojanje horizontalnih prolaza.

Korak 3: Stvorite okomite veze sa sljedećim redom

• Za svaki skup koji se pojavljuje u retku, najmanje jedna ćelija mora se povezati prema dolje (kako bi se osigurala povezanost).
• Nasumično odaberite jednu ili više ćelija iz svakog skupa za povezivanje sa sljedećim redom.

Korak 4: Prijeđite na sljedeći red

• Prenesite vertikalne veze dodjeljujući isti ID skupa odgovarajućim ćelijama u nastavku.
• Dodijelite nove skupne ID-ove svim nedodijeljenim ćelijama.

Korak 5: Ponavljajte korake 2-4 dok ne dođete do posljednjeg reda

• Nastavite s obradom red po red.

Korak 6: Obradite posljednji red

• Osigurajte da sve ćelije u zadnjem retku pripadaju istom skupu spajanjem svih preostalih zasebnih skupova.