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

• Les structures stationnaires : Ce sont des configurations qui restent figées dans le temps, sans changer d'état à travers les générations. Un exemple classique est le Block, un carré de 2x2 cellules vivantes qui reste stable tant qu’aucune autre cellule ne l’approche.

• Les vaisseaux : Ce sont des structures capables de se déplacer à travers la grille tout en conservant leur forme. Le plus connu est le Spaceship, un petit vaisseau qui se déplace horizontalement. Ces motifs montrent comment un mouvement global peut émerger de règles strictement locales.

• Les oscillateurs : Il s’agit de structures qui reviennent périodiquement à leur configuration initiale après un certain nombre de générations. Le Pulsar est un oscillateur de période 3 : il alterne entre trois états différents avant de retrouver sa forme de départ.

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. Cette approche est particulièrement adaptée pour simuler le jeu de la vie sur de très grandes grilles, voire infinies, lorsqu'une grande partie des cellules reste inactive.

Principe

• Subdivision de la grille : La grille est divisée en 4 quadrants, chacun pouvant être à son tour subdivisé en 4 sous-quadrants. Cette récursivité permet de représenter efficacement les zones homogènes, par exemple les régions totalement mortes.
• Compression  : Les régions ayant un état homogène (par exemple, totalement mortes) n'ont pas besoin d'être représentées en détail. Le quadtree regroupe ces zones en un seul noeud, réduisant ainsi la mémoire utilisée.
• Optimisation de l’évolution : Seules les zones actives, donc celles avec des cellules vivantes ou susceptibles de changer, sont simulées en détail. Ceci permet de gagner en performances en ignorant rapidement les grandes portions inactives.

Avantages de l'approche par quadtree

Les avantages sont nombreux, en voici certains :

• Mémoire : En ne stockant que les régions qu'il faut, l'approche par quadtree évite le gaspillage de mémoire associé aux grilles de grande taille.
• Performances améliorées : Le calcul se concentre uniquement sur les zones modifiées, ce qui accélère la simulation, notamment pour des configurations où la densité de cellules vivantes est faible.
• Extension à l’infini : Grâce à la représentation récursive et à la compression des zones inactives, cette méthode permet de simuler pratiquement une grille infinie.