Rekursīvs Backtracker labirinta ģenerators

Rekursīvais atpakaļizsekotāja algoritms patiesībā ir vispārējas nozīmes dziļuma meklēšana. Izmantojot to labirintu ģenerēšanai, tas tiek nedaudz modificēts, lai ceļš tiktu izvēlēts nejauši, savukārt, ja to izmanto faktiskās meklēšanas nolūkos, parasti tiek meklēts katrā līmenī lineārā secībā. Tas parasti rada labirintus ar gariem, līkumotiem koridoriem un ļoti garu, līkumotu 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ļizsekotāja algoritms ir dziļumā meklēšanas metode perfektu labirintu (labirintu bez cilpām un viena ceļa starp jebkuriem diviem punktiem) ģenerēšanai. Tas ir vienkāršs, efektīvs un rada vizuāli pievilcīgus labirintus ar gariem, līkumotiem koridoriem.

Neskatoties uz nosaukumu, tas nav obligāti jāievieš, izmantojot rekursiju. To bieži ievieš iteratīvā pieejā, izmantojot LIFO rindu (t. i., steku). Ļoti lieliem labirintiem rekursijas izmantošana, visticamāk, izraisīs izsaukumu steka pārpildi atkarībā no programmēšanas valodas un pieejamās atmiņas. LIFO rindu var vieglāk pielāgot lielu datu apjomu apstrādei, pat saglabājot rindu diskā vai datubāzē, ja pieejamā atmiņa nav pietiekama.

Kā tas darbojas

Algoritms darbojas, izmantojot uz steku balstītu dziļuma meklēšanas pieeju. Šeit ir soli pa solim sniegts apraksts:

1. Izvēlieties sākuma šūnu un atzīmējiet to kā apmeklētu.
2. Kamēr ir neapmeklētas šūnas: Apskatiet blakus esošās šūnas, kuras vēl nav apmeklētas. Ja pastāv vismaz viena neapmeklēta kaimiņš: Nejauši izvēlieties vienu no neapmeklētajiem kaimiņiem. Noņemiet sienu starp pašreizējo šūnu un izvēlēto kaimiņu. Pārvietojieties uz izvēlēto kaimiņu un atzīmējiet to kā apmeklētu. Ievietojiet pašreizējo šūnu kaudzē. Ja nav neapmeklētu kaimiņu: Atgriezieties, izņemot pēdējo šūnu no kaudzītes.
3. Turpiniet šo procesu, līdz kaudze ir tukša.

Interesants fakts par šo algoritmu ir tas, ka tas darbojas gan kā labirinta ģenerators, gan kā labirinta risinātājs. Ja to palaižat jau ģenerētā labirintā un vienkārši apstājaties, sasniedzot noteikto beigu punktu, kaudzē būs labirinta risinājums.

Man šajā vietnē faktiski ir divas šī algoritma versijas: LIFO rindas versija labirintu ģenerēšanai šajā lapā un rekursijas versija labirintu risināšanai, arī labirintu, ko ģenerē citi algoritmi (tieši tā tiek veidotas kartes ar risinājumiem). Divu dažādu versiju esamība ir paredzēta tikai sportam, jo esmu nūģis, kuram tas šķiet interesanti, jebkura no tām varētu derēt abām ;-)

Papildu lasāmviela

Ja jums patika šī ziņa, jums varētu patikt arī šie ieteikumi:

• Augošu koku algoritma labirinta ģenerators
• Ellera algoritma labirinta ģenerators
• Kruskal algoritma labirinta ģenerators