Jeu de la vie

Introduction

Le jeu de la vie est un automate cellulaire inventé par le mathématicien John Conway en 1970. Il s'agit d'un système fondé sur des règles très simples qui déterminent l'évolution d'un ensemble de cellules sur une grille. Chaque cellule peut être dans l'un des deux états : vivante ou morte, et son état à la génération suivante dépend de celui de ses voisines.

Malgré cette simplicité apparente, le jeu de la vie donne naissance à des comportements étonnamment complexes et variés comme nous le verrons. Dans ce projet, nous allons explorer différentes manières d'implémenter le jeu de la vie, en commençant par une version simple sur une grille finie, puis en passant à une grille infinie optimisée, avant d'aborder l'approche en arbre.

Théorie et règles

Règles de base du jeu de la vie

A chaque génération, l'état de chaque cellule dépend de ses 8 voisins immédiats (représenté en vert):

• Une cellules vivante meurt si elle a moins de 2 ou plus de 3 voisins vivants (sous-population ou surpopulation)

• Une cellule vivante survit si elle a exactement 2 ou 3 voisins.

• Une cellule morte naît si elle a exactement 3 voisins vivants

Ces règles simples donnent naissance à une diversité de motifs et d'interactions.

Exemples de comportements

(Mettre des gif pour illustrer)

• Les oscillateurs
  
• Les vaisseaux
  
• Les structures stationnaires

Implémentation sur une grille finie

Cette première version permet d'expérimenter les règles du jeu de la vie sur une grille simple. Elle est idéale pour bien comprendre le fonctionnement de base, même si elle montre vite ses limites sur des grandes tailles.

Structure de données utilisée

On utilise un tableau à deux dimensions pour stocker l’état de chaque cellule. Chaque élément vaut 0 (cellule morte) ou 1 (cellule vivante).

Initialisation et affichage de la grille

L'affichage se fait via Tkinter, en dessinant des rectangles pour chaque cellule selon son état.

# Initialisation d'une grille de dimensions définies par l'utilisateur
cases = [[0 for _ in range(largeur)] for _ in range(hauteur)]

Calcul des voisins et évolution des cellules

L'évolution d'une cellule s'effectue ensuite en appliquant les règles selon le nombre de voisins vivants.

 def voisins_vivants(x, y):
    voisins = [(-1, -1), (-1, 0), (-1, 1), 
               (0, -1),           (0, 1),
               (1, -1),  (1, 0),  (1, 1)]
    nb_vivants = 0
    for dx, dy in voisins:
        nx, ny = x + dx, y + dy
        if 0 <= nx < hauteur and 0 <= ny < largeur:
            nb_vivants += cases[nx][ny]
    return nb_vivants

Cette fonction permet de compter combien de voisines vivantes entourent une cellule donnée. On utilise une liste de décalages pour représenter les 8 positions autour de la cellule, et on vérifie que l’on reste bien dans les limites de la grille.

Avantages et limites de l'approche naïve

• Simple à comprendre et à implémenter.

• Utiles pour des grilles de petite taille.

• Gaspillage de mémoire pour de grandes tailles.

• Inadapté lorsque la majorité des cellules restent mortes.

Implémentation sur une grille infinie

Principe de stockage par dictionnaire

Pour simuler une grille infinie, seule l'information des cellules vivantes est stockée dans un dictionnaire.

Chaque clé représente les coordonnées d'une cellule vivante :

cases = {(x, y): 1, ...}

Gestion des cellules

Pour appliquer les règles, on ne parcourt pas l'ensemble de la grille mais seulement les cellules vivantes, leurs voisines potentielles.

for (x, y) in cases:
    candidats.add((x, y))
    for dx, dy in voisins:
        candidats.add((x + dx, y + dy))

Comparaison avec la grille finie

L'utilisation d'une dictionnaire pour stocker uniquement les cellules vivante est bien plus efficace en mémoire lorsque la densité de vie est faible. Elle est plus adapté aux grilles de grande taille, voire infinies, car elle évite de gérer un tableau complet.

Approche en arbre (quadtrees)

Un quadtree est une structure d’arbre qui divise récursivement la grille en 4 sous-régions.