Tekrarlayan Geri İzleme Labirent Oluşturucu

Özyinelemeli geri izleme algoritması aslında genel amaçlı bir derinlik öncelikli arama algoritmasıdır. Labirent oluşturmada kullanıldığında, yolu rastgele seçmek için biraz değiştirilirken, gerçek arama amaçları için kullanıldığında, genellikle her seviye doğrusal sırayla aranır. 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.

Özyinelemeli geri izleme algoritması, mükemmel labirentler (döngü içermeyen ve herhangi iki nokta arasında tek bir yol bulunan labirentler) oluşturmak için kullanılan derinlemesine arama yöntemidir. Basit, verimli ve uzun, dolambaçlı koridorlara sahip görsel olarak çekici labirentler üretir.

Adına rağmen, mutlaka özyineleme kullanılarak uygulanması gerekmez. Genellikle 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 mevcut belleğe bağlı olarak, özyineleme kullanmak çağrı yığını taşmasına yol açma olasılığını artırır. LIFO kuyruğu, mevcut bellek yetersizse bile, kuyruğu diskte veya bir veritabanında tutarak 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 açıklaması:

1. Başlangıç hücresini seçin ve ziyaret edildi olarak işaretleyin.
2. Henüz ziyaret edilmemiş hücreler varken: Henüz ziyaret edilmemiş komşu hücrelere bakın. En az bir ziyaret edilmemiş komşu varsa: Ziyaret edilmemiş komşulardan birini rastgele seçin. Geçerli hücre ile seçilen komşu arasındaki duvarı kaldırın. Seçilen komşuya gidin ve ziyaret edilmiş olarak işaretleyin. Geçerli hücreyi yığına ekleyin. Ziyaret edilmemiş komşu yoksa: Yığından son hücreyi çıkararak geri dönün.
3. Yığın boşalana kadar bu işleme devam edin.

Bu algoritmayla ilgili ilginç bir gerçek, hem labirent oluşturucu hem de labirent çözücü olarak çalışmasıdır. Zaten oluşturulmuş bir labirent üzerinde çalıştırıp, belirlenen bitiş noktasına ulaştığınızda durdurursanız, yığın labirentin çözümünü içerecektir.

Aslında bu sitede bu algoritmanın iki versiyonunu kullanıyorum: bu sayfadaki labirentleri oluşturmak için LIFO kuyruğuna dayalı bir versiyon ve labirentleri çözmek için özyinelemeye dayalı bir versiyon (çözümlerin bulunduğu haritalar da bu şekilde yapılıyor). İki farklı versiyon kullanmamın tek sebebi, bu konuya ilgi duyan bir bilgisayar meraklısı olmam; ikisi de aynı şekilde çalışabilirdi ;-)

Daha Fazla Okuma

Bu yazıyı beğendiyseniz, şu öneriler de ilginizi çekebilir:

• Büyüyen Ağaç Algoritması Labirent Oluşturucu
• Kruskal Algoritması Labirent Oluşturucu
• Avla ve Öldür Labirenti Oluşturucu