Rekursiv Backtracker labirent generatoru

Rekursiv geri izləmə alqoritmi əslində ümumi məqsədli dərinliyə əsaslanan axtarışdır. Labirint yaratmaq üçün istifadə edildikdə, təsadüfi yol seçmək üçün bir az dəyişdirilir, halbuki faktiki axtarış məqsədləri üçün istifadə edildikdə, adətən hər səviyyəni xətti ardıcıllıqla axtarmaq lazımdır. Uzun, dolama dəhlizləri və çox uzun, dolama həlli olan labirintlər yaratmağa meyllidir.

Mükəmməl bir labirint, labirintdəki hər hansı bir nöqtədən hər hansı digər nöqtəyə tam olaraq bir yolun olduğu labirintdir. Bu o deməkdir ki, siz dövrələrə girə bilməyəcəksiniz, ancaq tez-tez çıxılmaz nöqtələrlə qarşılaşacaqsınız, sizi dönüb geri qayıtmağa məcbur edəcəksiniz.

Burada yaradılan labirint xəritələri heç bir başlanğıc və bitmə mövqeləri olmayan defolt versiyanı ehtiva edir, buna görə də özünüz üçün bunlara qərar verə bilərsiniz: labirintdə istənilən nöqtədən istənilən digər nöqtəyə həll yolu olacaq. Əgər ilham almaq istəyirsinizsə, təklif olunan başlanğıc və bitiş mövqeyini aktivləşdirə və hətta ikisi arasında həll yolu görə bilərsiniz.

Rekursiv geri izləmə alqoritmi mükəmməl labirintlər (döngəsiz və istənilən iki nöqtə arasında tək bir yol olan labirintlər) yaratmaq üçün dərinliyə əsaslanan axtarış metodudur. Sadə, səmərəlidir və uzun, dolama dəhlizləri olan vizual cəhətdən cəlbedici labirintlər yaradır.

Adına baxmayaraq, mütləq rekursiya istifadə edilərək həyata keçirilməli deyil. Çox vaxt LIFO növbəsindən (yəni stekdən) istifadə edərək iterativ yanaşmada həyata keçirilir. Çox böyük labirintlər üçün rekursiyadan istifadə, proqramlaşdırma dilindən və mövcud yaddaşdan asılı olaraq, çağırış stekinin daşmasına səbəb olma ehtimalı daha yüksəkdir. LIFO növbəsi, mövcud yaddaş kifayət deyilsə, növbəni diskdə və ya verilənlər bazasında saxlayaraq belə, böyük həcmdə məlumatların işlənməsi üçün daha asanlıqla uyğunlaşdırıla bilər.

Necə işləyir

Alqoritm yığın əsaslı dərinlik axtarış yanaşmasından istifadə edərək işləyir. Addım-addım təhlili belədir:

1. Başlanğıc xananı seçin və onu ziyarət edilmiş kimi qeyd edin.
2. Ziyarət olunmamış xanalar olsa da: Hələ ziyarət olunmamış qonşu xanalara baxın. Ən azı bir ziyarət olunmamış qonşu varsa: Ziyarət olunmamış qonşulardan birini təsadüfi olaraq seçin. Cari xana ilə seçilmiş qonşu arasındakı divarı çıxarın. Seçilmiş qonşuya keçin və onu ziyarət edilmiş kimi qeyd edin. Cari xananı yığına itələyin. Ziyarət olunmamış qonşu yoxdursa: Yığından sonuncu xananı çıxararaq geri qayıdın.
3. Yığın boş qalana qədər bu prosesi davam etdirin.

Bu alqoritm haqqında maraqlı bir fakt, həm labirint generatoru, həm də labirint həlledicisi kimi işləməsidir. Əgər onu artıq yaradılmış labirintdə işlətsəniz və müəyyən edilmiş son nöqtəyə çatanda dayandırsanız, yığında labirint həlli olacaq.

Əslində bu saytda bu alqoritmin iki versiyası var: bu səhifədə labirintlər yaratmaq üçün LIFO növbə əsaslı versiya və labirintləri, həmçinin digər alqoritmlər tərəfindən yaradılan labirintləri həll etmək üçün rekursiya əsaslı versiya (həllləri olan xəritələr belə hazırlanır). İki fərqli versiyanın olması yalnız idman üçündür, çünki mən maraqlı hesab edən bir nerdəm, hər ikisi üçün də işləyə bilərdi ;-)

Əlavə Oxu

Bu yazı xoşunuza gəldisə, bu təklifləri də bəyənə bilərsiniz:

• Artan Ağac Alqoritmi Maze Generatoru
• Ov və öldür labirent generatoru
• Ellerin Alqoritmi Maze Generatoru