Ellers algoritm labyrintgenerator

Ellers algoritm är en labyrintgenereringsalgoritm som effektivt producerar perfekta labyrinter (labyrinter utan slingor och en enda väg mellan två valfria 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 bara generera en rad i taget, utan att behöva lagra hela labyrinten i minnet. Det gör det användbart för att generera mycket stora labyrinter på mycket begränsade system och för procedurinnehållsgenerering.

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-inställning till labyrintgenerering, vilket gör den idealisk för oändliga labyrinter eller labyrinter som genereras i realtid. Det citeras ofta i procedurinnehållsgenerering och labyrintgenereringslitteratur, men jag har inte kunnat hitta primära källor som beskriver dess ursprungliga publicering.

Hur Ellers algoritm fungerar för Maze Generation

Ellers algoritm bearbetar en rad i taget, underhåller och modifierar uppsättningar av anslutna celler. Den säkerställer anslutning samtidigt som den undviker loopar, och den förlänger effektivt labyrinten nedåt.

Det kan teoretiskt 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 logiken "slutraden" 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: Förena några angränsande celler horisontellt

• Slå slumpmässigt samman intilliggande celler genom att ställa in dem till samma uppsättnings-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 anslutas 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: Flytta till nästa rad

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

Steg 5: Upprepa steg 2–4 tills 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 slå samman eventuella återstående separata uppsättningar.