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

Büyüyen Ağaç algoritması ilginçtir, çünkü nesil sırasında bir sonraki hücrenin nasıl seçildiğine bağlı olarak diğer birkaç algoritmanın davranışını taklit edebilir. Bu sayfadaki uygulama genişlik öncelikli, kuyruk benzeri bir yaklaşım kullanır.

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.

Büyüyen Ağaç Algoritması Hakkında

Büyüyen Ağaç algoritması, mükemmel labirentler üretmek için esnek ve güçlü bir yöntemdir. Algoritma ilginçtir çünkü Prim'in algoritması, yinelemeli geri izleme ve yinelemeli bölme gibi diğer birkaç labirent oluşturma algoritmasının davranışını, işlenecek bir sonraki hücreyi nasıl seçtiğinize bağlı olarak taklit edebilir.

Büyüyen Ağaç Algoritması Nasıl Çalışır

Adım 1: Başlatma

• Ziyaret edilmemiş hücrelerden oluşan bir ızgarayla başlayın.
• Rastgele bir başlangıç hücresi seçin ve onu bir listeye ekleyin.

Adım 2: Labirent Oluşturma Döngüsü

• Hücre listesi boş değilken:
  • Belirli bir stratejiye (aşağıda açıklanmıştır) göre listeden bir hücre seçin.
  • Seçili hücreden ziyaret edilmemiş komşularından birine (rastgele seçilmiş) bir geçit kazın.
  • Komşunuzu da listeye ekleyin, artık labirentin bir parçası.
  • Seçili hücrenin ziyaret edilmemiş komşusu yoksa, hücreyi listeden kaldırın.

Adım 3: Sonlandırma

• Listede hücre kalmadığında algoritma sonlanır, yani labirentin tamamı oyulmuş olur.

Hücre Seçim Stratejileri (Algoritmanın Esnekliği)

Growing Tree algoritmasının tanımlayıcı özelliği, bir sonraki adımda hangi hücreyi işleyeceğinize nasıl karar verdiğinizdir. Bu seçim, labirentin görünümünü önemli ölçüde etkiler:

En Yeni Hücre (Yığın Benzeri Davranış) – Özyinelemeli Geri İzleme:

• Her zaman en son eklenen hücreyi seç.
• Uzun, dolambaçlı ve çok sayıda çıkmazı olan koridorlar oluşturur (derinlemesine arama labirenti gibi).
• Labirentler genellikle uzun geçitlere sahiptir ve çözülmesi kolaydır.

Rastgele Hücre (Rastgele Prim Algoritması):

• Her seferinde listeden rastgele bir hücre seçin.
• Karmaşık ve karmaşık yollardan oluşan, daha eşit dağıtılmış bir labirent oluşturur.
• Daha az uzun koridor ve daha fazla dallanma.

En Eski Hücre (Kuyruk Benzeri Davranış):

• Listedeki her zaman en eski hücreyi seçin.
• Genişlik öncelikli arama örüntüsüne benzer şekilde daha düzgün yayılımlı labirentler oluşturur.
• Kısa, yoğun bağlantılara sahip çalılıklı geçitler.
• (Burada uygulanan versiyon budur)

Hibrit Yaklaşımlar:

Çeşitli labirent özellikleri için stratejileri birleştirin. Örneğin:

• %90 en yeni, %10 rastgele: Çoğunlukla tekrarlayan bir geri izleme labirentine benziyor, ancak ara sıra uzun koridorları bölen dallar da var.
• %50 en yeni, %50 en eski: Uzun koridorları gür bitki örtüsüyle dengeler.