Minesweeper (récursivité)

On souhaite écrire une version du jeu Minesweeper (démineur). On utilise la librairie MLV pour gérer le graphisme et les interactions avec l'utilisateur. Normalement, la librairie est disponible sur vos comptes de l'université; si vous souhaitez l'utiliser sur votre ordinateur personnel, vous pouvez vous référer à cette page. Commencer par récupérer l'archive Sweeper.zip et extraire les fichiers dans votre répertoire de travail.

$ make
gcc -c -o sweeper.o sweeper.c -Wall -ansi
gcc -c -o grid.o grid.c -Wall -ansi
gcc -c -o draw.o draw.c -Wall -ansi
gcc -o sweeper sweeper.o grid.o draw.o -lMLV -lm -lSDL
$ ./sweeper

Vous voyez qu'il y a déjà une partie du jeu en place mais que le jeu ne fonctionne pas. Plus précisément, il manque une fonction qui place les mines sur la grille initiale et une fonction qui découvre les cases dès que le joueur clique (gauche) sur une case. Familiarisez-vous avec les structures cell et grid, les fonctions pour dessiner la grille et la fonction principale du jeu.

Écrire la fonction void add_mines(grid *g, int n) dans grid.c. La fonction prend (un pointeur vers) une grille, g, et un entier n et elle doit ajouter exactement n mines sur la grille à des emplacements choisis de facon aléatoire. De plus, cette fonction doit mettre à jour les champs mine_count des cases voisines des mines. Voir la figure ci-dessous : Pour vérifier votre fonction, vous pouvez ajouter dans votre main un appel à la fonction set_all_visible(g). Cette fonction rend toutes les cases visibles. N'oubliez pas d'enlever cet appel avant de commencer l'exercice suivant.

Écrire la fonction int uncover(grid *g, cell *c) dans grid.c. La fonction prend (un pointeur vers) une grille, g, et une case, c. Elle doit renvoyer le nombre de cases qui ont été découvertes. Pour cela, elle doit découvrir récursivement les cases comme suit :

1. Si la case est déjà visible ou marquée (gris-sombre, par un clic droit), alors la fonction ne découvre pas la case courante, ni les cases voisines. Elle renvoie 0 pour indiquer qu'aucune case n'a été découverte.
2. Sinon, on commence par découvrir la case c et on utilise la fonction draw_cell_actualise_window(c) pour visualiser ce changement.
   1. Si la case c contient une mine ou si son compteur de mines voisines ne vaut pas 0, alors on renvoie 1 pour indiquer qu'une seule case a été découverte.
   2. Sinon, on lance, pour chaque voisin v tel que v n'est pas découvert, un appel récursif à uncover sur v. On récupère les résultats (nombre de cases découvertes) de tous les appels et on renvoie leur somme (+ 1 pour la découverte de la case c).

Pour mieux voir l'ordre dans lequel les cases sont découvertes, vous pouvez utilisez la fonction void MLV_wait_milliseconds(int milliseconds) de la librairie MLV.

Dans cet exercice, on souhaite remplacer la fonction récursive int uncover(grid *g, cell *c) par une fonction itérative int uncover_it(grid *g, cell *c). Pour cela, il va nous falloir "simuler" le comportement des appels récursifs.

1. Dans un premier temps, on utilise une pile explicite (qui remplace la pile d'exécution utilisée pour les appels récursifs).
   1. Commencer par implémenter une pile d'entiers en utilisant la structure :

      typedef struct {
        int *data;
        int top;
        int max_size;
      } stack;
      

      avec les opérations :

      stack *create_stack(int max_size);
      void free_stack(stack *s);
      int is_empty_stack(stack *s);
      void push_stack(stack *s, int elt);
      int pop_stack(stack *s);
      

   2. Sur la pile, on empile deux entiers (x et y) pour chaque case de coordonnées (x,y) à découvrir, en commençant par la case c.
   3. Pour simuler les appels récursifs, on introduit une boucle while qui, tant que la pile n'est pas vide, dépile la prochaine case à traiter et, si nécessaire, empile les coordonnées (x,y) pour les voisins concernés (attention: en ordre inverse par rapport aux appels).
   4. Quel est la hauteur maximale de la pile ?
   5. Vérifier que les cases sont découvertes dans le même ordre (exactement) avec un appel à la fonction uncover qu'avec un appel à la fonction uncover_it.
2. Dans un deuxième temps, on veut remplacer la pile par une file d'attente, et observer le résultat. Dans quel ordre les cases sont-elles découvertes ?