Démineur

• Durée: 6 périodes + travail à la maison
• Date de rendu: minuit le jour avant le prochain labo

Contenu

• Démineur
  • Objectifs
  • Ncurses
  • Déroulement du laboratoire
  • Architecture
    • Cellule
    • Terrain
    • Jeu
  • Algorithmes
  • Considération de design

Objectifs

On vous demande d'implémenter un démineur en mode texte. La surface de jeu fera 7 x 7 cellules mais elle doit être un paramètre configurable.

Dans chaque cellule vous indiquez le nombre de bombes que la cellule touche. Si c'est une bombe vous indiquez *. Vous pouvez aussi indiquer 💣 en utilisant des émoji si votre terminal le supporte (Windows Terminal supporte ce type de caractères).

Voicl le plateau de jeu que l'utilisateur ne doit pas voir en temps normal, car il dévoile les bombes :

┌───┬───┬───┬───┬───┬───┬───┐
│   │ 1 │ 1 │ 1 │   │   │   │
├───┼───┼───┼───┼───┼───┼───┤
│   │ 1 │ * │ 1 │   │   │   │
├───┼───┼───┼───┼───┼───┼───┤
│   │ 2 │ 2 │ 2 │   │   │   │
├───┼───┼───┼───┼───┼───┼───┤
│   │ 1 │ * │ 1 │   │   │   │
├───┼───┼───┼───┼───┼───┼───┤
│   │ 1 │ 1 │ 1 │   │   │   │
├───┼───┼───┼───┼───┼───┼───┤
│   │   │   │ 1 │ 1 │ 1 │   │
├───┼───┼───┼───┼───┼───┼───┤
│   │   │   │ 1 │ * │ 1 │   │
└───┴───┴───┴───┴───┴───┴───┘

Un clic de souris permet de dévoiler une cellule.

Au démarrage du programme, une grille aléatoire est générée avec un certain nombre de bombes. L'utilisateur voit la grille avec aucune cellule exposée :

┌───┬───┬───┬───┬───┬───┬───┐
│ . │ . │ . │ . │ . │ . │ . │
├───┼───┼───┼───┼───┼───┼───┤
│ . │ . │ . │ . │ . │ . │ . │
├───┼───┼───┼───┼───┼───┼───┤
│ . │ . │ . │ . │ . │ . │ . │
├───┼───┼───┼───┼───┼───┼───┤
│ . │ . │ . │ . │ . │ . │ . │
├───┼───┼───┼───┼───┼───┼───┤
│ . │ . │ . │ . │ . │ . │ . │
├───┼───┼───┼───┼───┼───┼───┤
│ . │ . │ . │ . │ . │ . │ . │
├───┼───┼───┼───┼───┼───┼───┤
│ . │ . │ . │ . │ . │ . │ . │
└───┴───┴───┴───┴───┴───┴───┘

Cliquez sur une cellule (ligne 1, colonne 0) pourrait donner ceci :

┌───┬───┬───┬───┬───┬───┬───┐
│   │ 1 │ . │ . │ . │ . │ . │
├───┼───┼───┼───┼───┼───┼───┤
│   │ 1 │ . │ . │ . │ . │ . │
├───┼───┼───┼───┼───┼───┼───┤
│   │ 2 │ . │ . │ . │ . │ . │
├───┼───┼───┼───┼───┼───┼───┤
│   │ 1 │ . │ . │ . │ . │ . │
├───┼───┼───┼───┼───┼───┼───┤
│   │ 1 │ 1 │ 1 │ . │ . │ . │
├───┼───┼───┼───┼───┼───┼───┤
│   │   │   │ 1 │ . │ . │ . │
├───┼───┼───┼───┼───┼───┼───┤
│   │   │   │ 1 │ . │ . │ . │
└───┴───┴───┴───┴───┴───┴───┘

L'utilisateur gagne le jeu lorsque seul les bombes sont exposées :

┌───┬───┬───┬───┬───┬───┬───┐
│   │ 1 │ 1 │ 1 │   │   │   │
├───┼───┼───┼───┼───┼───┼───┤
│   │ 1 │ ? │ 1 │   │   │   │
├───┼───┼───┼───┼───┼───┼───┤
│   │ 2 │ 2 │ 2 │   │   │   │
├───┼───┼───┼───┼───┼───┼───┤
│   │ 1 │ ? │ 1 │   │   │   │
├───┼───┼───┼───┼───┼───┼───┤
│   │ 1 │ 1 │ 1 │   │   │   │
├───┼───┼───┼───┼───┼───┼───┤
│   │   │   │ 1 │ 1 │ 1 │   │
├───┼───┼───┼───┼───┼───┼───┤
│   │   │   │ 1 │ ? │ 1 │   │
└───┴───┴───┴───┴───┴───┴───┘

Lorsque l'utilisateur clique avec le bouton gauche de la souris, il démine une région. Lorsqu'il clique avec le bouton droit il marque la cellule comme à risque (?).

Ncurses

ncurses est une bibliothèque écrite en C et permettant de créer des interfaces graphiques en ligne de commande. Deux exemples vous sont donnés dans le répertoire ncurses-examples. Pour compiler ces exemples vous devez avoir la bibliothèque installée sur votre distribution Linux :

apt-get install libncurses-dev

Ensuite vous pouvez utiliser :

g++ 1.cpp -lncurses

Ces deux exemples vous montre comment :

• Afficher un caractère à une certaine position
• Capturer la position de la souris

Une bonne approche est d'encapsuler toute la complexité de NCurses dans des classes et des méthodes :

• displayBoard Qui affiche le terrain ou met à jour le terrain
• loop() Boucle principale qui détecte les clics souris
• initScreen() Initialize l'écran
• freeScreen() Libère l'écran

Vous avez le choix dans le noms de ces méthodes et dans l'architecture de votre code pour cette partie.

Déroulement du laboratoire

Le déroulement suivant est proposé mais c'est à vous de vous organiser :

1. Prise de connaissance des exemples en Ncurses
2. Essai d'un petit programme pour afficher une matrice et obtenir la position d'un clic dans la matrice.
3. Écriture de la classe de gestion de l'affichage
4. Modélisation de l'architecture générale du programme
5. Implémentation de la structure en C++
6. Implémentation des algorithmes demandés
7. Affichage minimaliste de la grille (sans les séparateurs)
8. Gestion clics (capture de la cellule correspondant au clic gauche ou droit)
9. Affichage avancé de la grille (avec les séparateurs)

Vous devez absolument découper votre programme en petites parties fonctionnelles sinon vous vous sentirez au fond du gouffre...

Architecture

Une bonne approche serait de définir plusieurs classes. À vous de définir ce qui doit être public ou privé. Voici une proposition :

Cellule

• int ligne Ligne ou se situe la cellule
• int column Colonne ou se situe la cellule
• bool isBomb Est-ce une bombe ou une cellule vide ?
• int number Nombre de bombes en voisinage proche
• bool isExposed Est-ce que la cellule est dévoilée ?
• bool isGuess Est-ce que la cellule est un candidat de bombe ? ?

Une cellule est réalisée avec un constructeur à deux paramètres : row, column. Chaque instance possède deux méthodes :

• flip() pour rendre la cellule visible (action clic gauche)
• toggleGuess() pour marquer la cellule comme un candidat de bombe (action clic droit)

Terrain

Le terrain de jeu Board est une classe comportant les paramètres suivants :

• int nRows : Nombre de lignes
• int nCols : Nombre de colonnes
• int nBombs : Nombre de bombes
• Cell[][] cells : toutes les cellules (à vous d'utiliser la bonne structure de donnée pour sauver les cellules [][] n'est pas du C++ valide)
• Cell[] bombs : une liste de références sur toutes les bombes
• int numUnexposedRemaining : nombre de cellules restantes à être dévoilées

Le constructeur prends en paramètre le nombre de lignes, le nombre de colonnes et le nombre de bombes à créer.

Une méthode privée initializeBoard() instancie les cellules et initialise le terrain de jeu. Cete méthode est appelée par le constructeur de classe.

flipCell(Cell cell) permet de changer l'état d'une cellule. expandBlank(Cell cell) permet d'étendre la surface valide jusqu'aux frontières à proximité des bombes. getNumRemaining() retourne le nombre de cellules restantes à retourner.

Jeu

La classe Game stoque les références sur le terrain et les cellules, ainsi que l'état du jeu.

Algorithmes

Il y a plusieurs algorithmes à implémenter dans ce labo :

• Placer les bombes
• Numéroter les cellules
• Étendre une région

Pour placer les bombes, la meilleures solution est de créer une méthode shuffleBoard() qui va mélanger le terrain de jeu en utilisant l'algorithme de Fisher-Yates. De cette façon il suffit de placer les bombes dans les premières cases du terrain et de mélanger le terrain.

Numéroter les cellules est de déterminer pour chaque cellule les bombes à proximité. Pour ce faire il faut détecter les proches voisins en utilisant une matrice de voisinage :

int deltas[][2] = {
    {-1, -1}, {-1, 0}, {-1, 1},
    { 0, -1}, { 0, 0}, { 0, 1},
    { 1,  1}, { 1, 0}, { 1, 1}
};

Pour chaque bombe référencées dans la table des bombes, la matrice de voisinage est parcourue et les cellules environnantes sont incrémentées.

Étendre une région peut être résolu itérativement ou récursivement. C'est l'algorithme le plus difficile de ce labo. La solution récursive est généralement plus facile à implémenter.

Considération de design

Dans ce labo, il n'y a pas de raison d'utiliser d'allocation dynamique hormis pour les listes de cellules dont la taille n'est pas connue avant la création de l'objet. Dans votre première implémentation utilisez simplement un tableau statique à deux dimensions Cell cells[7][7]. Par la suite lorsque cela fonctionnera, vous pourrez remplacer ce tableau par un vecteur multidimensionnel dynamique.

Dans ce labo, il n'y a pas d'héritage, les classes restent simples.

Commencer par développer votre programme dans un seul fichier, puis lorsque tout fonctionne découpez votre programme en fichiers séparés : game.cpp, board.cpp, main.cpp...

Faites un flowchart sur papier pour bien saisir le déroulement de votre programme. Par exemple:

1. Créer une instance de jeu
2. Initialiser les grilles
3. Initialiser l'écran
4. Afficher la grille
5. Entrer dans la boucle itérative du jeu
6. Terminer le jeu
7. Libérer l'écran
8. Quitter le programme