Démineur

Le but de ce travail est d’implémenter le jeu démineur en C (vous pouvez jouer à une version en ligne sur https://minesweeperonline.com par exemple).

Règles du jeu

Le jeu du démineur se joue seul. Un nombre fixé de mines cachées se trouvent sur une aire de jeu rectangulaire. À chaque étape, la joueuse peut soit ouvrir une case, soit placer un drapeau là où elle pense que se trouve une mine. Lorsqu’une case est ouverte, le nombre de mines dans le voisinage de cette case (les cases adjacentes, diagonales comprises, soit au plus 8 cases) est affiché. Si ce nombre est 0, alors les voisins de la case qui ne portent pas de drapeau sont également ouverts. Le processus est répété pour tout voisin n’ayant aucune mine dans son voisinage, puis ceci est propagé aux voisins, etc. Si une case contenant une mine est ouverte, le jeu se termine sur une défaite et l’aire de jeu est affichée avec toutes les cases ouvertes (une mine couverte par un drapeau s’affiche alors M). La première case ouverte peut contenir une mine: aucun traitement particulier n’est demandé. Si la joueuse réussit à ouvrir toutes les cases sans mine, alors elle gagne et la partie se termine: l’aire de jeu est affichée une dernière fois dans son état courant. Le temps écoulé doit s’afficher à la fin de la partie. À noter qu’il ne doit pas être possible de placer plus de drapeaux que de mines et que la joueuse peut toujours décider d’enlever un drapeau d’une case si elle pense s’être trompée sur la présence d’une mine. Le nombre de drapeaux restants est affiché avec l’aire de jeu.

Utilisation

Votre programme doit se lancer en ligne de commande selon deux modes. Si votre exécutable se nomme demineur, on le lancera comme suit:

$ ./demineur C L M

où C et L sont le nombre de colonnes et de lignes respectivement, et M le nombre de mines. Dans ce mode de jeu, les M mines sont placées aléatoirement sur des cases toutes distinctes (pensez à initialiser le générateur de nombres aléatoires avec srand). Le second mode permet de placer les mines à des endroits prédéterminés:

$ ./demineur C L c1 l1 c2 l2 ...

où C et L sont le nombre de colonnes et de lignes respectivement, et (c1, l1), (c2, l2), … sont les positions (colonne, ligne) des mines. Les colonnes et les lignes sont numérotées à partir de 0, la case (0, 0) se trouvant en haut à gauche.

Le nombre d’arguments permet de distinguer les deux modes: argc vaut 4 dans le premier mode, et est impair et supérieur ou égal à 5 dans le second.

Le programme affiche un message d’erreur sur stderr et se termine avec un code de retour non nul si les arguments sont invalides, c’est-à-dire:

Dans le cas où la joueuse a joué D ou O, on demande encore la position de la case sous la forme de deux entiers c et l, dans cet ordre.

Si la saisie est invalide (action inconnue, position hors de l’aire de jeu, drapeau sur une case ouverte, drapeau en trop, ouverture d’une case déjà ouverte ou portant un drapeau), le programme affiche un message et redemande une action.

L’affichage se fait uniquement en mode textuel dans le terminal. Une case fermée s’affiche ., une case ouverte sans mine voisine s’affiche avec un caractère espace, la mine un M, le drapeau un D, et une case ouverte ayant des mines voisines s’affiche avec le chiffre correspondant à leur nombre.

Exemple de partie

Le format exact des messages est libre. Voici une partie gagnée, sur une aire de jeu de 4 colonnes et 3 lignes avec des mines en (0, 0) et (3, 2):

Structure de données

Chaque case de votre jeu est d’un type énuméré nommé square_t qui consiste en les variantes EMPTY ou MINE. Ainsi votre tableau de jeu est un tableau à deux dimensions dont chaque case est du type square_t. On vous propose d’utiliser encore deux autres tableaux. Les cases du premier tableau contiendront le nombre de mines voisines d’une case. Le second tableau, dont les cases sont d’un type énuméré nommé state_t, stockera si une case du jeu a été ouverte, OPEN, est encore fermée, CLOSED, ou porte un drapeau, FLAG.

Afin de simplifier, nous utiliserons les VLA (variable length array, ou tableaux de longueur variable) et le tableau de jeu sera un tableau de taille L x C. Les VLA sont alloués sur la pile, dont la taille est limitée, et la profondeur de la récursion peut atteindre L x C appels: c’est pourquoi C et L sont limités à 100, afin d’éviter un dépassement de pile. Ainsi un tableau de tableaux de type square_t se déclare comme:

square_t board[L][C];

Pour passer un tel tableau à une fonction, les dimensions doivent précéder le tableau dans la liste des paramètres:

void init_board(int l, int c, square_t board[l][c]);

Attention, un VLA ne peut pas être initialisé à sa déclaration avec = {0}: il faut l’initialiser avec des boucles.

Ouverture des cases

Lorsqu’on ouvre une case valide (pas couverte par un drapeau et pas déjà ouverte), il faut bien réfléchir à ce qui se passe. Dans le cas où on découvre une mine, la partie se termine. Dans le cas où on découvre une case à côté d’une mine, on affiche le nombre de mines voisines de la case. Finalement, dans le cas où on découvre une case sans mine voisine, on découvre toutes les cases voisines qui ne sont ni ouvertes ni couvertes par un drapeau. La fonction qui ouvre une case est donc récursive.

Remarques

Fonctions

Il est indispensable que vous définissiez des fonctions. Réfléchissez bien à l’organisation de votre programme avant de commencer à coder.

Mesure du temps d’exécution

La mesure du temps d’exécution de votre programme se fait grâce à la librairie <time.h>. Un exemple d’utilisation est donné par les lignes suivantes:

struct timespec start, finish;
clock_gettime(CLOCK_MONOTONIC, &start);
// Code dont on veut mesurer le temps d'exécution
clock_gettime(CLOCK_MONOTONIC, &finish);
double elapsed = (finish.tv_sec - start.tv_sec)
               + (finish.tv_nsec - start.tv_nsec) / 1e9;
printf("elapsed seconds = %f\n", elapsed);