Miklix

Artan Ağac Alqoritmi Maze Generatoru

Nəşr olundu: 16 fevral 2025 at 21:59:30 UTC
Son yeniləmə: 6 mart 2025 at 10:01:16 UTC

Mükəmməl mazut yaratmaq üçün Growing Tree alqoritminin köməyi ilə Maze generatoru. Bu alqoritm Hunt and Kill alqoritminə bənzər mazutlar generasiya etməyə meyllidir, lakin bir qədər fərqli tipik həlllə.

Bu səhifə mümkün qədər çox insan üçün əlçatan olması üçün ingilis dilindən maşın tərcümə edilib. Təəssüf ki, maşın tərcüməsi hələ mükəmməl texnologiya deyil, ona görə də səhvlər baş verə bilər. İstəyirsinizsə, orijinal ingilis versiyasına buradan baxa bilərsiniz:

Growing Tree Algorithm Maze Generator

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.


Yeni labirint yaradın








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.

Bluesky-də paylaşınFacebookda paylaşLinkedIn-də paylaşınTumblr-da paylaşınX-də paylaşınLinkedIn-də paylaşınPinterest-də Pin

Mikkel Bang Christensen

Müəllif haqqında

Mikkel Bang Christensen
Mikkel miklix.com saytının yaradıcısı və sahibidir. O, peşəkar kompüter proqramçısı/proqram təminatı tərtibatçısı kimi 20 ildən artıq təcrübəyə malikdir və hazırda böyük Avropa İT korporasiyasında tam iş günü işləyir. Bloq yazmayanda o, boş vaxtını geniş çeşidli maraqlara, hobbilərə və fəaliyyətlərə sərf edir ki, bu da müəyyən dərəcədə bu veb-saytda əhatə olunan müxtəlif mövzularda əks oluna bilər.