Eller Algoritması Labirent Oluşturucu

Eller algoritması, satır satır yaklaşım kullanarak mükemmel labirentler (döngü içermeyen ve herhangi iki nokta arasında tek bir yol bulunan labirentler) üreten verimli bir labirent oluşturma algoritmasıdır. Kruskal algoritmasına benzer labirentler üretir, ancak bunu tüm labirenti bellekte saklamaya gerek kalmadan, her seferinde yalnızca bir satır üreterek yapar. Bu da onu çok sınırlı sistemlerde çok büyük labirentler oluşturmak ve prosedürel içerik üretimi 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 tanıtı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. Genellikle prosedürel içerik oluşturma ve labirent oluşturma literatüründe yer alıyor, ancak orijinal yayınını detaylandıran birincil kaynaklar bulamadım.

Eller'in Labirent Oluşturma Algoritması Nasıl Çalışır?

Eller algoritması, bağlantılı hücre kümelerini koruyup değiştirerek, her seferinde bir satırı işler. Döngülerden kaçınarak bağlantıyı sağlar ve labirenti verimli bir şekilde aşağı doğru genişletir.

Teorik olarak sonsuz labirentler oluşturmak için kullanılabilir, ancak oluşturulan labirentin gerçekten çözülebilir olduğundan emin olmak için, labirenti tamamlamak üzere bir noktada "son satır" mantığına geçmek gereklidir.

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

• Bitişik hücreleri aynı küme kimliğine ayarlayarak rastgele birleştirin. Bu, yatay geçişlerin olmasını sağlar.

3. Adım: Sonraki Satıra Dikey Bağlantılar Oluşturun

• Satırda yer alan her bir küme için, en az bir hücrenin aşağı doğru bağlanması gerekir (bağlantının sağlanması için).
• Her bir hücre kümesinden rastgele bir veya daha fazla hücre seçerek bir sonraki satıra bağlayın.

Adım 4: Sonraki Satıra Geçin

• Aşağıdaki hücrelere aynı küme kimliğini atayarak dikey bağlantıları devam ettirin.
• Atanmamış hücrelere yeni küme kimlikleri atayın.

Adım 5: Son sıraya ulaşılana kadar 2-4 arasındaki 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.

Daha Fazla Okuma

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

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