- Wave Function Collapse (WFC) algoritması kullanılarak yaklaşık 4.100 altıgen karo içeren ortaçağ temalı ada haritasını otomatik üreten bir proje
- Her karo yol, nehir, kıyı, uçurum, orman, köy gibi arazi bilgileri içeriyor ve Three.js WebGPU ile TSL shader kullanılarak yaklaşık 20 saniyede üretiliyor
- Büyük ölçekli ızgaralarda ortaya çıkan başarısızlıkları çözmek için yapı 19 altıgen alt ızgaraya bölünüyor ve backtracking ile local-WFC kurtarma sistemi sayesinde başarı oranı %86'nın üzerine çıkıyor
- Görsel tarafta PBR materyaller, WebGPU tabanlı shader'lar, su yansıması ve dalga efektleri, post-processing (aydınlatma, alan derinliği, grain) uygulanarak derinlik hissi güçlendiriliyor
- BatchedMesh render ve tek materyal paylaşımı ile binlerce karo 60fps hızında çizdiriliyor; bu da prosedürel üretim ile gerçek zamanlı grafiklerin birlikte kullanılabileceğini gösteriyor
Prosedürel harita üretimine genel bakış
- Proje, AD&D zindan zar üretim yönteminden ilham alıyor; kullanıcı doğrudan tasarlamasa bile algoritma dünyayı kendi kendine kuruyor
- Üretilen harita; yol, nehir, kıyı çizgisi, uçurum, orman, köy içeren ortaçağ tarzı bir ada formunda ve yaklaşık 4.100 altıgen hücreden oluşuyor
- Three.js WebGPU ve TSL shader kullanılarak tüm harita yaklaşık 20 saniyede tamamlanıyor
Wave Function Collapse (WFC) algoritması
- WFC, komşu karoların kenarlarının (edge) eşleşmesi gerektiği kısıtına dayanarak araziyi oluşturuyor
- Altıgen karolar 6 kenara sahip olduğu için kare karolara kıyasla %50 daha fazla kısıt koşulu taşıyor
- Her karo 6 yönlü kenar tipleri ile ağırlıklarını tanımlıyor; örneğin 3 yönlü yol kavşağı, yol ve çim kenarlarını dönüşümlü olarak içeriyor
- Algoritma şu adımları izliyor:
- Tüm hücreleri mümkün olan tüm durumlarla başlatma
- En fazla kısıtlanan hücreyi seçip tek bir duruma “çökertme”
- Komşu hücrelerde imkânsız durumları kaldırarak yayılım yapma
- Tüm hücreler çözülene kadar bunu tekrarlama
Büyük ızgaralar ve modüler çözüm
- Küçük ızgaralarda kararlı çalışsa da 4.000 hücre üzerindeki yapılarda başarısızlık olasılığı hızla artıyor
- Bunu çözmek için yapı 19 altıgen alt ızgaraya ayrılıyor; her ızgara bağımsız çözülürken sınır karoları sabit kısıtlar olarak korunuyor
- Sınır kısıtları çakıştığında sorun yalnızca backtracking ile çözülemiyor
Backtracking ve kurtarma sistemi
- Backtracking, yanlış seçimi geri alıp başka bir karoyu deneme yöntemi ve en fazla 500 kez uygulanıyor
- Ancak ızgaralar arası çakışmalar ayrı bir kurtarma sistemiyle ele alınıyor
- 1. aşama: Unfixing — çakışan hücreler yeniden değişken duruma alınırken çevredeki hücreler yeni kısıtlar olarak ayarlanıyor
- 2. aşama: Local-WFC — yarıçapı 2 hücre olan bölgede (19 hücre) yeniden çözüm yapılarak sınır uyumluluğu sağlanıyor, en fazla 5 kez deneniyor
- 3. aşama: Drop & Hide — başarısız olunursa ilgili hücre kaldırılıp dağlık bir karo ile kapatılarak doğal görünmesi sağlanıyor
- Bu çok katmanlı kurtarma yapısı sayesinde tüm harita üretiminde yaklaşık %86 başarı oranı elde ediliyor
3 boyutlu yükseklik işleme
- Harita 5 kademeli yükseklik seviyesine sahip ve eğimli yüzeyler ile uçurum karoları üst ve alt seviyeleri birbirine bağlıyor
- Yanlış bağlantılar olduğunda yolların uçurumda kesilmesi veya nehirlerin yukarı doğru akması gibi hatalar ortaya çıkabiliyor
- Yükseklik bilgisi instance color içinde kodlanıyor ve shader, alçak ve yüksek rakım renk paletlerini harmanlıyor
Altıgen koordinat sistemi
- Altıgen yapı 6 yönlü olduğu için basit bir 2D koordinat sistemiyle komşuluk hesabı karmaşık hale geliyor
- Bunu sadeleştirmek için cube coordinate sistemi (q, r, s) kullanılıyor
- WFC, gerçek geometriden çok kenar eşleme grafı yapısına odaklandığından koordinat sistemi çoğunlukla render ve çoklu ızgara yerleşimi için kullanılıyor
Ağaç ve bina yerleşimi
- WFC, yerel desenlerde güçlü olsa da geniş ölçekli dağılım için uygun değil
- Ağaçlar ve binalar, yoğunluğu belirlemek için Perlin gürültü alanı kullanıyor; böylece orman ve köy kümeleri daha doğal oluşuyor
- Ek mantık ile yol sonlarına binalar, kıyılara liman ve yel değirmenleri, tepelere ise taş çemberler (henge) yerleştiriliyor
Su efektlerinin uygulanması
- Deniz, basit bir düzlem değil; parıltılar ve kıyı dalgaları içeriyor
- Parıltılar (Sparkles), Voronoi gürültüsü yerine küçük kayan doku + gürültü maskesi ile uygulanarak GPU yükü azaltılıyor
- Kıyı dalgaları (Coast Waves), kıyı maskesinin blur uygulanmasıyla mesafe tabanlı sinüs dalga bantları üretiyor
- Koy (Cove) probleminde, blur tabanlı mesafe hesabı yeterince doğru olmadığı için CPU çevredeki hücreleri inceleyip dalgaların daha ince işleneceği alan maskesini oluşturuyor
Karo üretimi ve hizalama
- Temel model olarak KayKit Medieval Hexagon Pack kullanılıyor; ancak eksik bağlantı karoları (eğimli nehir, uçurum varyasyonları vb.) Blender ile doğrudan üretilmiş
- Tüm karolar 2 birim genişlikte standartlaştırılıyor ve UV hizalama hataları oluşursa sınırlar görünür hale geldiğinden hassas eşleme gerekiyor
Görsel efektler ve render
- Uygulama Three.js WebGPU + TSL shader ile geliştiriliyor; GLSL yerine düğüm tabanlı shader yapısı kullanılıyor
- Post-processing zinciri
- GTAO ile gölgelendirmeyi belirginleştirme
- Alan derinliği (Depth of Field) ile minyatür etkisi verme
- Vignette ve film grain ile analog doku katma
- Dinamik shadow map, kamera görüşüne göre her karede yeniden ayarlanarak yakınlaştırmada da keskin gölgeler korunuyor
Performans optimizasyonu
- BatchedMesh ile her ızgaranın karoları ve süslemeleri tek grupta toplanıp tek draw call ile render ediliyor
- Tüm mesh'ler tek bir materyali paylaşıyor; böylece shader durum geçişleri en aza indiriliyor
- Sonuç olarak 38 BatchedMesh, 4.100+ hücre ve 60fps render başarılıyor
Başlıca sayılar ve teknoloji yığını
- 30 karo türü, 19 ızgara, ~4.100 hücre, 500 kez backtracking, 5 Local-WFC denemesi, 20 saniye üretim, %100 başarı oranı (500 testte)
- Three.js r183, TSL shader, Web Workers, Vite build, BatchedMesh, Seeded RNG kullanılıyor
Deneyim ve kaynak
- Canlı demo üzerinden haritayı genişletmek ve tamamını üretmek mümkün
- GitHub kaynak kodu açık; 50'den fazla parametreyle aydınlatma, renk, su ve WFC ayarları değiştirilebiliyor
Özet
- Zarlar yerine algoritmanın dünyayı kurduğu bir deneyim sunuyor ve her seferinde farklı arazi yapılarıyla yol ve nehir bağlantıları keşfedilebiliyor
- Prosedürel üretim, grafik optimizasyonu ve shader teknolojisini birleştiren WebGPU tabanlı harita üretim deneyi
1 yorum
Hacker News görüşleri
Yazıda backtracking'in yalnızca 500 adımla sınırlandığı söyleniyor ama aslında kısıt programlama oldukça ilginç ve karmaşık bir alan
Knuth'un Algorithm X'i ve dancing links kullanılırsa, yazıda bahsedilen "Layer 2" bölgesi %86'dan daha yüksek bir başarı oranıyla çözülebilir gibi görünüyor
Ayrıca çeşitli heuristic'ler uygulanırsa, arama basit brute force'tan çok daha hızlı yapılabilir. Sudoku çözücüsü yazmış olanlar brute force'un ne kadar yavaşlayabildiğini iyi bilir
Örneğin MiniZinc, birden fazla solver backend'ini destekleyen yüksek seviyeli bir modelleme dili sunuyor
Algoritmayı doğrudan yazmak yerine, bu tür endüstriyel çözücülerle problemi modelleyip çözücünün rastgele ya da tam aramayla çözüm bulmasını sağlamak daha verimli
Böylece çözücü yazmaya zaman harcamak yerine, problem tanımını ayarlayıp daha ilginç haritalar oluşturmaya odaklanabilirsiniz
Benim dizüstünde (11. nesil Core i5, Iris Xe, Chrome'un son sürümü) demo 5 FPS'te çalışıyor. Darboğaz GPU gibi görünüyor
Yazıda mobilde 60 FPS çalıştığı söylendiği için biraz daha verimli olmasını bekliyordum
Harita güzel ama WFC'nin tile düzeyindeki kısıtları yüzünden doğal olmayan sonuçlar ortaya çıkıyor. Çünkü non-local influence'ı yansıtmak zor
Karoları tek tek keşfetmeye dayalı oyunlar için uygun ama tüm haritayı üretmek için pek uygun değil
Red Blob Games'in gürültü tabanlı yaklaşımı daha iyi sonuç veriyor. Nehirler nem takibiyle, yollar ya da köprüler ise ayrı bir geçişte ele alınırsa daha hızlı ve daha sağlam olur
Yine de WFC ilginç bir programlama problemi; bu yüzden uygulamanın kendisini yapmak muhtemelen keyifli olmuştur. Genel olarak harika bir yazı ve etkileyici bir demoydu
Oskar Stålberg, Wave Function Collapse(WFC)'u birkaç oyunda kullandı. Bunların en bilineni Townscaper
İlgili sunum videosu SGC21 - Beyond Townscapers'da izlenebilir
Jasper Flick'in Unity eğitimi Hex Terrain aklıma geldi
Bu proje önceden hazırlanmış tile'ları kısıtlarla eşleştirirken, Jasper'ın eğitiminde tile sınırları dinamik olarak oluşturuluyor
Her iki yaklaşım da ilginç ve okuması keyifli
Gerçekten harika bir projeydi
Bu arada yazar bunu görürse, tile'ların superposition durumunu (olası seçenekler kümesini) bir bitfield olarak temsil etmeyi düşünüp düşünmediğini merak ediyorum
Geçmişte WFC uyguladığımda bitfield'e geçince hız artışı inanılmaz olmuştu. Backtracking yapmaktan ziyade tüm chunk'ı yeniden hesaplamak daha hızlı hale gelmişti
Belirli aralıklarla durumu stack'e kaydedip, tıkanınca son duruma geri dönüyor
Değişken adının
tenperolması geçmişteki kendime biraz içerlememe neden oluyorKısıtları sağlayan bir düzen bulmak işin en zor kısmı gibi görünüyor
Acaba SAT solver kullanmak bir alternatif olabilir mi diye düşündüm. Ama o durumda her zaman 'kolay' çözümleri bulup rastgeleliğin azalması da mümkün
Bazı SAT solver'lar başlangıç değişkenlerini rastgele atayabiliyor ama bu doğrudan rastgele çözüm anlamına gelmiyor. Benzer bir şey deneyen oldu mu merak ediyorum
Buna karşılık WFC basit bir brute force yaklaşımı olduğu için uygulanması kolay ve çok fazla çıkmaz sokak yoksa hesaplama maliyeti düşük
Oyunlarda kusursuz çözümden ziyade 'yeterince iyi' sonuç yeterli olduğundan, WFC daha pratik olabilir
İlham verici bir projeydi. Referanslar da harika ve kaynak kodu açık
Buna Here Dragons Abound'un görsel stilini eklerseniz çok hoş olabilir
OP muhtemelen zaten biliyordur ama Red Blob Games'in Hexagon matematiği sayfasında çok sayıda harika örnek ve kod var
Kare olmayan(non-square) grid'lerde WFC'yi incelemek ilginç
Kısıt yayılımının karmaşıklığı klasik örneklere kıyasla çok daha yüksek gibi görünüyor
Böyle karmaşık topolojilerde Constraint Logic Programming gibi başka kısıt çözücülerin ifade gücü ve performans açısından avantajlı olabileceğini düşündürüyor
Dorfromantik aklıma geldi. Steam bağlantısı