Eller se Algoritme Maze Generator

Eller se algoritme is 'n doolhofgenerasie-algoritme wat doeltreffend perfekte doolhowe produseer (doolhowe sonder lusse en 'n enkele pad tussen enige twee punte) deur 'n ry-vir-ry benadering te gebruik. Dit produseer doolhowe soortgelyk aan Kruskal se algoritme, maar dit doen dit deur net een ry op 'n slag te genereer, sonder dat dit nodig is 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 die generering van prosedurele inhoud.

'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 opvallend 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 doolhofgenerasieliteratuur, maar ek kon nie primêre bronne vind wat die oorspronklike publikasie daarvan uiteensit nie.

Hoe Eller se algoritme werk vir Maze Generation

Eller se algoritme verwerk een ry op 'n slag, 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 werklik oplosbaar is, is dit nodig om een ​​of ander tyd na die "finale 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: Sluit 'n paar aangrensende selle horisontaal aan

• Voeg lukraak aangrensende selle 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: Skuif na die volgende ry

• Dra die vertikale verbindings aan 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 om ry vir ry te verwerk.

Stap 6: Verwerk die finale ry

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