Um autômato celular é um sistema que consiste em células com valores numéricos em uma grade, além de regras que determinam o comportamento dessas células. Aplicando repetidamente a regra a cada célula da grade em paralelo com a visualização da grade, é possível obter o efeito de um determinado organismo em evolução com comportamento complexo e intricado, mesmo que as regras sejam relativamente simples.
Os autômatos celulares têm várias formas, tipos e dimensões. Provavelmente o autômato celular mais famoso é o Jogo da Vida de Conway (GOL). Consiste em uma grade bidimensional na qual cada célula contém um valor binário (vivo ou morto). As regras que acompanham, com base no estado das células vizinhas, determinam se a célula deve estar morta ou viva. As regras dizem que uma célula viva morre de solidão se houver menos de duas células vivas ao seu redor. Se mais de três células vizinhas estiverem vivas, ela morre de superpopulação. Em outras palavras, uma célula "sobrevive" se houver exatamente 2 ou 3 células vizinhas vivas ao seu redor. Para que uma célula
morta ganhe vida, ela deve ter exatamente 3 células vizinhas vivas, caso contrário ela permanece morta. Um exemplo de uma máquina GoL que itera através de vários estados é mostrado abaixo.
Outra versão famosa do autômato celular é unidimensional; é chamado de autômato celular elementar (ECA). É isso que estamos implementando neste post.
Cada estado desse autômato é armazenado como uma matriz unidimensional de valores booleanos e, embora sejam necessárias duas dimensões para visualizar o estado GOL, um autômato de valores é suficiente para esse autômato. Graças a isso, podemos usar duas dimensões (em vez de animação) para visualizar todo o histórico dos estados desse autômato. Como no caso da GOL, o estado da célula nesta máquina é 0 ou 1, mas, diferentemente da célula GOL, que é atualizada dependendo de seus 8 vizinhos, a célula ECA é atualizada com base no estado do vizinho esquerdo, vizinho direito e ele próprio!
Exemplos de regras são mostrados abaixo: as três principais células são a entrada da regra e a inferior é a saída, onde preto é 1 e branco é 0. Além disso, podemos ver os padrões gerados por cada uma delas, quando o estado inicial é todo 0, exceto 1 na célula do meio.
Você pode se perguntar: por que as regras apresentadas acima são indicadas por números? Como cada número no intervalo de 0 a 255 corresponde diretamente à regra do ECA e, portanto, esses números são usados como os nomes das regras. Esta correspondência é mostrada abaixo:
Do número à regraQualquer número no intervalo de 0 a 255 pode ser representado em formato binário com apenas 8 dígitos (primeira seta acima). Além disso, podemos atribuir a cada um desses números um índice com base em sua localização (segunda seta). Naturalmente, esses índices estão no intervalo de 0 a 7, ou seja, podem ser representados na forma binária usando apenas 3 dígitos (terceira seta). Interpretando esses 3 dígitos como entrada e o dígito correspondente do número original como saída, obtemos a função ternária de que precisamos (quarta seta).
Geração de regras
Vamos implementar a interpretação acima como uma função de ordem superior
get_rule que recebe um número de 0 a 255 como entrada e retorna uma regra ECA correspondente a esse número.
Precisamos criar algo assim:
const rule30 = get_rule(30); const output110 = rule30(1, 1, 0);
No exemplo acima, a
rule30(1,1,0) inicial
rule30(1,1,0) combinará todos os três valores binários em um número (110 = 6) e retornará um pouco nessa posição (6) na representação binária 30. O número 30 na representação binária é 00011110, portanto, a função retornará 0 (contamos à direita e iniciamos a contagem de 0).
Sabendo que as três variáveis de entrada binárias serão combinadas em um número, vamos começar implementando essa função de
combine .
const combine = (b1, b2, b3) => (b1 << 2) + (b2 << 1) + (b3 << 0);
Tendo mudado os argumentos para as posições correspondentes à esquerda e, em seguida, somando os três números deslocados, obtemos a combinação desejada.
A segunda parte importante da função
get_rule é determinar o valor do bit em uma posição específica em um número. Portanto, vamos criar uma função
get_bit(num, pos) , que pode retornar um valor de bit em uma determinada posição
pos em um determinado número
num . Por exemplo, o número 141 no formato binário é 10001101, portanto,
get_bit(2, 141) deve retornar
1 e
get_bit(5, 141) deve retornar
0 .
A função
get_bit(num,pos) pode ser implementada executando primeiro um deslocamento de bit do número por
pos para a direita e, em seguida, executando a operação bit a bit "AND" com o número 1.
const get_bit = (num, pos) => (num >> pos) & 1;
Agora só precisamos combinar essas duas funções:
const get_rule = num => (b1, b2, b3) => get_bit(num, combine(b1, b2, b3));
Ótimo! Portanto, temos uma função que para cada número dentro do nosso intervalo nos fornece uma regra ECA única com a qual podemos fazer qualquer coisa. O próximo passo é renderizá-los no navegador.
Visualização de Regras
Para renderizar autômatos no navegador, usaremos o elemento
canvas . O
canvas pode ser criado e adicionado ao corpo html da seguinte maneira:
window.onload = function() { const canvas = document.createElement('canvas'); canvas.width = 800; canvas.height = 800; document.body.appendChild(canvas); };
Para poder interagir com a
canvas , precisamos de
contexto . O contexto nos permite desenhar formas e linhas, colorir objetos e geralmente navegar na
canvas . Ele é fornecido através do método
getContext de nossa
canvas .
const context = canvas.getContext('2d');
O parâmetro
'2d' refere-se ao tipo de contexto que usaremos neste exemplo.
Em seguida, criaremos uma função que, tendo o contexto, a regra ECA, bem como algumas informações sobre a escala e o número de células, desenhe a regra na
canvas . A idéia é gerar e desenhar uma grade linha por linha; A parte principal do código é mais ou menos assim:
function draw_rule(ctx, rule, scale, width, height) { let row = initial_row(width); for (let i = 0; i < height; i++) { draw_row(ctx, row, scale); row = next_row(row, rule); } }
Começamos com algum tipo de conjunto inicial de células, que é a linha atual. Essa linha, como nos exemplos acima, geralmente contém todos os zeros, com exceção de uma unidade na célula do meio, mas também pode conter uma linha completamente aleatória de 1 e 0. Nós desenhamos essa linha de células e usamos a regra para calcular a próxima linha de valores com base em linha atual. Em seguida, basta repetir o desenho e calcular as novas etapas até descobrirmos que a grade é alta o suficiente.
Para o trecho de código acima, precisamos implementar três funções:
draw_row ,
draw_row e
next_row .
initial_row é uma função simples. Ele cria uma matriz de zeros e altera o elemento no centro da matriz em um.
function initial_row(length) { const initial_row = Array(length).fill(0); initial_row[Math.floor(length / 2)] = 1; return initial_row; }
Como já temos uma função de regra, a função
next_row pode consistir em uma linha. O valor de cada célula em uma nova linha é o resultado da aplicação da regra com os valores das células mais próximas e a linha antiga é usada como entrada.
const next_row = (row, rule) => row.map((_, i) => rule(row[i - 1], row[i], row[i + 1]));
Você notou que traímos essa linha? Cada célula em uma nova linha requer entrada de outras três células, mas duas células nas bordas da linha recebem dados de apenas duas. Por exemplo,
next_row[0] tenta obter o valor de
next_row[0] da
row[-1] . Isso ainda funciona porque, ao tentar acessar valores por índices que não estão na matriz, o javascript retorna
undefined , e acontece que
(undefined >> [ ]) (da função de
combine ) sempre retorna 0. Isso significa que, na realidade, processamos cada valor fora da matriz como 0.
Sei que isso é feio, mas em breve criaremos algo bonito na tela, para que possamos ser perdoados.
Em seguida, vem a função
draw_row ; é ela quem realiza a renderização!
function draw_row(ctx, row, scale) { ctx.save(); row.forEach(cell => { ctx.fillStyle = cell === 1 ? '#000' : '#fff'; ctx.fillRect(0, 0, scale, scale); ctx.translate(scale, 0); }); ctx.restore(); ctx.translate(0, scale); }
É aqui que somos muito dependentes do objeto de contexto, usando pelo menos 5 métodos diferentes dele. Aqui está uma breve lista e como usá-los.
fillStyle indica como queremos preencher as formas. Pode ser uma cor, por exemplo, "#f55" , bem como um gradiente ou padrão. Usamos esse método para separar visualmente as células 0 das células 1.fillRect(x, y, w, h) desenha um retângulo a partir de um ponto (x, y) com largura w e altura h, preenchidos de acordo com fillStyle . Nossos retângulos são quadrados simples, mas você pode se surpreender que o ponto de partida de todos eles esteja na origem. Isso aconteceu porque usamos esse método em combinação com o translate .translate(x, y) permite mover todo o sistema de coordenadas. A posição é salva, portanto, o método é uma excelente alternativa para rastrear diferentes posições dos elementos. Por exemplo, em vez de calcular a posição de cada célula da grade individual, podemos simplesmente desenhar uma célula, mover para a direita, desenhar uma nova célula e assim por diante.save() e restore() são usados em conjunto com translate e outros métodos de conversão de coordenadas. Nós os usamos para salvar o sistema de coordenadas atual em um determinado ponto, para que mais tarde possamos retornar a ele (usando a restauração ). Nesse caso, salvamos o sistema de coordenadas antes de renderizar a linha e a movemos para a direita. Então, quando terminamos de desenhar a linha e percorremos todo o caminho para a direita, as coordenadas são restauradas e retornamos ao estado original. Então descemos para nos preparar para desenhar a próxima linha.
Agora temos todas as partes necessárias para a função
draw_rule . Usamos essa função em
window.onload após preparar a
canvas . Também determinaremos os parâmetros que precisamos.
window.onload = function() { const width = 1000;
Extraímos as dimensões da
canvas como variáveis separadas, juntamente com o número de células horizontalmente. Em seguida, computamos
cell_scale e 'cells_down' para que a grade preencha toda a
canvas , enquanto as células permanecem quadradas. Graças a isso, podemos alterar facilmente a "resolução" da grade, permanecendo dentro da
canvas .
Isso é tudo! O exemplo de código completo está no
github e no
codepen :
Seguindo em frente
Graças a esse sistema, poderemos examinar uma após a outra todas as 256 regras, iterativamente, alterando o código ou escolhendo um número de regra aleatoriamente a cada carregamento da página. Seja como for, é muito empolgante estudar todos esses resultados imprevisíveis em nosso ambiente controlado.
Você também pode tornar aleatório o estado inicial das células do autômato, em vez dos "zeros sólidos e uma unidade" estáticos. Portanto, obtemos resultados ainda mais imprevisíveis. Esta versão da função
initial_row pode ser escrita assim:
function random_initial_row(width) { return Array.from(Array(width), _ => Math.floor(Math.random() * 2)); }
Abaixo, você vê o quanto essa alteração na linha de saída tem um grande impacto na saída.
String de origem aleatóriaE este é apenas um aspecto que você pode mudar! Por que limitar-se a apenas duas condições? (A transição de 2 para 3 estados aumenta o número de regras de 256 para 7 625 597 484 987!) Por que limitar-se a quadrados? Por que apenas 2 dimensões? Por que apenas uma regra de cada vez?
Exemplos de visualizações baseadas no ECA são mostrados abaixo, mas com uma função
draw_rule alternativa que
draw_rule linhas não com quadrados, mas com um padrão isométrico e, em seguida, preenche as áreas definidas por essas linhas com cores. Você nem precisa exibir linhas divisórias e apenas mostrar cores.
Se você for ainda mais longe, poderá adicionar simetrias axiais (linha do meio) e espelho (linha de baixo).
Se essas visualizações pareciam interessantes para você, mas estude
essa caixa de proteção interativa , ou melhor ainda, comece com o código que criamos e tente criar seus próprios autômatos celulares!
Boa sorte