Uilsonun Alqoritmi Maze Generatoru

Wilson alqoritmi, labirint yaratmaq üçün vahid uzanan ağaclar yaradan bir dövrə ilə silinən təsadüfi gəzinti metodudur. Bu o deməkdir ki, müəyyən bir ölçülü bütün mümkün labirintlərin eyni dərəcədə yaranma ehtimalı var və bu da onu qərəzsiz labirint generasiya texnikasına çevirir. Wilson alqoritmi eyni xüsusiyyətlərə malik labirintlər yaratdığı üçün Aldous-Broder alqoritminin təkmilləşdirilmiş versiyası hesab edilə bilər, lakin daha sürətli işləyir, ona görə də burada Aldous-Broder alqoritmini tətbiq etməyə əziyyət çəkmədim.

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.

Vilson alqoritmi haqqında

Wilsonun ilgəklə silinmiş təsadüfi divardan istifadə edərək vahid uzanan ağaclar yaratmaq alqoritmi David Bruce Wilson tərəfindən yaradılmışdır.

Vilson bu alqoritmi ilk dəfə 1996-cı ildə ehtimal nəzəriyyəsində təsadüfi uzanan ağaclar və Markov zəncirlərini araşdırarkən təqdim etmişdir. Onun işi əsasən riyaziyyat və statistik fizika sahəsində olsa da, alqoritm o vaxtdan bəri mükəmməl vahid labirintlər yaratmaq qabiliyyətinə görə labirintlərin yaradılması üçün geniş istifadə olunur.

Wilson Alqoritmi Labirint Yaradılması üçün Necə İşləyir

Vilsonun alqoritmi, təsadüfi gəzintilərdən istifadə edərək ziyarət edilməmiş hücrələrdən təkrarlanan şəkildə yollar kəsərək son labirintdə heç bir döngə olmadan tam bir əlaqənin olmasını təmin edir.

Addım 1: Başlanğıclaşdırın

• Divarlarla dolu bir torla başlayın.
• Bütün mümkün keçid hüceyrələrinin siyahısını təyin edin.

Addım 2: Təsadüfi Başlanğıc Hücrə Seçin

• İstənilən təsadüfi xananı seçin və onu ziyarət edilmiş kimi qeyd edin. Bu, generasiya zamanı labirintdə başlanğıc nöqtəsi kimi xidmət edir.

Addım 3: Döngü Silmə ilə Təsadüfi Gəzinti

• Ziyarət olunmamış bir hücrə seçin və təsadüfi bir gəzintiyə başlayın (təsadüfi istiqamətlərdə hərəkət edin).
• Əgər gediş artıq ziyarət edilmiş bir xanaya çatırsa, yoldakı bütün döngələri silin.
• Gəzinti ziyarət edilən bölgəyə birləşdikdən sonra, yoldakı bütün xanaları ziyarət edilən kimi qeyd edin.

Addım 4: Bütün hücrələr ziyarət olunana qədər təkrarlayın:

• Hər bir hücrə labirintdə olana qədər ziyarət edilməmiş hücrələri seçməyə və təsadüfi gəzintilər etməyə davam edin.

Əlavə Oxu

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

• Kruskalın Alqoritmi Maze Generatoru
• Artan Ağac Alqoritmi Maze Generatoru
• Rekursiv Backtracker labirent generatoru