Jag en maak doolhof kragopwekker dood
Gepubliseer: 16 Februarie 2025 om 20:58:58 UTC
Doolhofgenerator wat die Hunt and Kill-algoritme gebruik om 'n perfekte doolhof te skep. Hierdie algoritme is soortgelyk aan die Rekursiewe Backtracker, maar is geneig om doolhowe te genereer met ietwat minder lang, kronkelende gange.Hunt and Kill Maze Generator
Die Hunt and Kill-algoritme is regtig 'n gewysigde weergawe van die Rekursiewe Backtracker. Die wysiging bestaan uit stelselmatige skandering (of "jag") vir 'n nuwe sel om voort te gaan vanaf wanneer dit nie verder kan gaan nie, in teenstelling met 'n ware rekursiewe soektog, wat altyd sal teruggaan 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, net deur te kies om meer gereeld of volgens spesifieke reëls die "jag"-modus te betree. Die weergawe wat hier geïmplementeer word, gaan slegs in die "jag"-modus wanneer dit nie verder van die huidige sel af 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 Hunt and Kill-algoritme is 'n eenvoudige dog effektiewe metode om doolhowe te genereer. Dit is ietwat soortgelyk aan 'n diepte-eerste soektog (dws die Rekursiewe Backtracker-algoritme), behalwe as wanneer dit nie verder van die huidige posisie af kan gaan nie, skandeer dit stelselmatig (of "jag") oor die doolhof om 'n nuwe sel te vind om van voort te gaan. Die algoritme bestaan uit twee hooffases: stap en jag.
Hoe die jag-en-dood-algoritme werk vir doolhofgenerasie
Stap 1: Begin by 'n ewekansige sel
- Soek 'n ewekansige sel in die rooster en merk dit as besoek.
Stap 2: Loopfase (ewekansige stap)
- 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).
- Soek die eerste onbesoekte sel wat ten minste een besoekte buurman het.
- Koppel daardie sel aan 'n besoekte buurman om die loopfase te hervat.
- Herhaal totdat alle selle besoek is.