Miklix

Groeiende boom algoritme doolhof kragopwekker

Gepubliseer: 16 Februarie 2025 om 21:57:37 UTC
Laas opgedateer: 06 Maart 2025 om 09:59:44 UTC

Doolhofgenerator wat die Growing Tree-algoritme gebruik om 'n perfekte doolhof te skep. Hierdie algoritme is geneig om doolhowe soortgelyk aan die Hunt and Kill-algoritme te genereer, maar met 'n ietwat ander tipiese oplossing.

Hierdie bladsy is masjienvertaal uit Engels om dit vir soveel mense moontlik toeganklik te maak. Ongelukkig is masjienvertaling nog nie 'n volmaakte tegnologie nie, dus kan foute voorkom. As jy verkies, kan jy die oorspronklike Engelse weergawe hier sien:

Growing Tree Algorithm Maze Generator

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.


Genereer nuwe doolhof








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.

Deel op BlueskyDeel op FacebookDeel op LinkedInDeel op TumblrDeel op XDeel op LinkedInSpeld op Pinterest

Mikkel Bang Christensen

Oor die skrywer

Mikkel Bang Christensen
Mikkel is die skepper en eienaar van miklix.com. Hy het meer as 20 jaar ondervinding as 'n professionele rekenaarprogrammeerder/sagteware-ontwikkelaar en is tans voltyds in diens van 'n groot Europese IT-korporasie. Wanneer hy nie blog nie, spandeer hy sy vrye tyd aan 'n groot verskeidenheid belangstellings, stokperdjies en aktiwiteite, wat tot 'n mate weerspieël kan word in die verskeidenheid onderwerpe wat op hierdie webwerf gedek word.