villares
commented
2 years ago Salvei @fabi-costa!
Este PR fico um puco confuso, misturou tudo (eu provavelmente não sei o que estou fazendo) mas eu dei merge :)
Agora esse texto que você preparou é tradução do Shiffman, certo? Vamos por ele em uma página separada?
Atualize o seu fork (com o botão do fetch, ou apague e recrie o fork) crie um branch separado e crie nele um arquivo automatos-celulares.md para o texto...
Um autômato celular (CA) é um modelo de um sistema de objetos "celulares" com as seguintes características:
- As células vivem em uma grade. (Os exemplos a seguir serão em uma e duas dimensões neste capítulo, embora um autômato celular possa existir em qualquer número finito de dimensões.)
- Cada célula tem um estado. O número de possibilidades de Estado é tipicamente finito. O exemplo mais simples tem as duas possibilidades de 1 e 0 (também referidas como "on" e "off" ou "viva" e "morta").
- Cada célula tem um bairro. Isso pode ser definido de várias maneiras, mas é tipicamente uma lista de células adjacentes.
Autômato Celular Elementar
Os exemplos neste capítulo começarão com uma simulação do trabalho de Wolfram. Para entender o CA elementar de Wolfram, devemos nos perguntar: "Qual é o autômato celular mais simples que podemos imaginar?" O que é emocionante sobre essa pergunta e sua resposta é que, mesmo com o CA mais simples imaginável, veremos as propriedades de sistemas complexos em ação. Quais são os três elementos-chave de um CA?
1) Grade. A grade mais simples seria unidimensional: uma linha de células.
2) Estados. O conjunto mais simples de estados (além de ter apenas um estado) seriam dois estados: 0 ou 1.
3) Bairro. O bairro mais simples em uma dimensão para qualquer célula seria a própria célula e seus dois vizinhos adjacentes: um para a esquerda e outro para a direita.
Então começamos com uma linha de células, cada uma com um estado inicial (digamos que é aleatório), e cada uma com dois vizinhos. Teremos que descobrir o que queremos fazer com as células nas bordas (já que elas têm apenas um vizinho cada), mas isso é algo que podemos resolver mais tarde.
Ainda não discutimos, no entanto, qual é talvez o detalhe mais importante de como os autômatos celulares funcionam: o tempo. Não estamos realmente falando sobre o tempo real aqui, mas sobre o CA viver durante um período de tempo, que também poderia ser chamado de geração e, no nosso caso, provavelmente se referirá à contagem de quadros de uma animação. Os números acima nos mostram que o CA no momento é igual a 0 ou geração 0. As perguntas que temos que nos fazer são: Como calcular os estados para todas as células da geração 1? E geração 2? E assim por diante.
Digamos que temos uma célula individual no AC, e vamos chamá-la de CELL. A fórmula para calcular o estado do CELL a qualquer momento t é a seguinte:
Estado celular no tempo t = f(bairro cell no tempo t - 1)
Em outras palavras, o novo estado de uma célula é uma função de todos os estados do bairro da célula no momento anterior (ou durante a geração anterior). Calculamos um novo valor estatal olhando para todos os estados vizinhos anteriores.
Agora, no mundo dos autômatos celulares, há muitas maneiras de calcular o estado de uma célula a partir de um grupo de células. O novo estado de um pixel (ou seja, sua cor) é a média de todas as cores de seus vizinhos. Com o CA elementar de Wolfram, no entanto, podemos realmente fazer algo um pouco mais simples e aparentemente absurdo: Podemos olhar para todas as configurações possíveis de uma célula e seu vizinho e definir o resultado do estado para cada configuração possível.
Temos três células, cada uma com um estado de 0 ou 1. De quantas maneiras possíveis podemos configurar os estados? Se você ama binário, você notará que três células definem um número de 3 bits, e quão alto você pode contar com 3 bits? Até 8.
Uma vez definidos todos os bairros possíveis, precisamos definir um resultado (novo valor estadual: 0 ou 1) para cada configuração do bairro.
O modelo wolfram padrão é começar a geração 0 com todas as células tendo um estado de 0, exceto para a célula média, que deve ter um estado de 1.
Referindo-se ao ruleset acima, vamos ver como uma determinada célula (vamos escolher a central) mudaria de geração 0 para geração 1.
Tente aplicar a mesma lógica em todas as células acima e preencha as células vazias. Agora, vamos passar de apenas uma geração e colorir as células — 0 significa branco, 1 significa preto — e empilhar as gerações, com cada nova geração aparecendo abaixo da anterior.
A forma de baixa resolução que estamos vendo acima é o "triângulo Sierpiński". Nomeado em homenagem ao matemático polonês Wacław Sierpiński, é um padrão fractal que examinaremos no próximo capítulo. Isso mesmo: este sistema incrivelmente simples de 0s e 1s, com pequenos bairros de três células, pode gerar uma forma tão sofisticada e detalhada quanto o triângulo Sierpiński. Vamos olhar para ele novamente, apenas com cada célula um único pixel de largura para que a resolução seja muito maior.
Este resultado em particular não aconteceu por acidente. Eu escolhi este conjunto de regras por causa do padrão que ele gera. Dê uma olhada na Figura 7.8 mais uma vez. Observe como existem oito configurações possíveis de bairro; por isso, definimos um "ruleset" como uma lista de 8 bits.
Assim, esta regra em particular pode ser ilustrada da seguinte forma:
Oito 0s e 1s significa um número de 8 bits. Quantas combinações de oito 0s e 1 existem? 256. É assim como definimos os componentes de uma cor RGB. Temos 8 bits para vermelho, verde e azul, o que significa que fazemos cores com valores de 0 a 255 (256 possibilidades).
O Jogo da Vida
Tendo como base o conceito de autômatos celulares, vamos compor o Jogo da Vida, que é o princípio do Campo Minado e de simulações de crescimento de bactérias.
Primeiro, é necessário criar um "tabuleiro", ou um campo. Esse campo vai atender dois valores: 0 e 1, ou "vivo" e "morto"
tam = 20 board = [] def setup(): global n_colunas, n_linhas size(500, 500) stroke(255, 0, 0) n_colunas = int(width / tam) # calcula numeto de colunas n_linhas = int(height / tam) # calcula numero de linhas
ivnentando o tabuleiro
for _ in range(n_colunas): board.append([0] * n_linhas) # jogando uma coluna para dentro
sorteando algumas celulas vivas (posição com valor 1)
for c in range(n_colunas): # 0, 1, 2, ... n_colunas - 1 for l in range(n_linhas): # 0, 1, 3, ... n_colunas - 1 if random(100) < 15: board[c][l] = 1 def draw(): background(0, 0, 100) for c in range(n_colunas): # sequência de números para colunas for l in range(n_linhas): if board[c][l] == 1: fill(255) rect(c tam, l tam, tam, tam) fill(255, 0, 0) text(vizinhos_vivos(c, l), c tam + tam / 2, l tam + tam / 2)
é uma grade que começamos a desenhar
def vizinhos_vivos(i, j): viz = ((-1, -1), (-1, 0), (-1, -1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)) vivos = 0 for oi, oj in viz: estado_vizinha = board[(i + oi) % n_colunas][(j + oj) % n_linhas] vivos = vivos + estado_vizinha return vivos
Para entender melhor, basta analisar a imagem a seguir. O zero central (com fundo branco) é uma célula 'viva', mas que não possui células vivas ao seu redor (por isso o valor zero). As células ao seu redor são células 'mortas' que sinalizam que tem uma ou duas células vivas.
Agora, para entender melhor como funcionam as gerações anteriormente citadas, no código a seguir, têm-se uma geração 0, que consecutivamente forma uma nova geração (geração 1), que formará uma outra, e assim por diante.
tam = 5 # cria variavel global tam (tamanho das celulas) board = [] # lista vazia que vai ser o tabuleiro def setup(): global n_colunas, n_linhas size(600, 600)
stroke(255, 0, 0) # cor de traço
n_colunas = int(width / tam) # calcula numero de colunas n_linhas = int(height / tam) # calcula numero de linhas
inventando o tabuleiro
for _ in range(n_colunas): board.append([0] * n_linhas) # jogando uma coluna pra dentro
sorteando algumas celulas vivas (posição com valor 1)
for c in range(n_colunas): # 0, 1, 2, ... n_colunas - 1 for l in range(n_linhas): # 0, 1, 3, ... n_linhas - 1 if random(100) < 15: board[c][l] = 1 def draw(): background(0, 0, 100) for c in range(n_colunas): for l in range(n_linhas): if board[c][l] == 1: fill(255) rect(c tam, l tam, tam, tam)
fill(255, 0, 0)
text(vizinhos_vivos(c, l),
c tam + tam / 2, l tam + tam / 2)
if frameCount % 5 == 0: # 1, 2, 3, 4, 5, 6, 7, atualizar_tabuleiro() def atualizar_tabuleiro(): global board nextboard = [] for in range(n_colunas): next_board.append([0] * n_linhas) for c in range(n_colunas): for l in range(n_linhas): vivos = vizinhos_vivos(c, l) if vivos == 3: next_board[c][l] = 1 elif vivos < 2 or vivos > 3: next_board[c][l] = 0 else: next_board[c][l] = board[c][l] board = next_board def vizinhos_vivos(i, j): viz = ((-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)) vivos = 0 for oi, oj in viz: estado_vizinha = board[(i + oi) % n_colunas][(j + oj) % n_linhas] vivos = vivos + estado_vizinha return vivos
BIBLIOGRAFIA SHIFFMAN, Daniel. Cellular Automata. In: https://natureofcode.com/book/chapter-7-cellular-automata/.
Um autômato celular (CA) é um modelo de um sistema de objetos "celulares" com as seguintes características:
As células vivem em uma grade. (Os exemplos a seguir serão em uma e duas dimensões neste capítulo, embora um autômato celular possa existir em qualquer número finito de dimensões.)
Cada célula tem um estado. O número de possibilidades de Estado é tipicamente finito. O exemplo mais simples tem as duas possibilidades de 1 e 0 (também referidas como "on" e "off" ou "viva" e "morta").
Cada célula tem um bairro. Isso pode ser definido de várias maneiras, mas é tipicamente uma lista de células adjacentes.
Autômato Celular Elementar
Os exemplos neste capítulo começarão com uma simulação do trabalho de Wolfram. Para entender o CA elementar de Wolfram, devemos nos perguntar: "Qual é o autômato celular mais simples que podemos imaginar?" O que é emocionante sobre essa pergunta e sua resposta é que, mesmo com o CA mais simples imaginável, veremos as propriedades de sistemas complexos em ação. Quais são os três elementos-chave de um CA?
1) Grade. A grade mais simples seria unidimensional: uma linha de células.
2) Estados. O conjunto mais simples de estados (além de ter apenas um estado) seriam dois estados: 0 ou 1.
3) Bairro. O bairro mais simples em uma dimensão para qualquer célula seria a própria célula e seus dois vizinhos adjacentes: um para a esquerda e outro para a direita.
Então começamos com uma linha de células, cada uma com um estado inicial (digamos que é aleatório), e cada uma com dois vizinhos. Teremos que descobrir o que queremos fazer com as células nas bordas (já que elas têm apenas um vizinho cada), mas isso é algo que podemos resolver mais tarde.
Ainda não discutimos, no entanto, qual é talvez o detalhe mais importante de como os autômatos celulares funcionam: o tempo. Não estamos realmente falando sobre o tempo real aqui, mas sobre o CA viver durante um período de tempo, que também poderia ser chamado de geração e, no nosso caso, provavelmente se referirá à contagem de quadros de uma animação. Os números acima nos mostram que o CA no momento é igual a 0 ou geração 0. As perguntas que temos que nos fazer são: Como calcular os estados para todas as células da geração 1? E geração 2? E assim por diante.
Digamos que temos uma célula individual no AC, e vamos chamá-la de CELL. A fórmula para calcular o estado do CELL a qualquer momento t é a seguinte:
Estado celular no tempo t = f(bairro cell no tempo t - 1)
Em outras palavras, o novo estado de uma célula é uma função de todos os estados do bairro da célula no momento anterior (ou durante a geração anterior). Calculamos um novo valor estatal olhando para todos os estados vizinhos anteriores.
Agora, no mundo dos autômatos celulares, há muitas maneiras de calcular o estado de uma célula a partir de um grupo de células. O novo estado de um pixel (ou seja, sua cor) é a média de todas as cores de seus vizinhos. Com o CA elementar de Wolfram, no entanto, podemos realmente fazer algo um pouco mais simples e aparentemente absurdo: Podemos olhar para todas as configurações possíveis de uma célula e seu vizinho e definir o resultado do estado para cada configuração possível.
Temos três células, cada uma com um estado de 0 ou 1. De quantas maneiras possíveis podemos configurar os estados? Se você ama binário, você notará que três células definem um número de 3 bits, e quão alto você pode contar com 3 bits? Até 8.
Uma vez definidos todos os bairros possíveis, precisamos definir um resultado (novo valor estadual: 0 ou 1) para cada configuração do bairro.
O modelo wolfram padrão é começar a geração 0 com todas as células tendo um estado de 0, exceto para a célula média, que deve ter um estado de 1.
Referindo-se ao ruleset acima, vamos ver como uma determinada célula (vamos escolher a central) mudaria de geração 0 para geração 1.
Tente aplicar a mesma lógica em todas as células acima e preencha as células vazias. Agora, vamos passar de apenas uma geração e colorir as células — 0 significa branco, 1 significa preto — e empilhar as gerações, com cada nova geração aparecendo abaixo da anterior.
A forma de baixa resolução que estamos vendo acima é o "triângulo Sierpiński". Nomeado em homenagem ao matemático polonês Wacław Sierpiński, é um padrão fractal que examinaremos no próximo capítulo. Isso mesmo: este sistema incrivelmente simples de 0s e 1s, com pequenos bairros de três células, pode gerar uma forma tão sofisticada e detalhada quanto o triângulo Sierpiński. Vamos olhar para ele novamente, apenas com cada célula um único pixel de largura para que a resolução seja muito maior.
Este resultado em particular não aconteceu por acidente. Eu escolhi este conjunto de regras por causa do padrão que ele gera. Dê uma olhada na Figura 7.8 mais uma vez. Observe como existem oito configurações possíveis de bairro; por isso, definimos um "ruleset" como uma lista de 8 bits.
Assim, esta regra em particular pode ser ilustrada da seguinte forma:
Oito 0s e 1s significa um número de 8 bits. Quantas combinações de oito 0s e 1 existem? 256. É assim como definimos os componentes de uma cor RGB. Temos 8 bits para vermelho, verde e azul, o que significa que fazemos cores com valores de 0 a 255 (256 possibilidades).
O Jogo da Vida
Tendo como base o conceito de autômatos celulares, vamos compor o Jogo da Vida, que é o princípio do Campo Minado e de simulações de crescimento de bactérias.
Primeiro, é necessário criar um "tabuleiro", ou um campo. Esse campo vai atender dois valores: 0 e 1, ou "vivo" e "morto"
Para entender melhor, basta analisar a imagem a seguir. O zero central (com fundo branco) é uma célula 'viva', mas que não possui células vivas ao seu redor (por isso o valor zero). As células ao seu redor são células 'mortas' que sinalizam que tem uma ou duas células vivas.
Agora, para entender melhor como funcionam as gerações anteriormente citadas, no código a seguir, têm-se uma geração 0, que consecutivamente forma uma nova geração (geração 1), que formará uma outra, e assim por diante.
BIBLIOGRAFIA SHIFFMAN, Daniel. Cellular Automata. In: https://natureofcode.com/book/chapter-7-cellular-automata/.