Tekrarlayan Geri İzleme Labirent Oluşturucu

Tekrarlayan geri izleme algoritması aslında genel amaçlı bir derinlik öncelikli aramadır. Labirent oluşturma için kullanıldığında, yolu rastgele seçmek için hafifçe değiştirilirken, gerçek arama amaçları için kullanıldığında, kişi genellikle her seviyeyi doğrusal sırayla arar. Uzun, dolambaçlı koridorlara ve çok uzun, kıvrımlı bir çözüme sahip labirentler üretme eğilimindedir.

Mükemmel bir labirent, labirentteki herhangi bir noktadan diğer herhangi bir noktaya tam olarak tek bir yolun olduğu bir labirenttir. Bu, daireler çizerek ilerleyemeyeceğiniz, ancak sık sık çıkmaz sokaklarla karşılaşacağınız ve sizi geri dönmeye zorlayacağınız anlamına gelir.

Burada oluşturulan labirent haritaları, herhangi bir başlangıç ve bitiş konumu olmayan varsayılan bir sürüm içerir, böylece bunlara kendiniz karar verebilirsiniz: labirentin herhangi bir noktasından başka bir noktaya bir çözüm olacaktır. İlham almak isterseniz, önerilen bir başlangıç ve bitiş konumunu etkinleştirebilir ve hatta ikisi arasındaki çözümü görebilirsiniz.

Tekrarlayan geri izleme algoritması, mükemmel labirentler (herhangi iki nokta arasında döngüleri olmayan ve tek bir yolu olan labirentler) üretmek için derinlemesine arama yöntemidir. Basit, verimlidir ve uzun, dolambaçlı koridorlara sahip görsel olarak çekici labirentler üretir.

Adına rağmen, mutlaka yineleme kullanılarak uygulanması gerekmez. Genellikle bir LIFO kuyruğu (yani bir yığın) kullanılarak yinelemeli bir yaklaşımla uygulanır. Çok büyük labirentler için, programlama diline ve kullanılabilir belleğe bağlı olarak yineleme kullanmanın çağrı yığını taşmasına neden olma olasılığı daha yüksektir. Bir LIFO kuyruğu, kullanılabilir bellek yetersizse kuyruğu diskte veya bir veritabanında tutarak bile büyük miktarda veriyi işlemek için daha kolay uyarlanabilir.

Nasıl Çalışır

Algoritma, yığın tabanlı derinlemesine arama yaklaşımını kullanarak çalışır. İşte adım adım dökümü:

1. Başlangıç hücresini seçin ve ziyaret edilmiş olarak işaretleyin.
2. Ziyaret edilmemiş hücreler varken:
   • Henüz ziyaret edilmemiş komşu hücrelere bakın.
   • En azından bir ziyaret edilmemiş komşu varsa:
     • Ziyaret etmediğiniz komşularınızdan birini rastgele seçin.
     • Mevcut hücre ile seçilen komşu arasındaki duvarı kaldırın.
     • Seçtiğiniz komşuya gidin ve ziyaret edildi olarak işaretleyin.
     • Mevcut hücreyi yığına it.
   • Ziyaret edilmemiş komşu yoksa:
     • Yığındaki son hücreyi çıkararak geri dön.
3. Yığın boşalana kadar bu işlemi sürdürün.

Bu algoritma hakkında ilginç bir gerçek, hem bir labirent oluşturucu hem de bir labirent çözücü olarak çalışmasıdır. Bunu önceden oluşturulmuş bir labirentte çalıştırırsanız ve kararlaştırılan son noktaya ulaştığınızda durursanız, yığın labirentin çözümünü içerecektir.

Aslında bu algoritmanın bu sitede iki versiyonu var: bu sayfadaki labirentleri oluşturmak için LIFO kuyruğu tabanlı bir versiyon ve labirentleri çözmek için yineleme tabanlı bir versiyon, ayrıca diğer algoritmalar tarafından oluşturulan labirentler (çözümleri olan haritalar bu şekilde yapılır). İki farklı versiyona sahip olmak sadece spor amaçlıdır çünkü ben bunu ilginç bulan bir inekim, her ikisi için de işe yarayabilirdi ;-)