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ı: 23 = 8 dir.

111 110 101 100 011 010 001 000

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 28 = 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 0 1 1 0 1 1 1 0

Alttaki satırın ikili sistemden onluk sisteme dönülmesi ile de kuralın numarası belirlenmiş olur. 011011102 = 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.

İlk Durum Çok karışık gözüküyor…
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 :

  1. 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.
  2. 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…

Kaynaklar

  1. http://www.conwaylife.com/wiki/Cellular_automaton
  2. http://en.wikipedia.org/wiki/Cellular_automaton
  3. http://natureofcode.com/book/chapter-7-cellular-automata/
  4. http://mathworld.wolfram.com/ElementaryCellularAutomaton.html
  5. http://en.wikipedia.org/wiki/Elementary_cellular_automaton
  6. http://gamedev.stackexchange.com/questions/79049/generating-tile-map
  7. http://www.roguebasin.com/index.php?title=Cellular_Automata_Method_for_Generating_Random_Cave-Like_Levels
  8. http://gamedevelopment.tutsplus.com/tutorials/cave-levels-cellular-automata–gamedev-9664
  9. http://pixelenvy.ca/wa/ca_cave.html

Diğer İlgili Linkler

Hayat Oyunu – Ilgın’ın Macerası

Kızım için, onunla beraber çok uzun zamandır bir oyun yazmayı planlıyordum, geçen 1 mayıs tatilinde ailece yaptığımız Eskişehir gezisi sonrasında Aizanoi antik kentinin de atmosferi ile konu gene alevlendi. Ilgın’ın hayalindeki oyununun hikayesini beraberce kurgulamaya başladık.

ilgin_zeus
Ilgın Zeus Tapınağı’nda
Zeus Tapınağı

Ilgın’ın hikayesinin kahramanı, çeşitli tehlikeli görevleri başardıktan sonra, büyücünün kara kitabına ulaşıp, ülkeyi esir alan büyüyü kaldıracaktır. Yalnız yine Ilgın’ın kurgusuna göre, oyunun başında oyuncu ana karakterin özelliklerini (cinsiyet, büyü gücü, dövüş gücü vs..) belirleyecek ki bu da oyunu biraz adventure biraz da rpg temelli hale getiriyor.

Ilgın’ın her oynadığında farklı bir oyun oynuyormuş hissini alması için, her seviyenin (Ilgın’a göre her görevin) farklı bir harita üzerinde geçmesini hedefledim (Eh bu da işin içine rogue-like oyunu sokuyor). Aynı seviyenin her oynanışında farklı bir haritada geçmesi ise işleme dayalı harita üretimi (procedural map generation) anlamına geliyor.

Peki, her seferinde rassal olarak üretilen ama mantıklı görünen bir haritayı / zindanı nasıl oluşturabiliriz şeklindeki araştırmalarım beni hücresel otomatlara (cellular automaton) kadar götürdü. Hücresel otomatların belki de en bilineni Conway‘in Hayat Oyunu.

Bu oyunda kurallar çok basit aslında,

  • Bir canlı hücrenin, iki’den daha az canlı komşusu varsa “yalnızlık nedeniyle” ölür
  • Bir canlı hücrenin, üç’ten daha fazla canlı komşusu varsa “kalabalıklaşma nedeniyle” ölür
  • Bir canlı hücrenin, iki ya da üç canlı komşusu varsa değişmeden bir sonraki nesile kalır
  • Bir ölü hücrenin tam olarak üç canlı komşusu varsa canlanır.

Her ne kadar bu algoritmanın bir çok uygulaması varsa da, bizim baba-kız oyunumuzda kullanacağım harita üretim algoritmasını anlayarak geliştirebilme adına bir tane de ben yazdım.

Hayat Oyunu
Hayat Oyunu

Uygulama Python 3 ile geliştirildi, sonraki aşamalarda testi kolaylaştırmak adına grid üzerinde canlı / ölü hücre ekleme ve hem başlangıç durumunu hem de mevcut durumu kaydedip, yükleme özelliğine sahip.

Kaynak kodlarına https://github.com/ctengiz/pygol adresinden ulaşabilirsiniz.

Hala daha hem Ilgın’ın hem de benim yapacak çok işimiz var. Ilgın hikayeyi tamamlayacak, ben de kodlayacağım. Gelişmeleri paylaşmaya devam edeceğiz…