Rekursiewe Backtracker Maze Generator

Die rekursiewe terugspoor-algoritme is eintlik 'n algemene diepte-eerste soektog. Wanneer dit vir doolhofgenerering gebruik word, word dit effens aangepas om die pad lukraak te kies, terwyl 'n mens tipies elke vlak in lineêre volgorde sou deursoek as dit vir werklike soekdoeleindes gebruik word. Dit is geneig om doolhowe met lang, kronkelende gange en 'n baie lang, kronkelende oplossing te produseer.

'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.

Die rekursiewe terugspooralgoritme is 'n diepte-eerste soekmetode vir die generering van perfekte doolhowe (doolhowe sonder lusse en 'n enkele pad tussen enige twee punte). Dit is eenvoudig, doeltreffend en lewer visueel aantreklike doolhowe met lang, kronkelende gange.

Ten spyte van die naam, hoef dit nie noodwendig met rekursie geïmplementeer te word nie. Dit word dikwels in 'n iteratiewe benadering geïmplementeer deur 'n LIFO-waglys (d.w.s. 'n stapel) te gebruik. Vir baie groot doolhowe is die gebruik van rekursie meer geneig om tot oproepstapeloorloop te lei, afhangende van die programmeertaal en beskikbare geheue. 'n LIFO-waglys kan makliker aangepas word om groot hoeveelhede data te hanteer, selfs om die waglys op skyf of in 'n databasis te hou as die beskikbare geheue onvoldoende is.

Hoe dit werk

Die algoritme werk met behulp van 'n stapelgebaseerde diepte-eerste soekbenadering. Hier is die stap-vir-stap uiteensetting:

1. Kies 'n beginsel en merk dit as besoek.
2. Terwyl daar onbesoekte selle is: Kyk na die aangrensende selle wat nog nie besoek is nie. Indien ten minste een onbesoekte buurman bestaan: Kies lukraak een van die onbesoekte bure. Verwyder die muur tussen die huidige sel en die gekose buurman. Beweeg na die gekose buurman en merk dit as besoek. Stoot die huidige sel op die stapel. Indien geen onbesoekte bure bestaan nie: Gaan terug deur die laaste sel van die stapel te verwyder.
3. Gaan voort met hierdie proses totdat die stapel leeg is.

'n Interessante feit oor hierdie algoritme is dat dit beide as 'n doolhofgenerator en as 'n doolhofoplosser werk. As jy dit op 'n reeds gegenereerde doolhof laat loop en net stop wanneer jy die besluite eindpunt bereik, sal die stapel die oplossing vir die doolhof bevat.

Ek het eintlik twee weergawes van hierdie algoritme in werking op hierdie webwerf: 'n LIFO-waglys-gebaseerde een vir die generering van doolhowe op hierdie bladsy en 'n rekursie-gebaseerde een vir die oplos van doolhowe, ook doolhowe wat deur ander algoritmes gegenereer word (dis hoe die kaarte met die oplossings gemaak word). Om twee verskillende weergawes te hê is net vir sport, want ek is 'n nerd wat dit interessant vind, enigeen kon vir albei gewerk het ;-)

Verdere Leeswerk

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

• Jag en maak doolhof kragopwekker dood
• Groeiende boom algoritme doolhof kragopwekker
• Wilson se algoritme doolhof kragopwekker