Rekursīvs Backtracker labirinta ģenerators

Rekursīvais atpakaļsekošanas algoritms patiešām ir vispārēja mērķa dziļuma meklēšana. Ja to izmantoja labirinta ģenerēšanai, tas nedaudz mainījās, lai nejauši izvēlētos ceļu, turpretim, ja to izmanto faktiskai meklēšanai, parasti tiek meklēts katrs līmenis lineārā secībā. Tas mēdz radīt labirintus ar gariem, līkumotiem koridoriem un ļoti garu, vērpjošu risinājumu.

Ideāls labirints ir labirints, kurā ir tieši viens ceļš no jebkura labirinta punkta uz jebkuru citu punktu. Tas nozīmē, ka jūs nevarat nonākt apļveida ceļos, bet bieži sastapsieties ar strupceļiem, kas liks jums apgriezties un atgriezties atpakaļ.

Šeit ģenerētajās labirinta kartēs ir noklusējuma versija bez sākuma un beigu pozīcijām, lai jūs paši varētu tās noteikt: būs risinājums no jebkura labirinta punkta uz jebkuru citu punktu. Ja vēlaties iedvesmu, varat ieslēgt ieteikto sākuma un beigu pozīciju un pat apskatīt risinājumu starp šīm divām pozīcijām.

Rekursīvais atpakaļsekošanas algoritms ir pirmā dziļuma meklēšanas metode ideālu labirintu ģenerēšanai (labirintus bez cilpām un vienu ceļu starp jebkuriem diviem punktiem). Tas ir vienkāršs, efektīvs un rada vizuāli pievilcīgus labirintus ar gariem, līkumotiem koridoriem.

Neskatoties uz tā nosaukumu, tam nav obligāti jābūt ieviestam, izmantojot rekursiju. To bieži īsteno iteratīvā pieejā, izmantojot LIFO rindu (ti, steku). Ļoti lielos labirintos atkarībā no programmēšanas valodas un pieejamās atmiņas, rekursijas izmantošana, visticamāk, izraisīs zvanu steka pārpildīšanu. LIFO rindu var vieglāk pielāgot liela datu apjoma apstrādei, pat saglabājot rindu diskā vai datu bāzē, ja nepietiek pieejamās atmiņas.

Kā tas darbojas

Algoritms darbojas, izmantojot uz steku balstītu dziļuma meklēšanas pieeju. Lūk, pakāpenisks sadalījums:

1. Izvēlieties sākuma šūnu un atzīmējiet to kā apmeklētu.
2. Kamēr ir neapmeklētas šūnas:
   • Paskatieties uz blakus esošajām kamerām, kuras vēl nav apmeklētas.
   • Ja ir vismaz viens neapmeklēts kaimiņš:
     • Nejauši izvēlieties kādu no neapmeklētajiem kaimiņiem.
     • Noņemiet sienu starp pašreizējo šūnu un izvēlēto kaimiņu.
     • Pārejiet pie izvēlētā kaimiņa un atzīmējiet to kā apmeklētu.
     • Nospiediet pašreizējo šūnu uz steku.
   • Ja nav neapmeklētu kaimiņu:
     • Atgriezieties, izvelkot pēdējo šūnu no steka.
3. Turpiniet šo procesu, līdz kaudze ir tukša.

Interesants fakts par šo algoritmu ir tas, ka tas darbojas gan kā labirintu ģenerators, gan kā labirintu risinātājs. Ja palaižat to jau izveidotā labirintā un vienkārši apstājaties, kad sasniedzat nolemto beigu punktu, kaudze saturēs labirinta atrisinājumu.

Man šajā vietnē faktiski ir divas šī algoritma versijas: LIFO rinda, kas balstīta uz labirintu ģenerēšanu šajā lapā, un uz rekursiju balstīta, kas paredzēta labirintu risināšanai, kā arī labirinti, ko ģenerē citi algoritmi (tā tiek veidotas kartes ar risinājumiem). Divas dažādas versijas ir paredzētas tikai sportam, jo ​​es esmu nerds, kuram tas šķiet interesanti, jebkurš varētu būt piemērots abiem ;-)