Wilson Algoritması Labirent Oluşturucu
Yayınlandı: 16 Şubat 2025 19:34:20 UTC
Wilson algoritmasını kullanarak mükemmel bir labirent oluşturmak için labirent üreteci. Bu algoritma, belirli bir boyuttaki tüm olası labirentleri aynı olasılıkla oluşturur, bu nedenle teoride birçok karışık düzende labirent oluşturabilir, ancak daha kısa koridorlu daha fazla olası labirent olduğu için, bunları daha sık göreceksiniz.Wilson's Algorithm Maze Generator
Wilson algoritması, labirent oluşturma için tekdüze yayılan ağaçlar üreten bir döngü silinmiş rastgele yürüyüş yöntemidir. Bu, belirli bir boyuttaki tüm olası labirentlerin oluşturulma olasılığının eşit olduğu 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 yüzden burada Aldous-Broder algoritmasını uygulama zahmetine girmedim.
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
Döngü silinmiş rastgele bir duvar kullanarak düzgün yayılan ağaçlar üreten Wilson algoritması David Bruce Wilson tarafından oluşturulmuştur.
Wilson bu algoritmayı ilk olarak 1996'da olasılık teorisinde rastgele yayılan ağaçlar ve Markov zincirleri üzerine araştırma yaparken tanıttı. Çalışmaları temel olarak matematik ve istatistiksel fizikte olmasına rağmen, algoritma o zamandan beri mükemmel derecede düzgün labirentler üretme yeteneği nedeniyle labirent oluşturmada yaygın olarak benimsendi.
Wilson Algoritması Labirent Oluşturma İçin Nasıl Çalışır?
Wilson algoritması, rastgele yürüyüşler kullanarak ziyaret edilmemiş hücrelerden yinelemeli olarak yollar oyularak son labirentin herhangi bir döngü olmaksızın tamamen bağlantılı olmasını sağlar.
Adım 1: Başlatma
- Duvarlarla dolu bir ızgarayla başlayın.
- Tüm olası geçiş hücrelerinin bir listesini tanımlayın.
Adım 2: Rastgele Bir Başlangıç Hücresi Seçin
- Herhangi bir rastgele hücreyi seçin ve ziyaret edilmiş olarak işaretleyin. Bu, üretim sırasında labirentin başlangıç noktası olarak hizmet eder.
Adım 3: Döngü Silme ile Rastgele Yürüyüş
- Ziyaret edilmemiş bir hücreyi seçin ve rastgele bir yürüyüşe (rastgele yönlerde hareket ederek) başlayın.
- Eğer yürüyüş daha önce ziyaret edilmiş bir hücreye ulaşırsa, yoldaki tüm döngüleri silin.
- Yürüyüş ziyaret edilen bölgeye bağlandıktan sonra, yol üzerindeki tüm hücreleri ziyaret edilmiş olarak işaretleyin.
Adım 4: Tüm Hücreler Ziyaret Edilene Kadar Tekrarlayın :
- Ziyaret edilmemiş hücreleri seçmeye ve her hücre labirentin bir parçası olana kadar rastgele yürüyüşler yapmaya devam edin.