Generator labirinta Ellerovog algoritma

Ellerov algoritam je algoritam za generiranje labirinta koji učinkovito stvara savršene labirinte (labirinte bez petlji i s jednim putem između bilo koje dvije točke) koristeći pristup redak po redak. Stvara labirinte slično Kruskalovom algoritmu, ali to čini generiranjem samo jednog retka odjednom, 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 je predstavio David Eller.

Algoritam je poznat po svom učinkovitom pristupu generiranju labirinta red po red, što ga čini idealnim za beskonačne labirinte ili labirinte generirane u stvarnom vremenu. Često se citira u literaturi o proceduralnom generiranju sadržaja i generiranju labirinta, ali nisam uspio pronaći primarne izvore koji detaljno opisuju njegovu originalnu objavu.

Kako Ellerov algoritam funkcionira za generiranje labirinta

Ellerov algoritam obrađuje jedan redak istovremeno, održavajući i mijenjajući skupove povezanih ćelija. Osigurava povezanost izbjegavajući petlje i učinkovito proširuje labirint prema dolje.

Teoretski se može koristiti za generiranje beskonačnih labirinata, međutim, kako bi se osiguralo da je generirani labirint zapravo rješiv, potrebno je u nekom trenutku prebaciti se na logiku "završnog retka" kako bi se labirint završio.

Korak 1: Inicijalizirajte prvi redak

• Dodijelite svakoj ćeliji u retku jedinstveni ID skupa.

Korak 2: Spojite neke susjedne ćelije vodoravno

• Nasumično spojite susjedne ćelije postavljanjem istog ID-a skupa. To osigurava da postoje horizontalni prolazi.

Korak 3: Stvorite vertikalne veze sa sljedećim redom

• Za svaki skup koji se pojavljuje u retku, barem jedna ćelija mora biti spojena prema dolje (kako bi se osigurala povezanost).
• Nasumično odaberite jednu ili više ćelija iz svakog skupa kako biste ih povezali sa sljedećim redom.

Korak 4: Prijeđite na sljedeći red

• Prenesite vertikalne veze dalje dodjeljivanjem istog ID-a skupa odgovarajućim ćelijama u nastavku.
• Dodijelite nove ID-ove skupova svim nedodijeljenim ćelijama.

Korak 5: Ponovite korake 2–4 dok ne dođete do posljednjeg reda

• Nastavite obradu red po red.

Korak 6: Obradite posljednji red

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

Dodatno čitanje

Ako vam se svidio ovaj post, možda će vam se svidjeti i ovi prijedlozi:

• Rekurzivni Backtracker Maze Generator
• Kruskalov algoritam generator labirinta
• Generator Labirinta Lov i Ubijanje