Ellers algoritme labyrintgenerator

Ellers algoritme er en labyrintgenereringsalgoritme, der effektivt producerer perfekte labyrinter (labyrinter uden sløjfer og en enkelt vej mellem to vilkårlige punkter) ved hjælp af en række-for-række-tilgang. Det producerer labyrinter svarende til Kruskals algoritme, men det gør det ved kun at generere én række ad gangen, uden at det er nødvendigt at gemme hele labyrinten i hukommelsen. Det gør det nyttigt 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 bemærkelsesværdig for sin effektive række-for-række tilgang til labyrintgenerering, hvilket gør den ideel til uendelige labyrinter eller labyrinter genereret i realtid. Det er almindeligt citeret i proceduremæssig indholdsgenerering og labyrintgenerationslitteratur, men jeg har ikke været i stand til at finde primære kilder, der beskriver dets oprindelige udgivelse.

Hvordan Ellers algoritme virker for Maze Generation

Ellers algoritme behandler en række ad gangen, vedligeholder og ændrer sæt af forbundne celler. Det sikrer forbindelse, samtidig med at det undgår sløjfer, og det udvider effektivt labyrinten nedad.

Det kan teoretisk bruges til at generere uendelige labyrinter, men for at sikre, at den genererede labyrint faktisk er løselig, er det nødvendigt at skifte til "final row"-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 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: Flyt til næste række

• Før de lodrette forbindelser videre ved at tildele det samme sæt-ID til de tilsvarende celler nedenfor.
• Tildel nye sæt-id'er til ikke-tildelte celler.

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

• Fortsæt med at behandle række for række.

Trin 6: Bearbejd 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.