Cellular Automata in the Triangular Grid

Abstract

Cellular automata are parallel computing devices working on a discrete timescale. Each cell of a regular grid has a finite number of states and the state in the next time instant depends only on the actual state of the cell itself and the states of its neighbor cells. When every cell could have exactly two states, they can be identified as “live” and “dead” states. “Game of Life” is a very popular type of cellular automata on the square grid based on the 8 neighborhood of the cells. There are various initial configuration that leads to periodic or growing or moving patterns, etc. Triangular Grid which also called an isometric grid, is a grid generated by tiling the plane regularly with equilateral triangles. In the thesis, life like cellular automata are analyzed in the triangular gird based on 3-neighborhood relation that is the next state of a cell depends only on its actual state and the states of its closest neighbor cells. There are 2 sets of conditions. The first set is called “Birth” or “B” which shows the number of live cells needed in the neighborhood of a dead cell to make it alive. The second set is called “Stay alive” or “S” which shows the number of live cells needed in the neighborhood of a live cell to keep it alive. Various B/S models are analyzed. While some can generate patterns like snowflake or etc, some can be used for noise removal in image processing. Keywords: Cellular Automata, Game of Life, Triangular Grid

ÖZ : Hücresel otomatlar ayrık zaman çizelgesi üzerinde çalışan paralel hesaplama araçlarıdır. Düzenli kılavuzun her hücresinin sonlu sayıda „durum‟ u vardır ve gelecek zamandaki durum ancak hücrenin ve komşu hücrelerin şu anki durumlarına bağlıdır. Hücrenin sadece iki durumu bulunduğunda, bunlar „canlı‟ ve „ölü‟ olarak adlandırılırlar. „Hayat Oyunu‟ kare kılavuz üzerinde, hücrelerin 8 komşuluğuna dayalı çok popüler bir hücresel otomat çeşididir. Dönemli, büyüyen, veya hareket eden kalıpları yaratan değişik başlangıç ayarlamaları bulunur. Ügensel kılavuz, ya da farklı bir adıyla „eş‟ kılavuz, düzlemi düzenli şekilde eşkenar üçgenlerle döşeyerek elde edilir. Bu tezde 3‟lü komşuluk bağıntısına dayalı üçgensel kılavuz yaşam tarzı hücresel otomatlar analiz edilir. Öyle ki hücrenin bir sonraki durumu sadece kendisinin ve en yakınındaki komşu hücrelerin şu anki durumuna bağlıdır. Toplam 2 sonuç kümesi vardır. İlk kümenin adı „Doğum‟ ya da kısaca „D‟ dir ve bu küme ölü hücreyi canlandırmak için komşuluğunda ihtiyaç duyulan canlı hücre sayısını gösterir. İkinci kümenin adı ise „Hayatta Kal‟ veya kısaca „K‟ olmakla beraber, bu küme de canlı hücreyi canlı tutmak için gerekli olan komşuluğundaki canlı hücre sayısını temsil eder. Farklı D/K modelleri analiz edilir. Bunların bazıları kartanesi gibi desenler üretirken, bazıları da görüntü işleme alanında gürültü gidermek için kullanılır. Anahtar Kelimeler: Hücresel Otomatlar, Hayat Oyunu, Ügensel kılavuz