Wilson Algoritması Labirent Oluşturucu

Wilson algoritması, labirent oluşturmak için tekdüze yayılma ağaçları üreten, döngü silme özelliğine sahip rastgele yürüyüş yöntemidir. Bu, belirli bir boyuttaki tüm olası labirentlerin eşit olasılıkla oluşturulabileceği anlamına gelir ve bu da onu tarafsız bir labirent oluşturma tekniği yapar. Wilson algoritması, aynı özelliklere sahip labirentler ürettiği için Aldous-Broder algoritmasının geliştirilmiş bir versiyonu olarak düşünülebilir, ancak çok daha hızlı çalışır, bu nedenle Aldous-Broder algoritmasını burada uygulamaya gerek duymadım.

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.

Wilson Algoritması Hakkında

David Bruce Wilson tarafından geliştirilen Wilson algoritması, döngü silme yöntemiyle rastgele bir duvar kullanarak tekdüze yayılma ağaçları üretmeyi amaçlamaktadır.

Wilson bu algoritmayı ilk olarak 1996 yılında olasılık teorisinde rastgele yayılma ağaçları ve Markov zincirleri üzerine araştırma yaparken tanıtmıştır. Çalışmaları esas olarak matematik ve istatistiksel fizik alanında olsa da, algoritma o zamandan beri mükemmel derecede düzgün labirentler üretebilme yeteneği nedeniyle labirent oluşturma alanında yaygın olarak benimsenmiştir.

Wilson Algoritmasının Labirent Oluşturmada Çalışma Şekli

Wilson algoritması, ziyaret edilmemiş hücrelerden rastgele yürüyüşler kullanarak yinelemeli olarak yollar oluşturarak, son labirentin hiçbir döngü içermeden tamamen bağlantılı olmasını sağlar.

Adım 1: Başlatma

• Duvarlarla dolu bir ızgara ile başlayın.
• Olası tüm geçiş hücrelerinin bir listesini tanımlayın.

Adım 2: Rastgele Bir Başlangıç Hücresi Seçin

• Rastgele bir hücre seçin ve ziyaret edilmiş olarak işaretleyin. Bu, labirent oluşturma sırasında başlangıç noktası olarak görev yapar.

Adım 3: Döngü Silme Özellikli Rastgele Yürüyüş

• Ziyaret edilmemiş bir hücre seçin ve rastgele bir yürüyüşe başlayın (rastgele yönlerde hareket edin).
• Eğer rota daha önce ziyaret edilmiş bir hücreye ulaşırsa, rotadaki tüm döngüleri silin.
• Yürüyüş yolu ziyaret edilen bölgeye ulaştığında, yol üzerindeki tüm hücreleri ziyaret edilmiş olarak işaretleyin.

4. Adım: Tüm hücreler ziyaret edilene kadar tekrarlayın:

• Daha önce ziyaret edilmemiş hücreleri seçmeye ve her hücre labirentin bir parçası olana kadar rastgele yürüyüşler yapmaya devam edin.

Daha Fazla Okuma

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

• Kruskal Algoritması Labirent Oluşturucu
• Avla ve Öldür Labirenti Oluşturucu
• Eller Algoritması Labirent Oluşturucu