Problème: Le jeu de la vie

Problème: Le jeu de la vie#

#include <vector>
#include <iostream>
#include <fstream>
using namespace std;

Les exercices suivants visent à implanter le jeu de la Vie en C++ avec les éléments appris ce semestre: le Jeu de la Vie est un jeu de simulation sur une grille inventé par John Conway en 1970. Le principe est à la fois très simple et très riche. Le jeu se base sur une grille rectangulaire divisées en cellules. Chaque cellule peut être "active" (point noir) ou inactive (point blanc) comme dans l'image ci-dessous

../../_images/Game_of_life.png

L'état des cellules va ensuite évoluer en fonction de leurs cellules voisines (nous expliquerons les détails plus tard). Dans notre programme, nous définission un type Grille qui est un tableau d'entiers à 2 dimensions pour représenter une grille de jeu. Les cellules actives seront codées par la valeur \(1\) et les cellules innactives par la valeur \(0\).

using Grille = vector<vector<int>>;

Pour simplifier, on supposera toujours que les variables grilles ont un nombre de lignes et de colonnes strictement supérieur à 0. Nous définissons plusieurs grilles de tests (suggestion: dessinez les):

Grille vide  = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}};
Grille test1 = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
Grille test2 = {{0, 0, 0}, {1, 1, 1}, {0, 0, 0}};
Grille test3 = {{0, 1, 0}, {0, 1, 0}, {0, 1, 0}};
Grille test4 = {{1, 1, 0}, {1, 1, 0}, {0, 0, 0}};

Toutes les questions sont indépendantes. On peut utiliser une fonction définie dans une question précédente même si on n'a pas réussi à l'écrire.

Définissez une fonction qui prend en paramètre une grille et renvoie le nombre de cellules actives. Des tests vous sont donnés à la page suivante.

/// BEGIN SOLUTION
int compteActives(Grille grille) {
    int v = 0;
    for(int i = 0; i < grille.size(); i++) {
        for(int j = 0; j < grille[i].size(); j++) {
            if(grille[i][j] == 1) {
                v++;
            }
        }
    }
    return v;
}
/// END SOLUTION

CHECK(compteActives(vide) == 0);
CHECK(compteActives(test1) == 1);
CHECK(compteActives(test2) == 3);
CHECK(compteActives(test3) == 3);
CHECK(compteActives(test4) == 4);

Les grilles peuvent facilement être enregistrées au format PBM. On rappelle que le format PBM est un format d'image stocké dans un fichier texte contenant dans cet ordre : le format (P1), le nombre de colonnes, le nombre de lignes et les pixels de l'image avec 1 pour noir et 0 pour blanc. Par exemple, l'image représentant la grille test3 est la suivante :

P1
3 3
0 1 0
0 1 0
0 1 0

Compléter la fonction lireGrille suivante qui fabrique une grille de jeu à partir d'un fichier PBM dont le nom est passé en paramètre.

Grille lireGrille(string nomFichier) {
    /// BEGIN SOLUTION
    ifstream flux;
    flux.open(nomFichier);
    string format;
    int lignes;
    int cols;
    flux >> format;
    flux >> cols;
    flux >> lignes;
    Grille resultat(lignes);
    for(int i = 0; i < lignes; i++) {
        resultat[i] = vector<int>(cols);
        for(int j =0; j < cols; j++) {
            flux >> resultat[i][j];
        }
    }
    flux.close();
    return resultat;
    /// END SOLUTION
}

CHECK(lireGrille("media/grille.pbm") == test3);

Le Jeu de la Vie est ce que l'on appelle un automate cellulaire. C'est-à-dire que la grille va évoluer par étape en fonction de son état. Plus précisément, l'état d'une cellule à l'étape \(n+1\) dépend de son nombre de voisines actives à l'étape \(n\). Les voisines d'une cellule sont les 8 cellules adjacentes verticalement, horizontalement et en diagonale. On cherche à implanter une fonction compteVoisines qui renvoie le nombre de cellules voisines actives d'une cellule donnée.

Voici la documentation de la fonction. Proposez cinq tests pour cette fonction, avec la grille test4 et, respectivement, les cellules des quatre coins et du milieu de la grille.

int min(int a, int b) {
    return a<b? a : b;
}

int max(int a, int b) {
    return a<b ? b : a;
}

int compteVoisines(Grille grille, int l, int c) {
    int min_l = max(l - 1, 0);
    int max_l = min(grille.size(), l + 2);
    int min_c = max(c - 1, 0);
    int max_c = min(grille[l].size(), c + 2);
    int voisines = 0;
    for(int i = min_l; i < max_l; i++) {
        for(int j = min_c; j < max_c; j++) {
            if(i != l or j != c) voisines += grille[i][j];
        }
    }
    return voisines;
}

/** compte les voisines d'une cellule donnée
 * @param grille, une grille de jeu
 * @param l, un numéro de ligne
 * @param c, un numéro de colonne
 * @return le nombre de voisines actives de la cellule de ligne l et colonne c
**/

/// BEGIN SOLUTION
CHECK( compteVoisines(test4, 0, 0) == 3 );
CHECK( compteVoisines(test4, 0, 2) == 2 );
CHECK( compteVoisines(test4, 2, 0) == 2 );
CHECK( compteVoisines(test4, 2, 2) == 1 );
CHECK( compteVoisines(test4, 1, 1) == 3 );
/// END SOLUTION

Un élève a défini la fonction comme suit, mais les tests ne passent pas. On obtient en particulier 4 voisines au lieu de 3 pour la cellule du milieu. Trouvez l'erreur et corrigez la fonction.

int compteVoisinesBug(Grille grille, int l, int c) {
    int min_l = max(l - 1, 0);
    int max_l = min(grille.size(), l + 2);
    int min_c = max(c - 1, 0);
    int max_c = min(grille[l].size(), c + 2);
    int voisines = 0;
    for(int i = min_l; i < max_l; i++)
        for(int j = min_c; j < max_c; j++)
            voisines += grille[i][j];
    return voisines;
}

compteVoisinesBug(test4,1,1) // affiche 4 au lieu de 3

Il peut être utile d'extraire une ligne ou une colonne donnée de la grille. Implantez une fonction extraitColonne qui prend en paramètre la grille et un indice \(j\) de colonne (qu'on supposera valide) et renvoie la colonne d'indice \(j\) sous forme de tableau.

using tableau = vector<int>; // Contournement de la limitation de Jupyter

/// BEGIN SOLUTION
tableau extraitColonne(Grille grille, int j) {
    vector<int> col(grille.size());
    for(int i =0; i < grille.size(); i++) {
        col[i] = grille[i][j];
    }
    return col;
}
/// END SOLUTION

Nous pouvons maintenant implanter l'évolution de la grille ! Voici les règles :

  • une cellule active "meurt" (devient inactive) à l'étape suivante si elle a strictement moins de deux voisines actives ou strictement plus de trois voisines actives;

  • une cellule inactive "naît" (devient active) à l'étape suivante si elle a exactement trois voisines actives;

  • sinon, la cellule garde le même état.

Complétez ci-dessous la fonction iterationJeuDeLaVie qui renvoie la nouvelle grille après l'évolution des cellules. Des tests sont fournis.

Indication: créer une nouvelle grille pour le nouvel état afin de ne pas modifier la grille de l'état courant: le changement d'état d'une cellule ne doit en effet pas impacter celui de ses voisines.

Grille iterationJeuDeLaVie(Grille grille) {
    /// BEGIN SOLUTION
    Grille resultat = Grille(grille.size());
    for ( int i = 0; i < resultat.size(); i++ ) {
        resultat[i] = vector<int>(grille[i].size());
        for ( int j = 0; j < grille[i].size(); j++ ) {
            int v = compteVoisines(grille, i, j);
            resultat[i][j] = grille[i][j];
            if ( grille[i][j] == 0 and v == 3 ) {
                resultat[i][j] = 1;
            }
            if ( grille[i][j] == 1 and (v < 2 or v > 3) ) {
                resultat[i][j] = 0;
            }
        }
    }
    return resultat;
	//
	//
	//
    /// END SOLUTION
}

CHECK(iterationJeuDeLaVie(test1) == vide);
CHECK(iterationJeuDeLaVie(test2) == test3);
CHECK(iterationJeuDeLaVie(test3) == test2);
CHECK(iterationJeuDeLaVie(test4) == test4);