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…

Bottlepy + Nginx + Uwsgi + Python3 with Virtualenv on Debian

Bottle is my favorite micro web framework for  python.  It is well designed, allows quick prototyping and also developing web based applications.

My preferred web application stack is bottle + nginx + uwsgi + firebird + debian.

So this is my brief tutorial for this stack :

Install required packages :

Prepare web files directory structure for nginx :

Let’s create our virtualenv for our applications. I prefer placing my virtaulenvs in opt directory :

Time to activate our virtualenv and install bottle :

To create our simple demo application :

And code of our simple demo application :

Let’s check if everything is working so far :

If your output is similar to below output then everything is well so far. When you locate to http://localhost:8081, your browser should say “hello” to you.

Now we can safely deactivate our virtualenv,

and start nginx configuration, first we have to create a virtual host file for nginx :

content of the nginx virtualhost is :

to activate our virtualhost we symlink it to sites-enabled directory :

Now it is time to configure our uwsgi. First we create our uswgi appliaction configuration file :

bottledemo.ini content

and symlink to enabled applications :

last touches :

Mac Os X Python3 Virtualenv

Quick & dirty guide for myself :

[bash]
Cagatay-MacBook-Pro:virt cagataytengiz$ virtualenv -p /Library/Frameworks/Python.framework/Versions/3.3/bin/python3.3 p3
Cagatay-MacBook-Pro:virt cagataytengiz$ cd p3/
Cagatay-MacBook-Pro:p3 cagataytengiz$ source ./bin/activate
[/bash]

and then install required packages as :

 

Python development with NetBeans in Ubuntu 8.10

For a time I’ve been searching for a good python editor under Ubuntu. I’ve tried :

  • SPE : Does not work in Turkish Locale. Have set LC_ALL = C before running. Also not so good in editing in html, css and js
  • Eric : Somehow I could not feel comfortable with it.
  • Komodo Edit : Fine in editing multiple types files, but lacks many python editing features. Comprasion with Komodo IDE is here.
  • Eclipse : Far too complex for me.
  • Komodo IDE : Powerfull enough for editing css, js, html and python. It has good code completion support, and can debug python. Also has a good source browser. Bu it is commercial and somehow it seemed slow for me while editing files, changing editor windows.

So far the ideal editor was the Komodo IDE. But I have new a candidate : NetBeans ! An early access edition of Netbeans with Python support is released. It can be downloaded from here. It nearly have all the features that I want from an editor :

  • Code completion
  • A Usable and fast source browser
  • A usable directory browser
  • Debugging
  • Fast response in editor
  • Renaming / refactoring
  • Good code highlighting
  • Ability to edit html, js and css
  • jQuery support

And the additional features I’ve liked are :

  • A database browser. Comes very handy when developing db applications.
  • Ability to connect to Firebird through Firebird JDBC driver.
  • Very nice tips about coding style
  • Very fast startup time.

More detailed information is on the wiki of NetBeans.

To install NetBeans 6.5, first install sun java6 SDK which is in multiverse repositories :

sudo apt-get install sun-java6-jdk

Then download it, and make it executable and run 🙂