Artan Ağac Alqoritmi Maze Generatoru

Böyüyən Ağac alqoritmi maraqlıdır, çünki generasiya zamanı növbəti xananın necə seçilməsindən asılı olaraq bir neçə digər alqoritmin davranışını təqlid edə bilər. Bu səhifədəki tətbiqdə genişliyə əsaslanan, növbəyə bənzər bir yanaşma istifadə olunur.

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.

Böyüyən Ağac Alqoritmi Haqqında

Böyüyən Ağac alqoritmi mükəmməl labirintlər yaratmaq üçün çevik və güclü bir metoddur. Alqoritm maraqlıdır, çünki emal üçün növbəti xananı necə seçməyinizdən asılı olaraq Primin alqoritmi, rekursiv geri izləmə və rekursiv bölmə kimi bir neçə digər labirint generasiya alqoritmlərinin davranışını təqlid edə bilər.

Böyüyən Ağac Alqoritmi Necə İşləyir

Addım 1: Başlanğıc

• Baxılmamış hücrələrdən ibarət bir şəbəkə ilə başlayın.
• Təsadüfi bir başlanğıc xanası seçin və siyahıya əlavə edin.

Addım 2: Labirint Yaratma Döngəsi

• Xana siyahısı boş deyilsə: Müəyyən bir strategiyaya əsasən siyahıdan bir xana seçin (aşağıda izah olunur). Seçilmiş xanadan ziyarət edilməmiş qonşularından birinə keçid oyun (təsadüfi seçilir). Qonşunu siyahıya əlavə edin, çünki o, artıq labirintdədir. Seçilmiş xanada ziyarət edilməmiş qonşu yoxdursa, onu siyahıdan silin.

Addım 3: Xitam

• Alqoritm siyahıda artıq xana qalmadıqda başa çatır, yəni bütün labirint yonulmuş olur.

Hüceyrə Seçimi Strategiyaları (Alqoritmin Çevikliyi)

Böyüyən Ağac alqoritminin əsas xüsusiyyəti, hansı hüceyrəni növbəti dəfə emal edəcəyinizi seçməyinizdir. Bu seçim labirint görünüşünə ciddi təsir göstərir:

Ən Yeni Hüceyrə (Stekə bənzər Davranış) – Rekursiv Geri İzləyici:

• Həmişə ən son əlavə edilmiş xananı seçin.
• Çoxlu çıxılmaz ucları olan uzun, əyri-üyrü dəhlizlər yaradır (dərinliyə önəm verən axtarış labirinti kimi).
• Labirintlərin uzun keçidləri olur və həlli asandır.

Təsadüfi Hüceyrə (Təsadüfi Prim Alqoritmi):

• Hər dəfə siyahıdan təsadüfi bir xana seçin.
• Mürəkkəb, dolaşıq yollarla daha bərabər paylanmış bir labirint yaradır.
• Daha az uzun dəhlizlər və daha çox budaqlanma.

Ən Köhnə Hüceyrə (Növbəyəbənzər Davranış):

• Həmişə siyahıdakı ən köhnə xananı seçin.
• Daha vahid yayılma ilə labirintlər yaradır, məsələn, genişliyə əsaslanan axtarış nümunəsi.
• Sıx əlaqələri olan qısa, kollu dəhlizlər.
• (Bu, burada tətbiq olunan versiyadır)

Hibrid yanaşmalar:

Müxtəlif labirint xüsusiyyətləri üçün strategiyaları birləşdirin. Məsələn:

• 90% ən yeni, 10% təsadüfi: Əsasən rekursiv geri izləmə labirintinə bənzəyir, lakin uzun dəhlizləri parçalayan bəzən budaqları var.
• 50% ən yeni, 50% ən köhnə: Uzun dəhlizləri kollu bitkilərlə tarazlaşdırır.

Əlavə Oxu

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

• Kruskalın Alqoritmi Maze Generatoru
• Ellerin Alqoritmi Maze Generatoru
• Uilsonun Alqoritmi Maze Generatoru