Ellers algoritme labyrintgenerator

Ellers algoritme er en labyrintgenereringsalgoritme, der effektivt producerer perfekte labyrinter (labyrinter uden løkker og med en enkelt sti mellem to punkter) ved hjælp af en række-for-række-tilgang. Den producerer labyrinter svarende til Kruskals algoritme, men den gør det ved kun at generere én række ad gangen uden behov for at gemme hele labyrinten i hukommelsen. Det gør den nyttig til at generere meget store labyrinter på meget begrænsede systemer og til generering af proceduremæssigt indhold.

En perfekt labyrint er en labyrint, hvor der er præcis én vej fra et hvilket som helst punkt i labyrinten til et hvilket som helst andet punkt. Det betyder, at du ikke kan ende med at gå rundt i cirkler, men du vil ofte støde på blindgyder, som tvinger dig til at vende om og gå tilbage.

De labyrintkort, der genereres her, indeholder en standardversion uden start- og slutpositioner, så du selv kan bestemme dem: der vil være en løsning fra ethvert punkt i labyrinten til ethvert andet punkt. Hvis du vil have inspiration, kan du aktivere en foreslået start- og slutposition - og endda se løsningen mellem de to.

Om Ellers algoritme

Ellers algoritme blev introduceret af David Eller.

Algoritmen er kendt for sin effektive række-for-række-tilgang til labyrintgenerering, hvilket gør den ideel til uendelige labyrinter eller labyrinter genereret i realtid. Den citeres ofte i litteraturen om proceduremæssig indholdsgenerering og labyrintgenerering, men jeg har ikke været i stand til at finde primære kilder, der beskriver dens oprindelige publikation.

Hvordan Ellers algoritme fungerer til labyrintgenerering

Ellers algoritme behandler én række ad gangen og vedligeholder og ændrer sæt af forbundne celler. Den sikrer forbindelse, undgår løkker og udvider effektivt labyrinten nedad.

Det kan teoretisk set bruges til at generere uendelige labyrinter, men for at sikre, at den genererede labyrint faktisk er løsbar, er det nødvendigt at skifte til "sidste række"-logikken på et tidspunkt for at afslutte labyrinten.

Trin 1: Initialiser den første række

• Tildel hver celle i rækken et unikt sæt-ID.

Trin 2: Forbind nogle tilstødende celler vandret

• Flet tilfældigt tilstødende celler ved at indstille dem til det samme sæt-ID. Dette sikrer, at der er vandrette passager.

Trin 3: Opret lodrette forbindelser til den næste række

• For hvert sæt, der vises i rækken, skal mindst én celle forbindes nedad (for at sikre forbindelse).
• Vælg tilfældigt en eller flere celler fra hvert sæt for at forbinde til den næste række.

Trin 4: Gå til næste række

• Fremfør de vertikale forbindelser ved at tildele det samme sæt-ID til de tilsvarende celler nedenfor.
• Tildel nye sæt-ID'er til alle ikke-tildelte celler.

Trin 5: Gentag trin 2-4, indtil den sidste række er nået

• Fortsæt behandlingen række for række.

Trin 6: Behandl den sidste række

• Sørg for, at alle celler i den sidste række tilhører det samme sæt, ved at flette eventuelle resterende separate sæt.

Yderligere læsning

Hvis du kunne lide dette indlæg, kan du måske også lide disse forslag:

• Kruskal's Algoritme Maze Generator
• Jag og dræb labyrintgenerator
• Rekursiv Backtracker Maze Generator