Conway's Game of life - Parte II

No post anterior, começamos a programar o jogo da vida (Conway's Game of life). Você pode ler aqui a Parte I. Vamos dar continuidade à nossa implementação.

Já construímos a função que calcula o número de vizinhos de cada célula no estado atual. Dados o estado atual e o número de vizinhos, precisamos aplicar as regras do jogo. Vamos relembrá-las:

1. Qualquer célula viva com menos de dois vizinhos vivos morre de solidão.
2. Qualquer célula viva com mais de três vizinhos vivos morre de superpopulação.
3. Qualquer célula morta com exatamente três vizinhos vivos se torna uma célula viva.
4. Qualquer célula viva com dois ou três vizinhos vivos continua no mesmo estado para a próxima geração.

Vamos criar uma nova matriz, chamada de novo_estado, em que representa a configuração do jogo no próximo passo. Inicialmente, essa matriz será igual a matriz do estado atual:

  novo_estado = estado_atual;

Agora, para cada célula, as regras de (1) a (4) acima citadas devem ser aplicadas. Primeiro, verificamos se a célula está viva ou morta:

  if(estado_atual[i,j]==0){ #celula morta
    ...
  }else{ #celula viva
    ...
  }

Se a célula está morta, aplicamos a regra (3), caso contrário, aplicamos as restantes. Dessa forma, temos o seguinte código:

  if(estado_atual[i,j]==0){ #celula morta
    if(vizinhos[i,j]==3) novo_estado[i,j] = 1;
  }else{ #celula viva
    if(vizinhos[i,j] < 2 || vizinhos[i,j] > 3) novo_estado[i,j] = 0;
  }

Note que não precisamos implementar os casos em que a célula está morta e continua morta ou está viva e continua viva. Isso porque a matriz de novo estado é inicializada com os valores da matriz de estado atual. Se iniciássemos a matriz de novo estado completa de zeros, por exemplo, precisaríamos fazer essas trocas e, consequentemente, nosso algoritmo perderia eficiência.

Podemos colocar nosso código dentro de uma função (o que é recomendável):

  proximo_estado = function(estado_atual,vizinhos){
    ncol_ = ncol(estado_atual);
    nrow_ = nrow(estado_atual);
    novo_estado = estado_atual;

    for(i in 1:nrow_){
      for(j in 1:ncol_){
        if(estado_atual[i,j]==0){ #celula morta
          if(vizinhos[i,j]==3) novo_estado[i,j] = 1;
        }else{
          if(vizinhos[i,j]<2 || vizinhos[i,j]>3) novo_estado[i,j] = 0;
        }
      }
    }
    return(novo_estado);
  }

Nosso jogo, tecnicamente, está pronto. Demos um passo inicial para o algoritmo, calculamos os vizinhos e implementamos o novo estado. Vamos verificar se funciona? Vamos utilizar uma gride de 6 por 6.

ncol_ = 6;
nrow_ = 6;
estado_atual = matrix(0,ncol=ncol_,nrow=nrow_)

pop2 = expand.grid(1:3,2:5)
estado_atual[pop2[,1],pop2[,2]] = 1
vizinhos = calcula_vizinhos(estado_atual)
novo_estado = proximo_estado(estado_atual,vizinhos);

> estado_atual
     [,1] [,2] [,3] [,4] [,5] [,6]
[1,]    0    1    1    1    1    0
[2,]    0    1    1    1    1    0
[3,]    0    1    1    1    1    0
[4,]    0    0    0    0    0    0
[5,]    0    0    0    0    0    0
[6,]    0    0    0    0    0    0
> vizinhos
     [,1] [,2] [,3] [,4] [,5] [,6]
[1,]    2    3    5    5    3    2
[2,]    3    5    8    8    5    3
[3,]    2    3    5    5    3    2
[4,]    1    2    3    3    2    1
[5,]    0    0    0    0    0    0
[6,]    0    0    0    0    0    0
> novo_estado
     [,1] [,2] [,3] [,4] [,5] [,6]
[1,]    0    1    0    0    1    0
[2,]    1    0    0    0    0    1
[3,]    0    1    0    0    1    0
[4,]    0    0    1    1    0    0
[5,]    0    0    0    0    0    0
[6,]    0    0    0    0    0    0

Na figura abaixo, vemos o estado atual (esquerda) e o novo estado (direita).

Para executar o próximo passo do jogo da vida, o novo estado vira o estado atual e procedemos da mesma forma, isto é:

estado_atual = novo_estado;
vizinhos = calcula_vizinhos(estado_atual);
novo_estado = proximo_estado(estado_atual,vizinhos);

A figura abaixo representa os próximos dois passos do algoritmo:

Nosso código está funcionando! O próximo passo é implementar uma forma de o algoritmo fazer alguns passos sem precisarmos rodar o bloco de código manualmente a cada passo. Para n passos, é fácil: basta colocar o código em uma estrutura de repetição que irá executar n vezes. Mas e se quisermos ter controle da execução, por exemplo, apertar Enter para o algoritmo executar até ficarmos satisfeitos e depois parar a execução? Esse problema é parecido com o do post de preencher retângulos no plot (que você pode ver aqui), mas vamos abordá-lo no próximo post.

Até a próxima aula!