Consignes

La note ne valide pas seulement le résultat de votre programme, mais également son style :

Vérifiez ces points avant de demander à votre intervenant de valider votre code.

Liens utiles

Pour le TP, vous aurez besoin de :

Objectifs du TP

  1. Découvrir :
    • l'interface graphique
    • les fonctions recursives
  2. se familiariser avec :
    • les structures de données complexes (listes de listes de dictionnaires)

1. Préliminaires : fonctions récursives

Pour cette partie, n'écrivez rien dans le fichier demineur.py, mais testez directement les fonctions dans l'interprète ou dans un autre fichier.

Une fonction est récursive si elle s'appelle elle même. Le risque avec ce genre de définition, c'est qu'elles risquent de ne jamais s'arrêter. C'est un peu comme une boucle while : le programmeur doit se débrouiller pour mettre une condition d'arrêt.

Écrivez la définition suivante dans l'interprète et testez la : 

def affiche(n):
    if n>0:
        print(n)
        affiche(n-1)  # appel récursif

S'agit il d'une fonction, ou d'une procédure ?

Que se passe t'il si on donne un argument négatif à affiche ?

Testez la définition suivante : 

def fonction_mystere(n):
    if n <= 1:
        return 1
    else:
        resultat = n * fonction_mystere(n-1)  # appel récursif
        return resultat

S'agit il d'une fonction, ou d'une procédure ?

Que calcule cette définition ?

2. Se familiariser avec la structure du plateau

À partir de maintenant, vous devez travailler dans le fichier demineur.py.

2.1. Initialisation

Chaque case du démineur est représentée par un dictionnaire avec deux cases :

Par exemple : 

>>> c1 = { "mine" : True , "etat" : -2 }
>>> c2 = { "mine" : False , "etat" : -1 }

Pour simplifier la vie, des constantes sont définies au début du fichier :

Le déclarations précédentes seront donc écrites comme : 

>>> c1 = { "mine" : True , "etat" : PERDU }
>>> c2 = { "mine" : False , "etat" : INCONNU }

Le plateau est un tableau de tableaux de cases. (On parle de tableau à deux dimensions.) Chaque élément du tableau représente un colonne, qui est elle même un tableau de cases : 

>>> c0 = { "mine" : False , "etat" : INCONNU }
>>> plateau = [
  [ {"mine": False, "etat": INCONNU},   {"mine": False, "etat" : 1},        {"mine": False, "etat": INCONNU} ],
  [ {"mine": False, "etat": INCONNU},   {"mine": True, "etat" : INCONNU},   {"mine": False, "etat": INCONNU} ],
  [ {"mine": False, "etat": INCONNU},   {"mine": True, "etat" : INCONNU},   {"mine": False, "etat": INCONNU} ]
  [ {"mine": True,  "etat": INCONNU},   {"mine": True, "etat" : INCONNU},   {"mine": False, "etat": INCONNU} ]
]

est un plateau de 12 cases (4 colonnes et 3 lignes), avec 2 mines (milieu de la deuxième colonne et milieu de la troisième colonne) et une case découverte (milieu de la première colonne).

On numérote les cases par des paires (i,j), où i est un numéro de colonne et j un numéro de ligne (en partant du coin en haut à droite). On peut donc accèder à une case de la manière suivante : 

>>> plateau[1][2]
{'etat': -1, 'mine': False}

Il s'agit de la deuxième colonne, troisième ligne...

Le fichier demineur.py contient une fonction "genere_plateau(largeur,hauteur,probabilite_mine=0)" qui crée un plateau de la taille donnée. L'argument probabilite_mine n'est pas utilisé.

Modifiez cette fonction pour utiliser l'argument "probabilite_mine" qui est un flottant compris entre 0 et 1. Ce nombre donne la probabilité que chaque case contienne une mine. Par exemple, si on appelle la fonction avec les arguments genere_plateau(10,20,0.25), chaque case aura une chance sur 4 (0.25 = 1/4) de contenir une mine.

Remarque : la fonction "random.random()" génère un nombre flottant aléatoire entre 0 et 1.

Pour vérifier que votre fonction fonctionne correctement, vous pouvez lancer le programme et appuyer sur la touche "m" qui montre les positions des mines pendant quelques secondes.

2.2. Compter les mines voisines

Lorsque l'on clique sur une case vide (qui ne contient pas de mine), il faut compter le nombre de mines voisines de la case pour pouvoir l'afficher. Il y a huit cases voisines de la case "(x,y)".

  1. Écrivez la fonction "dans_plateau" qui renvoie "True" si la case "(x,y)" est à l'intérieur du plateau, et "Faux" si la case "(x,y)" est à l'extérieur,

  2. écrivez la fonction "cases_voisines" qui renvoie la liste des coordonnées des voisins de "(x,y)" (vous pouvez utiliser la fonction dans_plateau pour simplifier votre fonction),

    Pour tester, vous pouvez lancer le programme avec la touche F5. La plateau sera affiché, et lors de l'appui sur la touche m, chaque case contiendra le nombre de cases voisines. Vérifiez que ce nombre est correct avant de continuer.

  3. écrivez la fonction "compte_mines_voisines" qui compte le nombre de mines dans les cases voisines de "(x,y)".

    N'oublier pas de tester.

3. Calcul de la composante connexe

La partie complexe du démineur est la propagation des cases sûres : si une case sans mine n'a aucun voisin avec une mine, on peut automatiquement découvrir les cases voisines, etc. C'est ceci qui permet d'obtenir la configuration de droite en un seul clic sur le coin supérieur gauche :

On parle de composante connexe : on découvre toutes les cases qui ne contiennent rien (ni de mine, ni un entier strictement supérieur à 0), en s'arrêtant aux cases qui contiennent un entier strictement supérieur à 0.

Le plus simple pour programmer cette opération est d'utiliser une fonction récursive. Le calcul de la composante connexe au démineur se fait de la manière suivante : pour une case donnée (sans mine),

Cette fonction s'arrête forcement au bout d'un moment car on ne fait pas d'appel récursif si la case de départ était déjà découverte. Comme toutes les cases qu'on explore sont découvertes, il ne peut pas y avoir de boucle infinie...

En suivant les instructions si dessus, programmez la procédure composante_connexe.

Attention : il s'agit d'une procédure qui modifie son argument plateau au fur et à mesure de la propagation des cases vides. Vous pouvez cependant employer l'instruction "return" (sans argument) pour arrêter la fonction.

Pour tester si votre fonction marche, il suffit de jouer au démineur !

4. Interface graphique

4.1. Drapeau

Dans la version originale du démineur, on peut également poser un drapeau ou un point d'interrogation sur une case non découverte. Le drapeau signale qu'on est sûr qu'une mine est présente alors que le point d'interrogation signale qu'il est possible que la case contienne une mine. Pour poser un drapeau, il suffit de cliquer avec le bouton droit de la souris sur une case. Pour transformer le drapeau en point d'interrogation, il suffit d'un deuxième clic droit. Un troisième clic droit remettra la case à l'état inconnu.

La procédure d'affichage gère les états INCONNU / DRAPEAU / QUESTION. Il faut donc simplement rajouter un évènement « clic droit » avec la commande associée...

La gestion du clic pour découvrir une case se fait grâce aux lignes 

def __action_clic(clic):
    """Fonction appelée quand on fait un clic sur la fenêtre."""
    ...

grille.bind("<Button-1>", __action_clic)

qui déclarent une procédure et la lie à l'évènement « clic ».

Ajoutez un évènement clic droit et la commande correspondante pour gérer les drapeaux / points d'interrogation.

Remarque : les boutons de la souris sont numérotés :

Si votre souris n'a que deux boutons (souris Apple par exemple), le bouton droit prendra probablement le numéro 2...

4.2. Fin du jeu

Pour le moment, lorsqu'on découvre une case qui contient une mine, celle-ci s'affiche en rouge et la partie continue.

  1. Écrivez une fonction 

        def perdu(plateau):
	"""renvoie True lorsque que le plateau contient une case découverte avec une mine"""
  2. Ajoutez un test au début de la fonction __action_clic pour que les clics n'aient plus d'effet lorsque la partie est perdue.

  3. Écrivez également une fonction qui permet de tester si le joueur a mis les drapeaux exactement sur les cases minées et qu'il a découvert toutes les autres cases. Si c'est le cas, il faut aussi arrêter la partie car le joueur a gagné.

  4. Modifiez la fin de la fonction __action_clic pour afficher une fenêtre de dialogue "PERDU" ou "GAGNÉ" lors du dernier clic. Pour cela, vous pouvez utiliser 

        from tkinter import messagebox
    ...
    messagebox.showinfo("bravo !", "Bravo ! Vous avez gagné...")

BONUS

Modifiez la fonction dessine_case pour qu'elle utilise l'image (l'image s'appelle mauvais_drapeau_img dans le code Python fourni) lorsqu'elle affiche une mine injustement repérée en mode solution.

4.3. bouton du milieu

Dans le jeu original, un clic du milieu sur une case découverte était équivalent à des clics sur toutes les cases voisines. Ceci ne fonctionnait que lorsque le nombre de mines voisines et le nombre de drapeaux voisins coïncidaient. Dans ce cas, le joueur pense avoir repéré toutes les mines voisines et veut donc découvrir les cases voisines restantes.

Ajoutez la gestion du bouton du milieu.

4.4. Améliorations (Bonus)

Apportez des améliorations :