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 prosessuell innholdsgenerering.

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 labyrintgenerering, noe som gjør den ideell for uendelige labyrinter eller labyrinter generert i sanntid. Det er ofte sitert i prosessuell innholdsgenerering og labyrintgenereringslitteratur, men jeg har ikke vært i stand til å finne primærkilder som beskriver den opprinnelige utgivelsen.

Hvordan Ellers algoritme fungerer for labyrintgenerering

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

Det kan teoretisk sett brukes til å generere uendelige labyrinter, men for å sikre at den genererte labyrinten faktisk kan løses, er det nødvendig å bytte til "siste rad"-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: Bli med i noen tilstøtende celler horisontalt

• Slå sammen tilstøtende celler tilfeldig 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 en eller flere celler tilfeldig fra hvert sett for å koble til neste rad.

Trinn 4: Gå til neste rad

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

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

• Fortsett å behandle rad for rad.

Trinn 6: Behandle den siste raden

• Kontroller at alle cellene i den siste raden tilhører samme sett ved å slå sammen eventuelle gjenværende separate sett.

Videre lesing

Hvis du likte dette innlegget, kan du også like disse forslagene:

• Wilsons algoritme labyrintgenerator
• Growing Tree algoritme labyrintgenerator
• Kruskals algoritme-labyrint-generator