Rekursiewe Backtracker Maze Generator

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

'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 backtracker-algoritme is 'n diepte-eerste soekmetode om perfekte doolhowe te genereer (doolhofe sonder lusse en 'n enkele pad tussen enige twee punte). Dit is eenvoudig, doeltreffend en produseer visueel aantreklike doolhowe met lang, kronkelende gange.

Ten spyte van sy naam, hoef dit nie noodwendig met behulp van rekursie geïmplementeer te word nie. Dit word dikwels in 'n iteratiewe benadering geïmplementeer deur 'n LIFO-tou (dws 'n stapel) te gebruik. Vir baie groot doolhowe sal die gebruik van rekursie meer geneig wees tot oorloop van oproepstapel, afhangende van programmeertaal en beskikbare geheue. 'n LIFO-tou kan makliker aangepas word om groot hoeveelhede data te hanteer, selfs om die tou op skyf of in 'n databasis te hou indien 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 naburige selle wat nog nie besoek is nie.
   • As daar ten minste een onbesoekte buurman bestaan:
     • Kies lukraak een van die onbesoekte bure.
     • Verwyder die muur tussen die huidige sel en die gekose buurman.
     • Skuif na die gekose buurman en merk dit as besoek.
     • Druk die huidige sel op die stapel.
   • Indien geen onbesoekte bure bestaan ​​nie:
     • Terugspoor deur die laaste sel uit die stapel te laat spring.
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 hardloop en net stop wanneer jy die besliste eindpunt tref, sal die stapel die oplossing vir die doolhof bevat.

Ek het eintlik twee weergawes van hierdie algoritme in die spel op hierdie webwerf: 'n LIFO-tou-gebaseerde een vir die generering van doolhowe op hierdie bladsy en 'n rekursie-gebaseerde een om doolhowe op te los, ook doolhowe wat deur ander algoritmes gegenereer word (dit is 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, óf kon vir albei gewerk het ;-)