Ellers algoritme doolhofgenerator

Eller's algoritme is een doolhofgeneratiealgoritme dat efficiënt perfecte doolhoven produceert (doolhoven zonder lussen en met één pad tussen twee punten) met behulp van een rij-voor-rij-benadering. Het produceert doolhoven die vergelijkbaar zijn met Kruskal's algoritme, maar het doet dit door slechts één rij per keer te genereren, zonder dat het hele doolhof in het geheugen hoeft te worden opgeslagen. Dat maakt het nuttig voor het genereren van zeer grote doolhoven op zeer beperkte systemen en voor procedurele contentgeneratie.

Een perfect doolhof is een doolhof waarin er precies één pad is van elk punt in het doolhof naar elk ander punt. Dat betekent dat je geen rondjes kunt lopen, maar dat je vaak op doodlopende paden stuit, waardoor je gedwongen wordt om te keren en terug te gaan.

De doolhofkaarten die hier worden gegenereerd bevatten een standaardversie zonder start- en eindposities, zodat je die zelf kunt bepalen: er is een oplossing van elk punt in het doolhof naar elk ander punt. Als je inspiratie wilt, kun je een voorgestelde start- en eindpositie inschakelen - en zelfs de oplossing tussen die twee bekijken.

Over het algoritme van Eller

Het algoritme van Eller werd geïntroduceerd door David Eller.

Het algoritme is opmerkelijk vanwege de efficiënte rij-voor-rij-benadering van doolhofgeneratie, waardoor het ideaal is voor oneindige doolhoven of doolhoven die in realtime worden gegenereerd. Het wordt vaak aangehaald in literatuur over procedurele contentgeneratie en doolhofgeneratie, maar ik heb geen primaire bronnen kunnen vinden die de oorspronkelijke publicatie beschrijven.

Hoe het algoritme van Eller werkt voor het genereren van doolhoven

Ellers algoritme verwerkt één rij per keer, onderhoudt en wijzigt sets van verbonden cellen. Het zorgt voor connectiviteit terwijl het lussen vermijdt, en het breidt het doolhof efficiënt naar beneden uit.

Theoretisch gezien kan het gebruikt worden om oneindige doolhoven te genereren. Om er echter zeker van te zijn dat het gegenereerde doolhof ook daadwerkelijk oplosbaar is, is het noodzakelijk om op een gegeven moment over te schakelen naar de logica van de 'laatste rij' om het doolhof te voltooien.

Stap 1: Initialiseer de eerste rij

• Wijs aan elke cel in de rij een unieke set-ID toe.

Stap 2: Enkele aangrenzende cellen horizontaal verbinden

• Voeg aangrenzende cellen willekeurig samen door ze in te stellen op dezelfde set-ID. Dit zorgt ervoor dat er horizontale doorgangen zijn.

Stap 3: Maak verticale verbindingen naar de volgende rij

• Voor elke set die in de rij voorkomt, moet minstens één cel naar beneden worden verbonden (om connectiviteit te garanderen).
• Kies willekeurig één of meer cellen uit elke set om verbinding te maken met de volgende rij.

Stap 4: Ga naar de volgende rij

• Voer de verticale verbindingen door door dezelfde set-ID toe te wijzen aan de corresponderende cellen hieronder.
• Wijs nieuwe set-ID's toe aan alle niet-toegewezen cellen.

Stap 5: Herhaal stappen 2-4 totdat de laatste rij is bereikt

• Ga rij voor rij door met verwerken.

Stap 6: Verwerk de laatste rij

• Zorg ervoor dat alle cellen in de laatste rij tot dezelfde set behoren door alle resterende afzonderlijke sets samen te voegen.