Ellers algoritme-labyrintgenerator

Ellers algoritme er en labyrintgenereringsalgoritme som effektivt produserer perfekte labyrinter (labyrinter uten løkker og en enkelt bane mellom to punkter) ved hjelp av en rad-for-rad-tilnærming. Den produserer labyrinter som ligner på Kruskals algoritme, men den gjør det ved å generere bare én rad om gangen, uten behov for å lagre hele labyrinten i minnet. Det gjør det nyttig for å generere veldig store labyrinter på svært begrensede systemer og for prosedyreinnholdsgenerering.

En perfekt labyrint er en labyrint der det finnes nøyaktig én vei fra et hvilket som helst punkt i labyrinten til et hvilket som helst annet punkt. Det betyr at du ikke kan ende opp med å gå i sirkler, men at du ofte vil støte på blindveier som tvinger deg til å snu og gå tilbake.

Labyrintkartene som genereres her, inneholder en standardversjon uten start- og målposisjoner, slik at du selv kan bestemme disse: Det vil finnes en løsning fra et hvilket som helst punkt i labyrinten til et hvilket som helst annet punkt. Hvis du vil ha inspirasjon, kan du aktivere en foreslått start- og målposisjon - og til og med se løsningen mellom de to.

Om Ellers algoritme

Ellers algoritme ble introdusert av David Eller.

Algoritmen er kjent for sin effektive rad-for-rad-tilnærming til generering av labyrint, noe som gjør den ideell for uendelige labyrinter eller labyrinter generert i sanntid. Det er ofte sitert i prosedyreinnholdsgenerering og labyrintgenerasjonslitteratur, men jeg har ikke vært i stand til å finne primærkilder som beskriver dens opprinnelige publikasjon.

Hvordan Ellers algoritme fungerer for labyrintgenerering

Ellers algoritme behandler en rad om gangen, og vedlikeholder og modifiserer sett med tilkoblede celler. Den sikrer tilkobling samtidig som den unngår løkker, og den utvider labyrinten effektivt nedover.

Den kan teoretisk brukes til å generere uendelige labyrinter, men for å sikre at den genererte labyrinten faktisk er løsbar, er det nødvendig å bytte til "final row"-logikken på et tidspunkt for å fullføre labyrinten.

Trinn 1: Initialiser den første raden

• Tilordne hver celle i raden en unik sett-ID.

Trinn 2: Koble sammen noen tilstøtende celler horisontalt

• Slå tilfeldig sammen tilstøtende celler ved å sette dem til samme sett-ID. Dette sikrer at det er horisontale passasjer.

Trinn 3: Opprett vertikale tilkoblinger til neste rad

• For hvert sett som vises i raden, må minst én celle kobles nedover (for å sikre tilkobling).
• Velg tilfeldig én eller flere celler fra hvert sett for å koble til neste rad.

Trinn 4: Flytt til neste rad

• Før de vertikale forbindelsene videre ved å tilordne samme sett-ID til de tilsvarende cellene nedenfor.
• Tilordne nye sett-ID-er til ikke-tilordnede celler.

Trinn 5: Gjenta trinn 2–4 til siste rad er nådd

• Fortsett å behandle rad for rad.

Trinn 6: Behandle den siste raden

• Sørg for at alle cellene i den siste raden tilhører det samme settet ved å slå sammen eventuelle gjenværende separate sett.