Artan Ağac Alqoritmi Maze Generatoru

Growing Tree alqoritmi maraqlıdır, belə ki, o, nəsil dövründə növbəti hüceyrənin 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ş birinci, növbəyə bənzər yanaşmadan 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

Growing Tree alqoritmi mükəmməl mazutların əmələ gətirdiyi elastik və güclü metoddur. Alqoritm ona görə maraqlıdır ki, o, primin alqoritmi, rekursiv backtracking və recursive division kimi bir neçə digər mazut nəsil alqoritmlərinin davranışını təqlid edə bilər. Bu, proseslərin növbəti hüceyrəni necə seçməyindən asılıdır.

Böyüyən ağac alqoritmi necə işləyir?

1-ci addım: Başlanğıc

• Görünməz hüceyrələrdən ibarət şəbəkə ilə başlayın.
• Təsadüfi başlanğıc hüceyrə seçin və siyahıya əlavə edin.

2-ci addım: Maze Nəsil döngəsi

• Hüceyrə siyahısı boş olmadığı halda:
  • Siyahıdan konkret strategiya əsasında hüceyrə seçin (aşağıda izah olunur).
  • Seçilmiş hüceyrədən onun görünməyən qonşularından birinə keçid oyun (təsadüfi seçilir).
  • Hal-hazırda mazutun bir hissəsi olduğu üçün qonşuları siyahıya əlavə edin.
  • Əgər hüceyrənin heç bir görünməyən qonşusu yoxdursa, onu siyahıdan çıxarın.

3-cü addım: Terminasiya

• Alqoritm siyahıda daha çox hüceyrə olmadıqda bitir, yəni bütün mazut oyulmuşdur.

Hüceyrə seçmə strategiyaları (Alqoritmin elastikliyi)

Growing Tree alqoritminin müəyyənedici xüsusiyyəti növbəti dəfə hansı hüceyrənin işlənməsini necə seçməyinizdir. Bu seçim mazutun xarici görünüşünə kəskin təsir edir:

Ən Yeni Hüceyrə (Stack-like Behavior) – Recursive Backtracker:

• Ən son əlavə olunan hüceyrəni həmişə seçin.
• Bir çox ölü ucu olan uzun, burulmuş koridorlar əmələ gətirir (dərinlik-ilk axtarış mazutu kimi).
• Mazlar adətən uzun keçidlərə malik olur və asanlıqla həll olunur.

Təsadüfi hüceyrə (Randomized Prim's Algorithm):

• Hər dəfə siyahıdan təsadüfi hüceyrə seçin.
• Mürəkkəb, qarışıq cığırlarla daha bərabər paylanmış mazut yaradır.
• Daha az uzun koridor və daha çox filial.

Ən Qədim Hüceyrə (Sıra tipli Davranış):

• Siyahıda həmişə ən qədim hüceyrəni seçin.
• Daha çox vahid yayılma ilə mazutlar yaradır, geniş-birinci axtarış sxemi kimi.
• Sıx əlaqələrə malik qısa, kolluq keçidləri.
• (Burada tətbiq olunan versiya budur)

Hibrid yanaşmalar:

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

• 90% ən yeni, 10% təsadüfi: Əksər hallarda rekursiv geri çəkilən mazuta oxşayır, lakin uzun koridorları parçalayan budaqlarla.
• 50% ən yeni, 50% ən qədim: Uzun koridorları kolluq inkişafla tarazlaşdırır.