Jag en maak doolhof kragopwekker dood

Die Jag-en-Dood-algoritme is eintlik 'n aangepaste weergawe van die Rekursiewe Terugspoorder. Die wysiging bestaan uit sistematiese skandering (of "jag") vir 'n nuwe sel om van te voortgaan wanneer dit nie verder kan gaan nie, in teenstelling met 'n ware rekursiewe soektog, wat altyd terug sal gaan na die vorige sel op die stapel.

As gevolg hiervan kan hierdie algoritme maklik aangepas word om doolhowe met verskillende voorkoms en gevoel te genereer, deur bloot te kies om meer gereeld na "jag"-modus te gaan of volgens spesifieke reëls. Die weergawe wat hier geïmplementeer word, gaan slegs na "jag"-modus wanneer dit nie verder van die huidige sel kan gaan nie.

'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 Jag-en-Dood-algoritme

Die Jag-en-Doodmaak-algoritme is 'n eenvoudige maar effektiewe metode om doolhowe te genereer. Dit is ietwat soortgelyk aan 'n diepte-eerste soektog (dws die Rekursiewe Terugspoorder-algoritme), behalwe dat wanneer dit nie verder van die huidige posisie kan gaan nie, dit sistematies skandeer (of "jag") oor die doolhof om 'n nuwe sel te vind om van te voortgaan. Die algoritme bestaan uit twee hooffases: loop en jag.

Hoe die Jag-en-Doodmaak-algoritme werk vir doolhofgenerering

Stap 1: Begin by 'n ewekansige sel

• Vind 'n ewekansige sel in die rooster en merk dit as besoek.

Stap 2: Loopfase (Willekeurige Loop)

• Kies 'n ewekansige onbesoekte buurman.
• Beweeg na daardie buurman, merk dit as besoek en kerf 'n pad tussen die vorige en nuwe sel.
• Herhaal totdat daar geen onbesoekte bure oor is nie.

Stap 3: Jagfase (Terugspoor via skandering)

• Skandeer die rooster ry vir ry (of kolom vir kolom).
• Vind die eerste onbesoekte sel wat ten minste een besoekte buurman het.
• Verbind daardie sel met 'n besoekte buurman om die loopfase te hervat.
• Herhaal totdat alle selle besoek is.

Verdere Leeswerk

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

• Groeiende boom algoritme doolhof kragopwekker
• Kruskal se algoritme doolhof kragopwekker
• Rekursiewe Backtracker Maze Generator