Hücresel Otonomlar ile Yordamsal Zindan / Mağara / Harita Üretimi

Hücresel otonomlar ile yardımı ile bir mahzen oluşturma hedefindeydik.

Hücresel otonomlar, N boyutlu bir matriste, kesikli zaman aralıkları ile yürütülen hesaplamalar ile her bir matris hücresinin sonlu sayıdaki değer kümesi içinden değer alabildiği ve matris hücresinin bir sonraki iterasyondaki değerinin, komşularının mevcut değerleri üzerinden belli kurallara göre belirlendiği matematiksel yapı olarak tanımlanabilir ^[1][2][3]

Otonomlar N boyutlu matrislerde tanımlanabiliyor olsalar da, bizim ihtiyacımız olan 2 boyutlu ve yaşamvari olan otonomlar. Dolayısı ile aşağıdaki bölüm konumuzla direk ilgili değil, labirent üretmek isteyenler bir sonraki bölüme atlayabilirler.

Basit (Tek Boyutlu) Hücresel Otonomlar

Basit hücresel otonomlarda, bir hücrenin bir sonraki adımdaki durumunun hesaplanmasında yalnızca soldaki hücrenin, kendisinin ve sağdaki hücrenin durumları (ki bu durumlar 0 / 1 olabilirler ancak) kullanılıyor.

Üç hücrenin her birinin ancak iki farklı durumu olabileceğinden olası tüm kombinasyonlarının sayısı: 2³ = 8 dir.

<td style="text-align: center;">
  110
</td>

<td style="text-align: center;">
  101
</td>

<td style="text-align: center;">
  100
</td>

<td style="text-align: center;">
  011
</td>

<td style="text-align: center;">
  010
</td>

<td style="text-align: center;">
  001
</td>

<td style="text-align: center;">
  000
</td>

111

Bu 8 farklı kombinasyon için de hücrenin yeni durumu iki farklı değeri içerebilir. Bu durumda tek boyutlu otonomlar için üretilebilecek tüm kuralların sayısı ise 2⁸ = 256’dır.

Kuralların genel gösterimi ise şu şekildedir.

Mevcut Durum	111	110	101	100	011	010	001	000
Hücrenin Yeni Değeri		1	1		1	1	1

Alttaki satırın ikili sistemden onluk sisteme dönülmesi ile de kuralın numarası belirlenmiş olur. 01101110₂ = 110^[4][5].

Web üzerinde tüm kuralların çalışmasını gösteren bir çok javascript uygulaması var. Bunlardan yalnızca bir tanesi : https://dl.dropboxusercontent.com/u/676174/html/eca/main.html#demo

Tek boyutlu otonomları ilginç kılan unsurlar ise rassal sayı üretimi ve şifreleme (kural 30), fiziksel gerçeklerin modellenmesi, trafik akışı gibi parçacık modellenmesi (kural 184), evrensel hesaplayıcı / turing complete (kural 110) vb. çalışmalara konu olmaları.

İki Boyutlu Yaşamvari Hücresel Otonomlar

Hücresel otonomların yaşamvari olarak tanımlanabilmeleri için^[1] :

İki boyutlu olmaları
Hücrelerin yalnızca iki durumu olmalı (0: Ölü / 1: canlı)
Komşuları sayılırken köşeden değen komşular da sayılmalı (toplamda 8 komşu)
Bir sonraki iterasyondaki hücre değeri, canlı komşuları ile kendi durumunun bir fonksiyonu olarak ifade edilebilinmeli

Bir önceki yazımda belirttiğim üzere yaşamvari hücrresel otonomların en bilinen örneği Conway’in Yaşam Oyunudur. Bu tarz otonomların yaşam kurallarının metinsel olarak ifade edielbilinmesi amacı ile S/B notasyonu geliştirilmiştir.^[1]

S (Survival) : Canlı bir hücrenin canlı kalabilmesi için gerekli canlı komşu hücreleri tanımlar.
B (Birth) Ölü bir hücrenin canlanması için gerekli canlı hücreleri tanımlar.

Bu notasyona göre Conway’in algoritması şu şekilde ifade edilebilinir: 23/3 : Yani, bir canlı hücrenin 2 veya 3 canlı hücresi varsa yaşar, aksi takdirde ölür, bir ölü hücrenin 3 canlı komşusu varsa o hücre canlanır.

Mahzen ve labirent üretmek içinse en uygun kuralların

12345/3^[1]
45678/5678^[7]
1267/17^[6]
345678/5678^[8]

Oldukları söyleniyor. Şimdi bu kuralları rahatça test edebilmek adına github’daki projeyi, kuralların girebileceği şekilde yeniden düzenledim.

Kuralı girip, adım adım işletebiliyoruz simülasyonu

Bundan sonraki adım ise, kuralları, ilk doğurganlık oranı ile test ederek en fazla 4 adımda mağara / mahzen benzeri bir yapıya ulaşıp ulaşamadığımızı test etmek ve kurallar içerisinden en çok içimize sineni seçmek.

12345/3 – % 45

Bu ayar bize daha çok labirentsi bir yapı verdi :

45678/5678 – %45

Bu ayar da sanki arazi / dünya haritası gibi bir sonuç üretti. Canlı hücrelerin mi yoksa ölü hücrelerin mi deniz olacağı konusu ise size kalmış.

1267/17 – % 45

Daha çok labirente benzedi sanki..

345678/5678 – % 45

En iyi sonuçları bu kuraldan aldığımı düşünüyorum. 2 veya 3 iterasyon sonucunda gayet mantıklı gözüken haritalara ulaşabiliyoruz.

1. İterasyon sonu. Birden bire biraz mahzeni andırmaya başladı.

2. iterasyon: Her adım yapı biraz daha köşesiz hale geliyor.

Bu noktadan sonra yapılması gerekenler ise :

Floodfill algoritması ile mağaranın büyüklüğünü tespit etmek ve uygun boyutta olup olmadığına karar vermek, uygun değğilse yeni bir harita üretmek.
Arada kalan boşlukları doldurmak veya boşluklar çok büyükse koridorlar ile birbirine bağlayan bir algoritma geliştirmek.

Şimdiki hedefim bu iki nokta üzerinde çalışmaya başlamak…