Ellers algoritm labyrintgenerator

Ellers algoritm är en labyrintgenereringsalgoritm som effektivt producerar perfekta labyrinter (labyrinter utan loopar och en enda väg mellan två punkter) med hjälp av en rad-för-rad-metod. Den producerar labyrinter som liknar Kruskals algoritm, men den gör det genom att generera bara en rad i taget, utan behov av att lagra hela labyrinten i minnet. Det gör den användbar för att generera mycket stora labyrinter på mycket begränsade system och för generering av procedurmässigt innehåll.

En perfekt labyrint är en labyrint där det finns exakt en väg från varje punkt i labyrinten till varje annan punkt. Det betyder att du inte kan gå runt i cirklar, men du kommer ofta att stöta på återvändsgränder, vilket tvingar dig att vända om och gå tillbaka.

De labyrintkartor som genereras här innehåller en standardversion utan några start- och målpositioner, så att du själv kan bestämma dem: det kommer att finnas en lösning från vilken punkt som helst i labyrinten till vilken annan punkt som helst. Om du vill ha inspiration kan du aktivera en föreslagen start- och målposition - och till och med se lösningen mellan de två.

Om Ellers algoritm

Ellers algoritm introducerades av David Eller.

Algoritmen är känd för sin effektiva rad-för-rad-metod för labyrintgenerering, vilket gör den idealisk för oändliga labyrinter eller labyrinter som genereras i realtid. Den citeras ofta i litteratur om procedurgenerering av innehåll och labyrintgenerering, men jag har inte kunnat hitta primärkällor som beskriver dess ursprungliga publicering.

Hur Ellers algoritm fungerar för labyrintgenerering

Ellers algoritm bearbetar en rad i taget, och underhåller och modifierar uppsättningar av sammankopplade celler. Den säkerställer anslutning samtidigt som loopar undviks, och den utökar effektivt labyrinten nedåt.

Den kan teoretiskt sett användas för att generera oändliga labyrinter, men för att säkerställa att den genererade labyrinten faktiskt är lösbar är det nödvändigt att byta till "sista raden"-logiken någon gång för att avsluta labyrinten.

Steg 1: Initiera den första raden

• Tilldela varje cell i raden ett unikt set-ID.

Steg 2: Koppla ihop några intilliggande celler horisontellt

• Slå samman intilliggande celler slumpmässigt genom att ställa in dem till samma set-ID. Detta säkerställer att det finns horisontella passager.

Steg 3: Skapa vertikala anslutningar till nästa rad

• För varje uppsättning som visas i raden måste minst en cell ansluta nedåt (för att säkerställa anslutning).
• Välj slumpmässigt en eller flera celler från varje uppsättning för att ansluta till nästa rad.

Steg 4: Gå till nästa rad

• För fram de vertikala kopplingarna genom att tilldela samma set-ID till motsvarande celler nedan.
• Tilldela nya uppsättnings-ID:n till alla otilldelade celler.

Steg 5: Upprepa steg 2–4 tills den sista raden är nådd

• Fortsätt bearbeta rad för rad.

Steg 6: Bearbeta den sista raden

• Se till att alla celler i den sista raden tillhör samma uppsättning genom att sammanfoga eventuella återstående separata uppsättningar.

Vidare läsning

Om du gillade det här inlägget kanske du också gillar dessa förslag:

• Wilsons algoritm labyrintgenerator
• Växande trädalgoritm labyrintgenerator
• Jaga och döda labyrintgenerator