Eller se Algoritme Maze Generator

Eller se algoritme is 'n doolhofgenereringsalgoritme wat doeltreffend perfekte doolhowe (doolhowe sonder lusse en 'n enkele pad tussen enige twee punte) produseer deur 'n ry-vir-ry-benadering te gebruik. Dit produseer doolhowe soortgelyk aan Kruskal se algoritme, maar dit doen dit deur slegs een ry op 'n slag te genereer, sonder die behoefte om die hele doolhof in die geheue te stoor. Dit maak dit nuttig vir die generering van baie groot doolhowe op baie beperkte stelsels en vir prosedurele inhoudgenerering.

'n Volmaakte doolhof is 'n doolhof waarin daar presies een pad van enige punt in die doolhof na enige ander punt is. Dit beteken dat jy nie uiteindelik in sirkels kan rondloop nie, maar jy sal dikwels doodloopstrate teëkom, wat jou dwing om om te draai en terug te gaan.

Die doolhofkaarte wat hier gegenereer word, bevat 'n verstekweergawe sonder enige begin- en eindposisies, so jy kan dit self besluit: daar sal 'n oplossing wees van enige punt in die doolhof na enige ander punt. As jy inspirasie wil hê, kan jy 'n voorgestelde begin- en eindposisie aktiveer - en selfs die oplossing tussen die twee sien.

Oor Eller se Algoritme

Eller se Algoritme is deur David Eller bekendgestel.

Die algoritme is opmerklik vir sy doeltreffende ry-vir-ry-benadering tot doolhofgenerering, wat dit ideaal maak vir oneindige doolhowe of doolhowe wat intyds gegenereer word. Dit word algemeen aangehaal in prosedurele inhoudgenerering en doolhofgenereringliteratuur, maar ek kon nie primêre bronne vind wat die oorspronklike publikasie daarvan uiteensit nie.

Hoe Eller se Algoritme Werk vir Doolhofgenerering

Eller se algoritme verwerk een ry op 'n slag, en onderhou en wysig stelle gekoppelde selle. Dit verseker konnektiwiteit terwyl lusse vermy word, en dit brei die doolhof doeltreffend afwaarts uit.

Dit kan teoreties gebruik word om oneindige doolhowe te genereer, maar om te verseker dat die gegenereerde doolhof eintlik oplosbaar is, is dit nodig om op 'n stadium na die "laaste ry"-logika oor te skakel om die doolhof te voltooi.

Stap 1: Inisialiseer die eerste ry

• Ken elke sel in die ry 'n unieke stel-ID toe.

Stap 2: Verbind 'n paar aangrensende selle horisontaal

• Voeg aangrensende selle lukraak saam deur hulle op dieselfde stel-ID te stel. Dit verseker dat daar horisontale gange is.

Stap 3: Skep vertikale verbindings na die volgende ry

• Vir elke stel wat in die ry verskyn, moet ten minste een sel afwaarts verbind (om konnektiwiteit te verseker).
• Kies lukraak een of meer selle uit elke stel om aan die volgende ry te koppel.

Stap 4: Beweeg na die volgende ry

• Dra die vertikale verbindings vorentoe deur dieselfde stel-ID aan die ooreenstemmende selle hieronder toe te ken.
• Ken nuwe stel-ID's toe aan enige ontoegekende selle.

Stap 5: Herhaal stappe 2–4 totdat die laaste ry bereik is

• Gaan voort met die verwerking ry vir ry.

Stap 6: Verwerk die laaste ry

• Maak seker dat alle selle in die laaste ry aan dieselfde stel behoort deur enige oorblywende afsonderlike stelle saam te voeg.

Verdere Leeswerk

As jy hierdie plasing geniet het, sal jy dalk ook van hierdie voorstelle hou:

• Jag en maak doolhof kragopwekker dood
• Kruskal se algoritme doolhof kragopwekker
• Rekursiewe Backtracker Maze Generator