Le jeu de la vie

Le jeu et ses règles

Le jeu de la Vie (Game of Life) est un automate cellulaire — devenu un jeu de simulation mathématique — imaginé par John Horton Conway en 1970 https://fr.wikipedia.org/wiki/Jeu_de_la_vie.

Le jeu se déroule sur une grille à deux dimensions, théoriquement infinie, dont les cases — appelées « cellules », par analogie avec les cellules vivantes — peuvent prendre deux états distincts : « vivante » ou « morte ».

Une cellule possède huit voisines, qui sont les cellules adjacentes horizontalement, verticalement et diagonalement.

À chaque itération, l’état d’une cellule est entièrement déterminé par l’état de ses huit cellules voisines, selon les règles suivantes :

• Une cellule morte possédant exactement trois cellules voisines vivantes devient vivante (elle naît) ;
• Une cellule vivante ne possédant pas exactement deux ou trois cellules voisines vivantes meurt.

L’initialisation de la grille

Nous allons initialiser une grille en la remplissant aléatoirement avec des cellules vivantes (représentées par 1) et mortes (0). Pour simplifier la suite des calculs, nous ajoutons une bordure autour de la grille : cela permet d’éviter de gérer explicitement les effets de bord.

taille = 100
probability = 0.4

grille = matrix(0, taille + 2, taille + 2) # + 2 la bordure à gauche à droite, en haut et en bas. 
grille[2:(taille + 1),2:(taille + 1)] = rbinom(taille^2, 1, probability)


image(grille, asp=1, xaxt='n', yaxt='n', ann=FALSE)

Pouvez-vous exécuter plusieurs fois ce code, en modifiant la valeur du paramètre probability, puis observer les résultats obtenus ? Cela vous permettra de mieux comprendre le comportement de la fonction rbinom et son effet sur la répartition des cellules vivantes (1) et mortes (0).

Programmer la vie

Ma première fonction : pour connaitre l’état futur d’une cellule

Réaliser une itération sur l’ensemble de la grille est une opération relativement complexe. Pour simplifier, nous allons commencer par nous concentrer sur une seule cellule : l’objectif est de calculer son état au prochain tour. La fonction que nous allons écrire devra donc récupérer le voisinage de cette cellule, puis en déduire son état futur.

cellule_etat_n_plus_un <- function(i,j, grille){ # ligne i, colonne j
     etat_cellule = grille[i,j]
     voisinage <- grille[(i-1):(i+1), (j-1):(j+1)] 
     nb_voisin <- sum(voisinage) - etat_cellule
     if (etat_cellule==0){ # je teste si la cellule est morte (égale à 0) 
         if (nb_voisin==3){ # si oui, je teste si elle a trois voisins
            return(1)      # si oui je retourne 1 car elle est vivante    
         }else {          # si non,   
            return(0)      # je retourne 0  
     }}else {              # si j'arive ici la cellule est vivante
         if (nb_voisin %in% c(2,3)){# je teste si la cellule a deux ou trois voisins
            return(1)      # qu'est ce que j'affecte ?  
         }else{
            return(0)      # qu'est ce que j'affecte .
         }        
  }
    
}

# je la lance de cette manière 
cellule_etat_n_plus_un(52,18,grille) 

[1] 1

Boucler pour trouver l’état futur de la grille

Maintenant que nous avons défini notre fonction principale, il est temps de voir comment l’utiliser sur toute la grille. Pour cela, nous allons créer une nouvelle fonction qui va parcourir la grille, ligne par ligne et colonne par colonne, et appliquer notre fonction principale à chaque case. Cette nouvelle fonction prendra donc en entrée une grille complète, et s’appuiera sur la fonction précédente pour effectuer le traitement souhaité à chaque étape.

grille_etat_n_plus_un <- function(grille){ 
  taille = nrow(grille) - 2 # je déduis la taille directement depuis la grille (attention la variable est locale) 
  grille_n_plus_un = matrix(0, taille + 2, taille + 2)
  for (i in 2:(taille + 1)){
    for (j in 2:(taille + 1)){
      grille_n_plus_un[i,j] = cellule_etat_n_plus_un(i, j, grille)
    } 
  }
  return(grille_n_plus_un)    
}

# je la lance de cette manière 
grille_n_plus_un <- grille_etat_n_plus_un(grille) 
image(grille_n_plus_un, asp=1, xaxt='n', yaxt='n', ann=FALSE)

Et maintenant la vie

On crée une fonction qui applique autant de fois que souhaité la fonction d’itération précédente. Le nombre d’itérations à effectuer est défini par le paramètre N.

jeu_de_la_vie <- function(grille, N){
  for (i in 1:N){
    grille <- grille_etat_n_plus_un(grille)
  }
  return(grille)
}

resultat <- jeu_de_la_vie(grille, 10)
image(resultat, asp=1, xaxt='n', yaxt='n', ann=FALSE)

Le résultat est intéressant, mais il reste difficile de suivre visuellement l’évolution de la grille à chaque étape. Pour y remédier, nous allons créer une fonction qui génère une image à chaque itération. Cette option ne sera active que si le paramètre image_plot est défini sur TRUE (par défaut, il est sur FALSE pour ne pas générer trop d’images inutilement).

jeu_de_la_vie <- function(grille, N, image_plot=FALSE){
  for (i in 1:N){
    grille <- grille_etat_n_plus_un(grille)
    if (image_plot){
      png(filename=paste0("resultats/image", i ,".png"))
      image(grille, asp=1, xaxt='n', yaxt='n', ann=FALSE)
      dev.off()
    }

  }
  return(grille)
}

resultat <- jeu_de_la_vie(grille, 100, image_plot = TRUE)

Pour les plus hardcoreu.s.es, on utilise magick pour transformer les images en une gif animée :

## list file names and read in
library(magick)

Linking to ImageMagick 6.9.13.17
Enabled features: cairo, fontconfig, freetype, ghostscript, lcms, pango, raw, rsvg, webp, x11
Disabled features: fftw, heic

Using 29 threads

details = file.info(list.files("resultats/", full.names = TRUE))
details = details[with(details, order(as.POSIXct(mtime))), ]
imgs = rownames(details)


img_list <- lapply(imgs, image_read)

## join the images together
img_joined <- image_join(img_list)

## animate at 2 frames per second
img_animated <- image_animate(img_joined, fps = 10)

## view animated image
img_animated

## save to disk
image_write(image = img_animated,
            path = "gameoflife.gif")

Un peu de poésie

Maintenant, tu vas appliquer ta fonction sur une grille particulière : un U (cf https://fr.wikipedia.org/wiki/Jeu_de_la_vie#Dimension_et_complexit%C3%A9 )

grille <- matrix(0, taille + 2, taille + 2)
grille[50,50] <- 1
grille[50,51] <- 1
grille[50,52] <- 1
grille[51,52] <- 1
grille[52,52] <- 1
grille[52,51] <- 1
grille[52,50] <- 1
resultat <- jeu_de_la_vie(grille, 110)
image(resultat, asp=1, xaxt='n', yaxt='n', ann=FALSE)

Créer un band d’essai pour le jeu de la vie

La dernière étape consiste à créer une fonction capable de générer une grille aléatoire, en fonction d’une taille et d’une probabilité données. Une fois la grille initiale créée, la fonction lancera N étapes d’évolution.

experience <- function(probability, taille, N){
  grille = matrix(0, taille + 2, taille + 2) # + 2 la bordure à gauche à droite, en haut et en bas. 
  grille[2:(taille + 1),2:(taille + 1)] = rbinom(taille^2, 1, probability)
  
  return(jeu_de_la_vie(grille, N))
}

image(experience(0.2,100,150), asp=1, xaxt='n', yaxt='n', ann=FALSE)

image(experience(0.8,100,150), asp=1, xaxt='n', yaxt='n', ann=FALSE)

Bonus : est ce que l’on aurait pu vectoriser les calculs ?

L’exécution du programme est assez lente, principalement parce que nous utilisons des boucles pour parcourir la grille. Une question intéressante à se poser est la suivante : peut-on améliorer les performances en utilisant des opérations vectorisées, qui permettent de traiter les données plus efficacement, notamment en tirant parti des optimisations internes du langage ?

somme = grille[1:(taille),1:(taille)] + grille[2:(taille+1), 1:(taille)] + grille[3:(taille+2), 1:(taille)] + 
  grille[1:(taille),2:(taille+1)] + grille[3:(taille+2), 2:(taille+1)] +
grille[1:(taille),3:(taille+2)] + grille[2:(taille+1), 3:(taille+2)] + grille[3:(taille+2), 3:(taille+2)]  
image(somme, asp=1, xaxt='n', yaxt='n', ann=FALSE)