Ellers algoritme doolhofgenerator

Het algoritme van Eller is een algoritme voor het genereren van doolhoven dat op efficiënte wijze perfecte doolhoven produceert (doolhoven zonder lussen en met slechts één pad tussen twee willekeurige punten) door rij voor rij te werken. Het produceert doolhoven die vergelijkbaar zijn met het algoritme van Kruskal, maar doet dit door slechts één rij tegelijk te genereren, zonder dat het hele doolhof in het geheugen hoeft te worden opgeslagen. Dit maakt het nuttig voor het genereren van zeer grote doolhoven op systemen met beperkte mogelijkheden 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 Ellers algoritme

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

Het algoritme is opmerkelijk vanwege de efficiënte rij-voor-rij-aanpak voor het genereren van doolhoven, 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 ervan beschrijven.

Hoe het algoritme van Eller werkt voor het genereren van doolhoven

Het algoritme van Eller verwerkt rij voor rij, waarbij sets van verbonden cellen worden onderhouden en aangepast. Het zorgt voor connectiviteit en voorkomt lussen, en het breidt het doolhof efficiënt naar beneden uit.

Het kan theoretisch gebruikt worden om oneindige doolhoven te genereren, maar om ervoor te zorgen dat het gegenereerde doolhof daadwerkelijk oplosbaar is, is het op een bepaald moment nodig om over te schakelen naar de "laatste rij"-logica 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: Verbind enkele aangrenzende cellen horizontaal.

• Voeg willekeurig aangrenzende cellen samen door ze dezelfde set-ID te geven. Dit zorgt ervoor dat er horizontale verbindingen ontstaan.

Stap 3: Maak verticale verbindingen met de volgende rij.

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

Stap 4: Ga naar de volgende rij

• Behoud de verticale verbindingen door dezelfde set-ID toe te wijzen aan de corresponderende cellen eronder.
• Wijs nieuwe set-ID's toe aan alle cellen waaraan nog geen set-ID is toegewezen.

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

• Ga door met de verwerking, rij voor rij.

Stap 6: Verwerk de laatste rij

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

Verder lezen

Als je dit bericht leuk vond, vind je deze suggesties misschien ook interessant:

• Groeiende boom algoritme doolhofgenerator
• Wilson's algoritme doolhofgenerator
• Generator voor jacht- en doodsdoolhoven