Groeiende boom algoritme doolhof kragopwekker

Die Growing Tree-algoritme is interessant, want dit kan die gedrag van verskeie ander algoritmes naboots, afhangende van hoe die volgende sel tydens generering gekies word. Die implementering op hierdie bladsy gebruik 'n breedte-eerste, touagtige benadering.

'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 die groeiende boomalgoritme

Die Growing Tree-algoritme is 'n buigsame en kragtige metode om perfekte doolhowe te genereer. Die algoritme is interessant omdat dit die gedrag van verskeie ander doolhofgenereringsalgoritmes kan naboots, soos Prim se algoritme, rekursiewe terugsporing en rekursiewe verdeling, afhangende van hoe jy die volgende sel kies om te verwerk.

Hoe die groeiende boomalgoritme werk

Stap 1: Inisialisering

• Begin met 'n rooster van onbesoekte selle.
• Kies 'n ewekansige beginsel en voeg dit by 'n lys.

Stap 2: Doolhof-generasielus

• Terwyl die sellys nie leeg is nie:
  • Kies 'n sel uit die lys gebaseer op 'n spesifieke strategie (hieronder verduidelik).
  • Kerf 'n gang van die geselekteerde sel na een van sy onbesoekte bure (lukraak gekies).
  • Voeg die buurman by die lys aangesien dit nou deel van die doolhof is.
  • As die geselekteerde sel geen onbesoekte bure het nie, verwyder dit uit die lys.

Stap 3: Beëindiging

• Die algoritme eindig wanneer daar nie meer selle in die lys is nie, wat beteken dat die hele doolhof gekerf is.

Selseleksiestrategieë (buigsaamheid van die algoritme)

Die bepalende kenmerk van die Growing Tree-algoritme is hoe jy kies watter sel om volgende te verwerk. Hierdie keuse beïnvloed die doolhof se voorkoms dramaties:

Nuutste sel (stapelagtige gedrag) – Rekursiewe Backtracker:

• Kies altyd die sel wat onlangs bygevoeg is.
• Produseer lang, kronkelende gange met baie doodloopstrate (soos 'n diepte-eerste soekdoolhof).
• Doolhowe is geneig om lang gange te hê en is maklik om op te los.

Ewekansige sel (gerandomiseerde Prim se algoritme):

• Kies elke keer 'n ewekansige sel uit die lys.
• Skep 'n meer eweredig verspreide doolhof met komplekse, verstrengelde paadjies.
• Minder lang gange en meer vertakking.

Oudste sel (touagtige gedrag):

• Kies altyd die oudste sel in die lys.
• Genereer doolhowe met 'n meer eenvormige verspreiding, soos 'n breedte-eerste soekpatroon.
• Kort, bosagtige gange met digte verbindings.
• (Dit is die weergawe wat hier geïmplementeer word)

Hibriede benaderings:

Kombineer strategieë vir uiteenlopende doolhofeienskappe. Byvoorbeeld:

• 90% nuutste, 10% lukraak: Lyk meestal soos 'n rekursiewe backtracker-doolhof, maar met af en toe takke wat lang gange opbreek.
• 50% nuutste, 50% oudste: Balanseer lang gange met bosagtige groei.