Wave Function Collapse

Maksim Gumin tarafından geliştirilmiştir. Amaç, basit yapılara(configuration) veya örnek görüntülere dayalı tile based görüntüler oluşturmaktır. Tabi daha birçok alanda da kullanılmaktadır. Tessera asseti ile yapılabileceklere ve twitterda #wavefunctioncollapse hastagi ile yapılan örneklere göz atabilirsiniz. WFC’e geçmeden önce constraint programming ile ilgili birkaç şey söylemek isterim.

Constraint programming bilgisayarlara talimat vermenin bir yoludur. Belirli talimatların bir listesini verdiğimiz imperative programming yada functional programming’in aksine, constraint programming’e matematiksel bir fonksiyon verdiğimizde, bilgisayara titizlikle tanımlanmış bir problem vermiş oluruz ve ardından bilgisayar çözümü bulmak için hazırlanmış algoritmaları kullanır.

Mini Sudako

Örnek vermesi adına Mini Sudoku kullanalım. Mini Sudako sayılar ile doldurulmuş 4*4 ızgaraya sahip bir bulmacadır.

Amaç, aşağıdaki kurallara uyarak her boş kareyi 1 ile 4 arasında bir sayı ile doldurmaktır:

• 1 ile 4 arasındaki sayılar her satırda tam olarak bir kez görünmelidir
• 1 ile 4 arasındaki sayılar her sütunda tam olarak bir kez görünmelidir
• 1 ile 4 arasındaki sayılar, 2 × 2 köşe kutularının her birinde tam olarak bir kez görünmelidir

Bu kurallara uyarak, sonunda çözümü bulursunuz:

Bizim kolayca çözebileceğimiz bu bulmacayı bilgisayar nasıl çözer? İlk olarak sorunu bilgisayara belirtiriz ve ardından çözmek için bir algoritma kullanırız.

Problemin Tanımlanması

Genellikle bunu yapmak için bir constraint programming kullanırız. Bunun birkaç yolu var, ancak hepsi benzer şekillerde çalışıyor.

Öncelikle problemin değişkenlerini(variables) tanımlamalıyız. Değişkenler normal programlamadaki gibi değildir. bir constraint çözücü(solver) için değişken, çözümünü bulmak istediğimiz bilinmeyen bir değer anlamına gelir. Mini Sudoku örneğimizde, her boş kare için bir değişken oluşturacağız. Kolaylık sağlamak için dolu kareler için de bir değişken oluşturabiliriz.

Her değişken için, daha sonra alması mümkün olan değerler kümesini tanımlarsınız. Her boş kare için kümemiz {1, 2, 3, 4} şeklindedir. Zaten 1 ile doldurulmuş bir kare için ise küme {1} olacaktır.

Son olarak, değişkenleri birbiriyle ilişkilendiren kuralları, kısıtlamaları belirtiriz. Çoğu constraint programlama dili, all_distinct (..) adında önceden var olan bir kısıtlama fonksiyonuna sahiptir ve bu, iletilen değişkenlerin farklı olmasını gerektirir. Dolayısıyla, mini Sudoku kuralları, her satır, sütun ve 2 × 2 köşe kutusu için bir tane olmak üzere 12 all_distinct kısıtlamasına çevrilir.

Constraint Solving Algoritmaları

Her hücreye, o değişken için alandaki tüm olası değerleri belirten birden çok sayı yazalım. Şimdi ilk kısıtlamayı ele alalım. Üst sıradaki dört hücrenin hepsinin farklı olması gerekir. Ama bu hücrelerden birinde zaten 4 var. Bu, diğer 3 hücrenin 4 olamayacağı anlamına gelmelidir. Yani, bu hücrelerin kümesinden 4ü çıkarabiliriz.

Bu süreci on iki kısıtlamanın hepsinde sistematik olarak tekrarlayabiliriz. Bilgi, bir değişkenden diğerine kısıtlamalar yoluyla yayıldığından, bu sürece kısıt yayılımı (constraint propagation) denir.

Bazı alanlarda sadece tek bir değeri olan değişkenlerimiz var. Bu, bu değişkenler için doğru çözüm diyebiliriz.

Bu adımdan sonra sonuca gidene kadar constraint propagation yapılır -yeni yazılan 1 ler diğer değişkenlerin 1 olamayacağı anlamına gelir. Bu algoritma, bütün değişkenlerin tek bir değere sahip olmasıyla son bulur.-

Daha Zor Problem

Ne yazık ki, tüm bulmacaların cevabını bu kadar çabuk vermiyor. İşte tam boyutlu bir sudoku bulmacası. Aynı şekilde çalışır, ancak artık 9 farklı değer, 9 satır, 9 sütun ve 9 tane 3 × 3 kutu vardır.

Daha önce tarif ettiğimiz prosedürü denersek, sıkışırız:

Bu noktada, tüm kısıtlamalar tamamen yayılır, ancak yine de belirsiz olan birçok kısım vardır.

Bu noktada, bir insanın bunu çözme şekli ve bir bilgisayar algoritması birbirinden ayrılır. İnsanlar için öğreticiler(tutorials) artık giderek daha karmaşık mantıksal çıkarımlar aramaya başlamanızı söylüyor. Bilgisayar algoritmamızın bunu yapmasını istemiyoruz -herhangi bir kısıtlama kümesiyle çalışacak genel bir algoritma istiyoruz.-

Bunun yerine bilgisayarlar mümkün olan en aptalca şeyi yapar: tahmin ederler. Önce bulmacanın mevcut durumunu kaydediyoruz. Ardından, rastgele bir değişken seçeriz ve değerini olası değerlerinden birine ayarlarız. Merkezdeki kareyi seçelim ve değeri 1 olarak ayarlayalım. Artık kısıtlamaları biraz daha yayarak daha fazla ilerleme kaydedebiliriz. Aşağıdakileri elde edene kadar merkezi sütun için kısıtlamayı tekrar tekrar çalıştıralım.

Mavi değerler, tahmin ettiğimizden beri yaptığımız tüm çıkarımlardır. Ve görüyoruz, özel bir şey oldu. Birkaç değişken daha çözüldü, ancak en üst ortadaki kareye bakın. Boştur — etki alanında o karenin tüm kısıtlamalarını karşılayan olası bir değer yoktur (aynı 3 × 3 kutuda 5 olduğu için 5 olamaz ve sütun nedeniyle başka bir sayı olamaz).

Boş alanı olan bir değişken elde edersek, bu alana değişken atamanın mümkün olmadığı anlamına gelir. Bu, bulmacanın tamamlanamayacağı anlamına gelir. Bu da tahminimizin yanlış olduğu anlamına geliyor.

Bunun gibi bir çelişki bulduğumuzda, geri izleme (backtracking) adı verilen bir prosedür uygularız. İlk olarak, bulmacayı tahminden önceki durumuna geri yüklüyoruz. İkinci olarak, tahmin edilen değeri (1) tahmin edilen değişkenin bulunduğu kümeden (ortadaki küme {1,5,8,9}) alanından kaldırırız. Bunu yapmamızın sebebi artık bu değeri seçmenin sorunlara yol açtığını biliyoruz, bu nedenle doğru cevap olamaz.

Pekala, bu çok yorucuydu, ama şimdi küçük bir ilerleme kaydettik. Merkezden 1'i eledikten sonra, hala sıkışmış durumdayız. Bu yüzden tekrar tekrar tahmin etmenin zamanı geldi.

Algoritmada gerçekten çok fazla şey yok. Her yayılma sürecinde takılıp kaldığınızda, bir tahminde bulunun ve devam edin. Her çelişkide, en son kaydedilene geri döner ve bir olasılık olarak tahmini ortadan kaldırırız. Bir çelişkiye ulaşmadan önce birkaç kez takılıp kalabileceğimiz için, bir yığın kaydedilmiş durum ve tahmin elimizde kalır.

Geriye döndüğümüzde (backtrack) her seferinde en az bir değişkenin etki alanını azaltırız, bu nedenle çok fazla vazgeçme ve yeniden başlatma söz konusu olsa bile, algoritmanın sonucu bulması garanti edilir.

WFC’ye Dönüş

Wave Function Collapse bir kısıtlama(constraints) problemidir — binlerce olası çözüm vardır. Ana fikir, tahminlerimiz ile bir çözücü(solver) elde etmek yerine rastgele yaparsak, bir generator(oluşturucu) elde ederiz. Ancak bu generator, belirlediğimiz tüm kısıtlamalara uyacak ve böylece onu diğer birçok prosedürel nesilden çok daha kontrol edilebilir hale getirecektir.

WFC’de amaç, yakındaki tile’ların birbirine bağlanacağı şekilde bir grid’i tile’larla doldurmaktır. Yukarıda kullandığımız terminolojide, her bir tile farklı bir değerdir ve ızgaradaki her hücre(cell), tile seçimini temsil eden bir değişkendir.

Maxim, makul bir tile seçimi ve mantıklı bir randomizasyon rutini ile, nadiren geriye dönmenin (backtrack) gerekli olduğunu keşfetti. Bu, WFC algoritmasının en basit haliyle aşağıdaki gibi göründüğü anlamına gelir:

• Her hücre(cell) için, o değişkenin alanını temsil eden bir boolean array oluştur (sudoku örneğindeki gibi her kutucuğun alabileceği değerler kümesi örn. {1, 5, 8, 9} ). Etki alanı her tile başına bir girişe sahiptir ve hepsi true olarak başlatılır. Bu giriş doğruysa, etki alanında bir tile var.
• Etki alanında hâlâ birden çok öğe bulunan hücreler varken:
• “Least entropy” yöntemini kullanarak rastgele bir hücre seçin.
• Bu hücrenin alanından rastgele bir tile seçin ve alandan diğer tüm döşemeleri kaldırın.
• Bu yeni bilgilere göre diğer hücrelerin alan kümelerini güncelleyin. Bu hücrelerde yapılan değişikliklerin başka etkileri olabileceğinden, bunun tekrar tekrar yapılması gerekir.

Örnek

3'e 3'lük bir grid’i aşağıdaki 4 karo(tile) kümesiyle doldurmak istediğimizi varsayalım:

Kullanacağımız kısıtlamalar, bitişik karolardaki renklerin birbiriyle eşleşmesi gerektiğidir.

Sudoku örneğinde olduğu gibi, alanda ne olduğunu belirtmek için küçük gri resimler kullanalım. Alanda yalnızca tek bir öğe kaldığında, onu daha büyük ve renkli gösterelim.

Başlangıçta, her hücre her grid konumu için olası bir seçenektir.

Şimdi WFC’nin ana döngüsünü tekrarlıyoruz. İlk önce rastgele bir hücre seçiyoruz, diyelim sol üst. Ardından, etki alanında bir karo seçeriz ve diğerlerini kaldırırız.

Sonra kısıtlamaları yayarız. Tek kuralımız bitişik karolar hakkındadır, bu nedenle bitişiğimiz olan iki hücreyi güncellememiz gerekir:

Daha küçük alanlarda güncellenecek başka karo var mı? Evet! Üst merkezdeki karo seçiminden hala emin olamamış olsak da, kalan tüm seçeneklerin sağa doğru ilerlediğini görebiliriz. Bu, sağ üstteki bazı karoların belirlenmiş bir hücresi olmadığı anlamına gelir. Benzer şekilde sol alt içinde geçerli.

Artık yapılacak bir yayılma yok, bu yüzden ana döngüyü yeniden yapıyoruz — bir hücre seçer, bir karo seçer ve yayarız. Bu kez, üst orta karo seçildi ve birkaç karo olasılık olarak elendi.

Bir döngü daha. Bu kez merkez-sol döşeme seçildi ve yayıldıktan sonra, ortadaki döşeme için yalnızca bir olasılık kaldı.

Tüm grid dolana kadar devam eder.

Daha gelişmiş bir örnek için Oscar Stålberg’in bu çalışmasına göz atabilirsiniz. Burada ise 3 boyutlu örnek mevcuttur.

Least Entropy

Doldurulacak bir sonraki karoyu seçerken, bazı seçenekler diğerlerinden daha iyidir. Grid’in herhangi bir yerinden rastgele seçim yaparsak, aynı anda birden fazla alanı doldurabiliriz. Bu yöntem bazı sorunlara neden olabilir — tile setine bağlı olarak, zamanı geldiğinde doldurulmuş alanları birleştirmek mümkün olmayabilir. Sorun yaratma olasılığı en düşük olan hücreleri seçmek istiyoruz. Bunun için bariz bir seçim var — etki kümesinde mümkün olan en az değere sahip hücreyi seç (en az 2 olasılık). Bu iyi bir seçimdir:

1. Diğer doldurulmuş hücrelerin yakınında olma olasılığı yüksek olan
2. Eğer onu daha sonraya bırakırsak, halihazırda birkaç olasılık olduğu için sorun olabilir.

Devam edecek…

Görsel ve içerik Wave Function Collapse Explained adlı makaleden alınmıştır.

Thank you so much Boris.

Kaynakça

Wave Function Collapse Explained