Eller Algoritması Labirent Oluşturucu
Yayınlandı: 16 Şubat 2025 20:07:19 UTC
Mükemmel bir labirent oluşturmak için Eller algoritmasını kullanan labirent oluşturucu. Bu algoritma ilginçtir çünkü yalnızca geçerli satırı (tüm labirenti değil) bellekte tutmayı gerektirir, bu nedenle çok sınırlı sistemlerde bile çok, çok büyük labirentler oluşturmak için kullanılabilir.Eller's Algorithm Maze Generator
Eller'in algoritması, satır satır yaklaşım kullanarak mükemmel labirentler (hiçbir döngüsü olmayan ve herhangi iki nokta arasında tek bir yolu olan labirentler) üreten bir labirent oluşturma algoritmasıdır. Kruskal'ın algoritmasına benzer labirentler üretir, ancak bunu tüm labirenti bellekte depolamaya gerek kalmadan, her seferinde yalnızca bir satır oluşturarak yapar. Bu, onu çok sınırlı sistemlerde çok büyük labirentler oluşturmak ve prosedürel içerik oluşturmak için kullanışlı hale getirir.
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.
Eller Algoritması Hakkında
Eller Algoritması David Eller tarafından ortaya atılmıştır.
Algoritma, labirent oluşturmada satır satır verimli yaklaşımıyla dikkat çekiyor ve bu da onu sonsuz labirentler veya gerçek zamanlı olarak oluşturulan labirentler için ideal kılıyor. Prosedürel içerik oluşturma ve labirent oluşturma literatüründe sıklıkla atıfta bulunuluyor ancak orijinal yayınını ayrıntılarıyla açıklayan birincil kaynaklar bulamadım.
Eller Algoritması Labirent Oluşturma İçin Nasıl Çalışır?
Eller'in algoritması, bağlı hücre kümelerini koruyarak ve değiştirerek her seferinde bir satırı işler. Döngülerden kaçınırken bağlantıyı sağlar ve labirenti aşağıya doğru verimli bir şekilde uzatır.
Teorik olarak sonsuz labirentler üretmek için kullanılabilir, ancak üretilen labirentin gerçekten çözülebilir olduğundan emin olmak için, labirenti bitirmek için bir noktada "son satır" mantığına geçmek gerekir.
Adım 1: İlk Satırı Başlatın
- Satırdaki her hücreye benzersiz bir küme kimliği atayın.
Adım 2: Bazı Bitişik Hücreleri Yatay Olarak Birleştirin
- Aynı küme kimliğine ayarlayarak bitişik hücreleri rastgele birleştirin. Bu, yatay geçişlerin olmasını sağlar.
Adım 3: Sonraki Satıra Dikey Bağlantılar Oluşturun
- Satırda görünen her küme için en az bir hücrenin aşağıya doğru bağlanması gerekir (bağlantıyı sağlamak için).
- Her kümeden rastgele bir veya daha fazla hücre seçerek bir sonraki satıra bağlanın.
Adım 4: Sonraki Satıra Geçin
- Aynı küme kimliğini alttaki ilgili hücrelere atayarak dikey bağlantıları sürdürün.
- Atanmamış hücrelere yeni küme kimlikleri atayın.
Adım 5: Son Sıraya Ulaşana Kadar 2–4. Adımları Tekrarlayın
- Satır satır işlemeye devam edin.
Adım 6: Son Satırı İşleyin
- Son satırdaki tüm hücrelerin aynı kümeye ait olduğundan emin olmak için kalan ayrı kümeleri birleştirin.