Ellerin Alqoritmi Maze Generatoru

Eller alqoritmi, sıra-sıra yanaşmasından istifadə edərək mükəmməl labirintləri (döngəsiz və istənilən iki nöqtə arasında tək bir yol olan labirintlər) səmərəli şəkildə yaradan bir labirint generasiya alqoritmidir. Kruskal alqoritminə bənzər labirintlər yaradır, lakin bunu bütün labirinti yaddaşda saxlamağa ehtiyac olmadan bir anda yalnız bir sıra yaratmaqla edir. Bu, onu çox məhdud sistemlərdə çox böyük labirintlər yaratmaq və prosedur məzmunu yaratmaq üçün faydalı edir.

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.

Eller alqoritmi haqqında

Eller alqoritmi David Eller tərəfindən təqdim edilmişdir.

Alqoritm labirint yaratmaq üçün səmərəli sətir-sətir yanaşması ilə diqqət çəkir və bu da onu sonsuz labirintlər və ya real vaxt rejimində yaradılan labirintlər üçün ideal hala gətirir. Prosedur məzmunu yaratmaq və labirint yaratmaq ədəbiyyatında tez-tez istinad edilir, lakin orijinal nəşrini ətraflı izah edən ilkin mənbələri tapa bilmədim.

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

Ellerin alqoritmi bir sətirdən birini emal edərək, əlaqəli hüceyrələr dəstlərini saxlayır və dəyişdirir. Döngələrdən qaçınarkən əlaqəni təmin edir və labirinti səmərəli şəkildə aşağıya doğru uzadır.

Nəzəri olaraq, sonsuz sayda labirint yaratmaq üçün istifadə edilə bilər, lakin yaradılan labirintin həqiqətən həll edilə biləcəyini təmin etmək üçün labirinti bitirmək üçün bir nöqtədə "son sıra" məntiqinə keçmək lazımdır.

Addım 1: Birinci Sətri Başlat

• Sətirdəki hər bir hücrəyə unikal bir dəst ID təyin edin.

Addım 2: Bəzi qonşu hücrələri üfüqi olaraq birləşdirin

• Eyni dəst ID-sinə təyin edərək qonşu xanaları təsadüfi olaraq birləşdirin. Bu, üfüqi keçidlərin olmasını təmin edir.

Addım 3: Növbəti Sətrə Şaquli Əlaqələr Yaradın

• Sıradakı hər bir dəst üçün ən azı bir hücrə aşağıya doğru birləşməlidir (əlaqəni təmin etmək üçün).
• Növbəti sətrə qoşulmaq üçün hər dəstdən təsadüfi olaraq bir və ya daha çox hücrə seçin.

Addım 4: Növbəti Sətrə Keçin

• Aşağıdakı müvafiq xanalara eyni dəst ID təyin edərək şaquli əlaqələri irəli aparın.
• Təyin olunmamış hücrələrə yeni dəst ID-ləri təyin edin.

Addım 5: Sonuncu sətir çatana qədər 2-4 addımlarını təkrarlayın

• Sıra-sıra emal etməyə davam edin.

Addım 6: Son sıranı emal edin

• Qalan ayrı dəstləri birləşdirərək son sətirdəki bütün xanaların eyni dəstə aid olduğundan əmin olun.

Əlavə Oxu

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

• Ov və öldür labirent generatoru
• Kruskalın Alqoritmi Maze Generatoru
• Rekursiv Backtracker labirent generatoru