Para um sistema de autômatos celulares, é necessário
que se tenha uma geometria regular.
A geometria do sistema pode ser classificada quanto a dois pontos: a dimensão e o formato da célula. A seguir, encontram-se os sub-tipos mais freqüentes de cada aspeto.
Dimensão
Podemos ter um autômato celular de uma, duas ou três dimensões. No autômato unidimensional, as células estão distribuídas linearmente. No bidimensional, teremos uma distribuição no plano e no tridimensional, uma distribuição espacial.
Esquemas de autômatos de dimensões diferentes:
Formato da célula
As células podem ter de várias formas(triangular, quadrangular, hexagonal, etc), desde que num mesmo autômato todas as células sejam de uma mesma forma.
Esquemas de autômatos com algumas formas de células:
É necessário também especificar quais serão
os vizinhos de uma célula, pois as regras de transição
serão aplicadas baseadas nos estados deles e da própria célula.
Há algumas formas de vizinhança que seguem uma lógica
ou regra (von neumann e moore) e há formas que são arbitrárias.
Na figura abaixo, as células de cinza escuro estão representando as vizinhas da célula preta. (e r é o raio da vizinhança)
Geralmente há uma necessidade de que o autômato seja
infinito em todas as dimensões, mas é impossível que
isso seja implementado em um computador (por limitação de
espaço de memória), então precisamos determinar condições
de limite para que possamos simular um autômato infinito. Estas condições
de limite indicam como o autômato se encontra além do seu
limite. Estas condições são também necessárias
para completar o conjunto de vizinhos das células que se encontram
nas bordas do autômato.
Por exemplo: as células que se encontram na extremidade esquerda não terão vizinhos à sua esquerda. A condição de limite irá justamente simular o comportamento daquelas células que na verdade não existem.
Há vários tipos de condições de limite,
das quais citaremos três delas:
Limite periódico
São obtidos periodicamente estendendo-se o autômato. É como se autômato fosse copiado nas bordas, da maneira como ele se encontra num dado instante. Para um ganho de tempo e memória, não precisamos colocar o autômato inteiro, basta colocarmos um pedaço dele (que são as r colunas ou r linhas mais próximas, e r é o raio da vizinhança).
Esquema de um autômato
unidimensional com raio de vizinhança 1 e condição
de contorno periódica:
Limite reflexivo
Esta condição de contorno é obtida refletindo-se o autômato em cada limite.
Esquema de um autômato unidimensional com raio de vizinhança 2 e condição de contorno reflexiva:
Limites de valores fixos
Esta condição de limite é obtida, simplesmente
descrevendo como serão os estados das células no contorno
do autômato, e estes estados serão os mesmos em qualquer instante
da simulação. Por exemplo, se um autômato tem 2 estados
possíveis para uma célula, PRETO e BRANCO, podemos determinar
uma condição de limite onde todas as células no contorno
são BRANCAS, como se vê na figura abaixo.
Um outro ponto importante na implementação de uma
sistema de autômatos celulares é a condição
em que o sistema se encontra no tempo inicial (t0). Dependendo
de como o sistema seja iniciado, diferentes evoluções são
obtidas. Dependendo do caso, podem ser obtidos padrões que permanecem
constantes indeterminadamente, que se anulam, ou que permanecem num estado
aparentemente aleatório. Essa característica importante pode
ser visualizada no applet (http://www.cin.ufpe.br/~if114/Monografias/Automatos Celulares/exemplo.htm)
do exemplo do jogo da vida.
Todo autômato celular deve ter um conjunto de estados, que
serão os possíveis estados em que as células poderão
se encontrar. Por exemplo, o conjunto de estados pode ser um conjunto de
cores (preto, branco e azul), uma certa propriedade (ligado e desligado),
etc. Cada célula poderá encontrar-se em apenas um estado,
e em qualquer instante, algum estado pode não ocorrer no autômato.
Por exemplo: Digamos que o conjunto de estados sejam as cores AZUL, VERMELHO, VERDE e PRETO. Então uma célula só poderá estar com apenas uma destas cores e alguma cor pode não ocorrer em nenhuma célula deste autômato.
Uma possível configuração de um autômato unidimensional com o conjunto de estados citado acima.
É interessante que este conjunto de estados seja tão menor quanto possível, pois o número de elementos da tabela de regras cresce exponencialmente , isto é, é proporcional a #S(v+1), onde #S é a cardinalidade do conjunto de estados e v é o número de vizinhos que uma célula possui, e um elemento da tabela de regras é uma (v+2)-tupla, contendo o estado de uma célula os estados dos seus vizinhos e o estado final(o novo estado daquela célula). O estado final não importa neste cálculo, pois é tido como a saída de uma função (função de transição de estados), então só devemos considerar os dados de entrada desta função.