Avla ve Öldür Labirenti Oluşturucu

Avla ve Öldür algoritması aslında Özyinelemeli Geri İzleme algoritmasının değiştirilmiş bir versiyonudur. Değişiklik, gerçek bir özyinelemeli aramanın her zaman yığındaki önceki hücreye geri dönmesinin aksine, daha ileri gidemediğinde devam etmek için sistematik olarak yeni bir hücre taramaktan (veya "avlamaktan") oluşur.

Bu nedenle, bu algoritma, "avlanma" moduna daha sık girmeyi veya belirli kurallara göre girmeyi seçerek, farklı görünüm ve hisse sahip labirentler oluşturmak için kolayca uyarlanabilir. Burada uygulanan sürüm, yalnızca mevcut hücreden daha ileri gidemediğinde "avlanma" moduna girer.

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.

Avla ve Öldür Algoritması Hakkında

Avla ve Öldür algoritması, labirent oluşturmak için basit ama etkili bir yöntemdir. Derinlemesine arama algoritmasına (yani Özyinelemeli Geri İzleme algoritmasına) biraz benzer, ancak mevcut konumdan daha ileri gidemediğinde, ilerlemek için yeni bir hücre bulmak üzere labirent üzerinde sistematik olarak tarama (veya "avlama") yapar. Algoritma iki ana aşamadan oluşur: yürüme ve avlanma.

Labirent Oluşturmada Avla ve Öldür Algoritmasının Çalışma Şekli

Adım 1: Rastgele bir hücreden başlayın

• Izgaradaki rastgele bir hücreyi bulun ve ziyaret edilmiş olarak işaretleyin.

Adım 2: Yürüme Aşaması (Rastgele Yürüyüş)

• Ziyaret edilmemiş bir komşuyu rastgele seçin.
• Komşu hücreye geçin, ziyaret edilmiş olarak işaretleyin ve önceki hücre ile yeni hücre arasında bir yol çizin.
• Ziyaret edilmemiş komşu kalmayana kadar işlemi tekrarlayın.

3. Adım: Avlanma Aşaması (Tarama Yoluyla Geri İzleme)

• Izgara tablosunu satır satır (veya sütun sütun) tarayın.
• En az bir komşusu ziyaret edilmiş olan ilk ziyaret edilmemiş hücreyi bulun.
• Yürüme aşamasına devam etmek için o hücreyi ziyaret edilen bir komşu hücreye bağlayın.
• Tüm hücreler ziyaret edilene kadar işlemi tekrarlayın.

Daha Fazla Okuma

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

• Büyüyen Ağaç Algoritması Labirent Oluşturucu
• Wilson Algoritması Labirent Oluşturucu
• Kruskal Algoritması Labirent Oluşturucu