- Qualquer célula viva com menos de dois vizinhos vivos morre de solidão.
- Qualquer célula viva com mais de três vizinhos vivos morre de superpopulação.
- Qualquer célula morta com exatamente três vizinhos vivos se torna uma célula viva.
- Qualquer célula viva com dois ou três vizinhos vivos continua no mesmo estado para a próxima geração.
ncol_ = 11;
nrow_ = 11;
estado_atual = matrix(0,ncol=ncol_,nrow=nrow_)
A matriz estado_atual define qual o estado atual da simulação. No momento, não temos nenhuma célula viva. Temos que definir um valor inicial para o algoritmo.
pop1 = expand.grid(2:6,5:10)
estado_atual[pop1[,1],pop1[,2]] = 1
Dessa forma, informamos que as células da gride definidas em pop1 estão vivas. A Figura abaixo apresenta o estado inicial do nosso algoritmo, em que as células preenchidas representam as células vivas.
> estado_atual
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11]
[1,] 0 0 0 0 0 0 0 0 0 0 0
[2,] 0 0 0 0 1 1 1 1 1 1 0
[3,] 0 0 0 0 1 1 1 1 1 1 0
[4,] 0 0 0 0 1 1 1 1 1 1 0
[5,] 0 0 0 0 1 1 1 1 1 1 0
[6,] 0 0 0 0 1 1 1 1 1 1 0
[7,] 0 0 0 0 0 0 0 0 0 0 0
[8,] 0 0 0 0 0 0 0 0 0 0 0
[9,] 0 0 0 0 0 0 0 0 0 0 0
[10,] 0 0 0 0 0 0 0 0 0 0 0
[11,] 0 0 0 0 0 0 0 0 0 0 0
Isso ocorre porque eu defini que as linhas estariam representadas no eixo x e as colunas, no eixo y. É claro que você pode mudar isso, dependendo da visualização gráfica que quer. Para o algoritmo em si, não faz diferença, já que trabalhamos com as matrizes.
Dada a matriz com o estado inicial, precisamos calcular os vizinhos (vivos) de cada célula. Para isso, vamos contar os vizinhos de cada célula e armazenar esse informação em uma matriz de vizinhos, em que vizinhos[1,1] terá como valor o número de vizinhos da célula [1,1] da nossa gride. Vamos criar nossa matriz de vizinhos:
vizinhos = matrix(0,ncol=ncol_,nrow=nrow_)
Note que as algumas células possuem número de células adjacentes diferentes de outras. Por exemplo, a primeira célula da matriz [1,1] possui como células adjacentes as células [1,2], [2,1] e [2,2]. Já a célula [2,2] possui oito células adjacentes. Logo, a implementação da contagem de vizinhos vivos deve levar isso em conta. Então, temos que fazer essa computação com alguns cuidados:
- as células dos extremos da matriz possuem apenas 3 células adjacentes,
- as células das bordas da matriz (exceto os extremos) possuem 5 células adjacentes,
- as células do interior da matriz possuem 8 células adjacentes.
Para contar quantos vizinhos vivos cada célula possui, vamos utilizar uma estrutura de repetição. Utilizaremos um for duplo, ou seja, um dentro do outro. O primeiro percorrerá as linhas da matriz e o segundo, as colunas:
for(i in 1:nrow_){
for(j in 1:ncol_){
...
}
}
Logo, i indica a linha atual e j indica a coluna atual. Usaremos essas variáveis para acessar a matriz de estado atual e computar os vizinhos vivos da célula [i,j].
Para as células do interior da matriz, as células adjacentes seguem o mesmo padrão: linha i-1, linha i+1, coluna j-1, coluna j+1. Vamos implementar:
for(i in 1:nrow_){
for(j in 1:ncol_){
aux = as.matrix(expand.grid((i-1):(i+1),(j-1):(j+1)));
vizinhos[i,j] = sum(estado_atual[aux])-estado_atual[i,j];
}
}
Perceba que pegamos um bloco de nove células: as oito células adjacentes à célula [i,j] e a própria célula [i,j]. Dessa forma, quando somamos os valores do estado atual desse bloco, precisamos subtrair o valor da célula [i,j] para obtermos apenas os vizinhos vivos. Parece fácil, correto? Para as células do interior da matriz sim, mas para as células na borda da matriz devemos ter cuidado extra.
Por exemplo, as quatro células dos extremos da matriz precisam de um código diferente para o cálculo de vizinhos, apesar de possuírem a mesma quantidade de células adjacentes. Se pegamos a célula [1,1], as células adjacentes estão na próxima coluna e na próxima linha. Agora, se pegamos a célula [nrow_,1], suas células adjacentes estão na próxima coluna e na linha anterior. Percebem o cuidado que devemos ter aqui? E isso se aplica à todas as células da borda da matriz!
Vamos passo a passo. Como o for da linha é o externo, vamos começar identificando se a linha atual está no interior da célula ou pertence à uma das bordas:
if(i>1 && i<nrow_){
...
}else if(i==1){ #primeira linha
...
}else if(i==nrow_){ #ultima linha
...
}
Agora, para cada situação da linha (ou seja, dentro de cada if do código acima), devemos verificar se a coluna atual está nas bordas ou não, ou seja, se j = 1 ou ncol_ ou está entre esses valores.
if(j>1 && j<ncol_){
...
}else if(j==1){ #primeira coluna
...
}else{#ultima coluna
...
}
Agora, o que colocar dentro de cada condição? Se a célula está no interior da matriz, nós já fizemos o código anteriormente. Mas, se está nas bordas, devemos computar os vizinhos de maneiras particulares. Nesse momento, você deve ter entendido como calcular esses vizinhos para essas células. Dessa forma, abaixo coloco a função completa, de fácil entendimento.
calcula_vizinhos = function(estado_atual){
ncol_ = ncol(estado_atual);
nrow_ = nrow(estado_atual);
vizinhos = matrix(0,ncol=ncol_,nrow=nrow_)
for(i in 1:nrow_){
for(j in 1:ncol_){
if(i>1 && i<nrow_){
if(j>1 && j<ncol_){
aux = as.matrix(expand.grid((i-1):(i+1),(j-1):(j+1)))
}else if(j==1){ #primeira coluna
aux = as.matrix(expand.grid((i-1):(i+1),(j):(j+1)))
}else{#ultima coluna
aux = as.matrix(expand.grid((i-1):(i+1),(j-1):(j)))
}
}else if(i==1){ #primeira linha
if(j>1 && j<ncol_){
aux = as.matrix(expand.grid((i):(i+1),(j-1):(j+1)))
}else if(j==1){#primeira coluna
aux = as.matrix(expand.grid((i):(i+1),(j):(j+1)))
}else{#ultima coluna
aux = as.matrix(expand.grid((i):(i+1),(j-1):(j)))
}
}else if(i==nrow_){ #ultima linha
if(j>1 && j<ncol_){
aux = as.matrix(expand.grid((i-1):(i),(j-1):(j+1)))
}else if(j==1){#primeira coluna
aux = as.matrix(expand.grid((i-1):(i),(j):(j+1)))
}else{#ultima coluna
aux = as.matrix(expand.grid((i-1):(i),(j-1):(j)))
}
}
vizinhos[i,j] = sum(estado_atual[aux])-estado_atual[i,j]
}
}
return(vizinhos);
}
Resumindo a função acima: dada uma determinada célula, pegamos um bloco de células, que depende da posição dessa célula na matriz, e calculamos seus vizinhos (somando os valores do bloco e retirando o valor da própria célula). Nossa função, então, retorna a matriz de números de vizinhos do estado atual do algoritmo do jogo da vida.
Vejamos como funciona para nosso exemplo:
> vizinhos = calcula_vizinhos(estado_atual)
> vizinhos
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11]
[1,] 0 0 0 1 2 3 3 3 3 2 1
[2,] 0 0 0 2 3 5 5 5 5 3 2
[3,] 0 0 0 3 5 8 8 8 8 5 3
[4,] 0 0 0 3 5 8 8 8 8 5 3
[5,] 0 0 0 3 5 8 8 8 8 5 3
[6,] 0 0 0 2 3 5 5 5 5 3 2
[7,] 0 0 0 1 2 3 3 3 3 2 1
[8,] 0 0 0 0 0 0 0 0 0 0 0
[9,] 0 0 0 0 0 0 0 0 0 0 0
[10,] 0 0 0 0 0 0 0 0 0 0 0
[11,] 0 0 0 0 0 0 0 0 0 0 0
> estado_atual
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11]
[1,] 0 0 0 0 0 0 0 0 0 0 0
[2,] 0 0 0 0 1 1 1 1 1 1 0
[3,] 0 0 0 0 1 1 1 1 1 1 0
[4,] 0 0 0 0 1 1 1 1 1 1 0
[5,] 0 0 0 0 1 1 1 1 1 1 0
[6,] 0 0 0 0 1 1 1 1 1 1 0
[7,] 0 0 0 0 0 0 0 0 0 0 0
[8,] 0 0 0 0 0 0 0 0 0 0 0
[9,] 0 0 0 0 0 0 0 0 0 0 0
[10,] 0 0 0 0 0 0 0 0 0 0 0
[11,] 0 0 0 0 0 0 0 0 0 0 0
Já deu um trabalho até aqui, certo? Continuamos a implementação do algoritmo no próximo post.
Até a próxima aula!
Nenhum comentário:
Postar um comentário