Consignes

Vous devrez utiliser l'interface TPLab pour envoyer vos TP aux encadrants de TP.

Liens utiles

• la page du langage Python
• la page de la documentation de la librairie standard de Python
• un livre d'apprentissage de la programmation en Python (en français) (lien direct (pdf)) Pour les chaînes de caractères, reportez vous au début de la partie 10.

• email des enseignants
  • Chambéry : Pierre.Hyvernat@univ-savoie.fr, Tom.Hirschowitz@univ-savoie.fr, Flavien.Vernier@univ-savoie.fr, Christine.Ferraris@univ-savoie.fr
  • Annecy : Francoise.Deloule@univ-savoie.fr, lionel.valet@univ-savoie.fr et Ilham.Alloui@univ-savoie.fr.

Pour le TP, vous aurez besoin de :

• fichier demineur.py
• Les 6 images pour le jeu sont les suivantes : , , , , et . Si vous souhaitez les modifier, vous pouvez les télécharger dans le même répertoire que le fichier python et modifier leurs déclararations dans le fichier.

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

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.

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

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

2. Se familiariser avec la structure du plateau

2.1. Initialisation

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

• "mine" qui est un booléen et qui indique si la case contient une mine
• "etat" qui indique l'état de la case :
  • un nombre entre 0 et 8 qui représente le nombre de mines voisines
  • -1 si le joueur n'a pas encore découvert la case,
  • -2 si le joueur a découvert la case, et qu'elle contient une mine.

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 :

• INCONNU = -1
• PERDU = -2

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} ]
]

est un plateau de 9 cases (3 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 accède donc à la case (i,j) d'un tels plateau de la manière suivante :

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

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

Une fois que vous avez écrit cette fonction, vous pouvez commencer à jouer au démineur. Le seul problème, c'est qu'il n'y a pas de mine sur le plateau !

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 un instant.

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)".

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),

• si la case était déjà découverte (etat != INCONNU), on s'arrête,
• sinon :
  1. on compte le nombre de mines voisines : c,
  2. on met à jours cette case dans le plateau (etat = c),
  3. on teste :
     • si la case a au moins une mine parmi ses voisine, on s'arrête,
     • si la case n'a aucune mine parmi ses voisines, on recommence la fonction récursivement sur toutes les cases voisines.

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...

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 ».

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.

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érer toutes les mines voisines et veut donc découvrir les cases voisines restantes.

4.4. Améliorations (Bonus)