================================
Terminale NSI - Projet Rush Hour
================================

Objectifs du projet
=====================
* Écrire un programme python permettant la résolution d'un problème du jeu Rush-Hour
* Comprendre l'intérêt des arbres pour résoudre ce type de problème

Présentation du jeu
===================

Description générale
--------------------
*Rush Hour* est un casse-tête dont le but est de faire sortir d'un terrain de jeu rectangulaire une voiture, alors que le chemin vers la sortie est encombré par d'autres véhicules. Chaque véhicule se déplace soit horizontalement, soit verticalement (mais pas les deux).

En plus du plateau de jeu, le casse-tête contient une quarantaine de cartes représentant des configurations à résoudre.

Voici quelques images du jeu ainsi que des cartes de configuration :

.. image:: img/image1.jpg
   :width: 700px
   
.. image:: img/image2.jpg
   :width: 700px

Les voitures
------------
Pour pouvoir jouer, un plateau doit posséder au minimum 2 voitures. Le nombre de voiture et leurs positions initiales déterminent la difficulté pour résoudre une configuration.

Une voiture ne peut se déplacer que **verticalement** ou **horizontalement**.

La taille d'une voiture peut être de 2 ou 3 cases.

Pour gagner, il faut que la voiture rouge se retrouve devant la sortie de la grille située aux coordonnées [5;2].

Le plateau
----------
Le plateau de jeu est une grille de 6 lignes et 6 colonnes. 

La voiture rouge est toujours sur la troisième ligne et doit sortir à l'extrémité droite du plateau.

Travail à faire
===============

Pré-requis
----------
Ce TP guidé vous permet de construire le projet Rush-Hour étapes par étapes. Les notions suivantes sont des pré requis indispensables pour réaliser le projet :

* Les bases de la programmation sous python.
* Les notions de programmation orientée objet.
* La manipulation de la structure *File*.
* La manipulation de la structure *Arbre*.
* La notion de *parcours en largeur* d'un arbre.

Classes à disposition
---------------------
Vous avez à disposition les classes suivantes : 

* La classe Arbre permettant l'utilisation des Arbres : Arbre.py_
* La classe File permettant l'utilisation des Files : File.py_

.. _Arbre.py: ../src/Arbre.py

.. _File.py: ../src/File.py

De plus, vous avez à disposition 3 énumérations. Les énumérations ressemblent aux classes python avec l'avantage d'avoir des valeurs pré-définies. Vous avez à dispositions les énumérations suivantes : 

* Direction représentant les 4 valeurs des directions possible : *HAUT*, *BAS*, *DROITE*, *GAUCHE* : Direction.py_
* Sens représentant les 2 valeurs possibles : *HORIZONTAL* et *VERTICAL* : Sens.py_
* Taille présentant les tailles possibles : *DEUX* et *TROIS* : Taille.py_

.. _Direction.py: ../src/Direction.py

.. _Sens.py: ../src/Sens.py

.. _Taille.py: ../src/Taille.py

Pour chaque classe et énumération, leur utilisation est indiquée dans la documentation.

**Voici le diagramme des classes représentant la totalité du projet :**

.. image:: ../diagramme/classe.svg
   :width: 700px

Utilisation de la documentation
------------------------------
Vous avez à disposition l'ensemble de la documentation du projet. Cette documentation générée à l'aide de Sphinx vous sera très utile. Elle vous permet d'avoir toutes les informations nécessaires pour écrire les méthodes demandées comme : 

* L'utilité de la méthode
* Le détail de chaque paramètres et leurs types
* La valeur de retour (si elle existe) et son type

La documentation vous montre aussi des exemples de chaques méthodes pour comprendre leur utilisation.

.. image:: img/doc.jpg

Question 1
----------
Écrire la classe ``Voiture(x,y,lettre,sens,taille)`` avec son constructeur qui initialise chaques attributs. La valeur de l'attribut ``case`` sera complétée à la question suivante.

Question 2
----------
Une voiture est posée sur 2 ou 3 cases en fonction de sa taille. Dans la classe ``Voiture``, écrire une méthode ``generer_cases_utilises()`` qui retourne la liste les cases occupées par la voiture.
La valeur retournée par cette méthode sera stockée dans l'attribut ``case`` créé à la question précédente.

Question 3
----------
Dans la classe ``Voiture``,écrire la méthode ``__str__()`` qui retourne une chaine de caractères de la forme ``[<lettre>]``. Cette méthode est appelée lorsqu'on utilise la fonction ``print()`` avec l'objet voiture passé en paramètre.

Question 4
----------
Dans la classe ``Voiture``, écrire la méthode ``__eq__(voiture)`` qui teste l'égalité entre 2 voitures.

Question 5
----------
Dans la classe ``Voiture``, écrire la méthode ``info()`` qui retourne toutes les informations d'une voiture. Cette méthode n'est pas indispensable mais vous permettra de débugger votre programme en cas d'erreurs.

Question 6
----------
Écrire la classe ``CaseVide(x,y)`` avec son constructeur qui initialise chaque attribut.

Question 7
----------
Dans la classe ``CaseVide``,écrire la méthode ``__str__()`` qui retourne une chaine de caractères de la forme ``[ ]``. Cette méthode est appelée lorsqu'on utilise la fonction ``print()`` avec l'objet caseVide passé en paramètre.

Question 8
---------
Dans la classe ``CaseVide``, écrire la méthode ``info()`` qui retourne toutes les informations d'une case vide. Cette méthode n'est pas indispensable mais vous permettra de débugger votre programme en cas d'erreurs.

Question 9
----------
Écrire une classe ``Situation(liste_voiture)`` avec son constructeur qui initialise chaque attribut. La valeur de l'attribut ``grille`` sera complétée dans la question suivante.

Question 10
-----------
Dans la classe ``Situation``, écrire la méthode ``generer_grille(liste_voiture)`` qui retourne un tableau à deux dimensions représentant la situation.
La valeur retournée par cette méthode sera stockée dans l'attribut ``grille`` créé à la question précédente.

Question 11
-----------
Dans la classe ``Situation``, écrire la méthode ``afficher()`` qui permet d'afficher la grille représentant la situation. N'oubliez pas de prendre en compte la taille des voitures : pour une voiture de taille 3, il faut afficher ``[A][A][A]`` dans la grille.

Question 12
-----------
A l'aide des méthodes et des classes créés précédemment, essayer le code suivant pour générer et afficher une situation de 5 voitures. La voiture à déplacer sera toujours la dernier voiture passée en paramètre de la classe situation.

.. code:: python

          >>> a = Voiture(0,0,"A", Sens.HORIZONTAL, Taille.DEUX)
          >>> b = Voiture(4,4,"B", Sens.HORIZONTAL, Taille.DEUX)
          >>> c = Voiture(2,5,"C", Sens.HORIZONTAL,Taille.TROIS)
          >>> d = Voiture(0,1,"D", Sens.VERTICAL, Taille.TROIS)
          >>> x = Voiture(1,2,"X",Sens.HORIZONTAL,Taille.DEUX)

          >>> situation = Situation( [a,b,c,d,x])
          >>> situation.afficher()
          [A][A][ ][ ][ ][ ]
          [D][ ][ ][ ][ ][ ]
          [D][X][X][ ][ ][ ]
          [D][ ][ ][ ][ ][ ]
          [ ][ ][ ][ ][B][B]
          [ ][ ][C][C][C][ ]

Question 13
-----------
Dans la classe ``Situation``, écrire la méthode ``__eq__(situation)`` qui teste l'égalité entre 2 situations. On considère que 2 situations sont identiques lorsque leurs liste de voitures sont identiques.

Question 14
-----------
Dans la classe ``Situation``, écrire la méthode ``get_liste_voiture()`` qui retourne la liste des voitures triées par ordre alphabétique.

Question 15 
-----------
Dans la classe ``Situation``, écrire la méthode ``get_case_vide()`` qui retourne la liste des cases vides d'une situation.

Question 16
----------
Dans la classe ``CaseVide``, écrire la méthode ``get_voisins()`` qui retourne la liste des voisins d'une case vide.

Question 17
-----------
Créer une classe ``Mouvement(direction, voiture)`` avec son constructeur qui initialise chaque attribut.

Question 18
-----------
Dans la classe ``Mouvement``, écrire la méthode ``info()`` qui retourne toutes les informations d'une situation. Cette méthode n'est pas indispensable mais vous permettra de débugger votre programme en cas d'erreurs.

Question 19
-----------
A l'aide des méthodes ``get_case_vide()`` et ``get_voisins()``, écrire la fonction ``get_mouvements_possibles()`` dans la classe ``Situation``. Cette méthode retourne la liste des mouvements possibles.

Un mouvement est possible lorsque :

* Une case vide est voisine avec une voiture
* Cette même case vide est dans un sens adéquat permettant le déplacement d'une voiture

Question 20
-----------
Dans la classe ``Voiture``, écrire la méthode ``move(direction, situation)`` qui **effectue le déplacement** dans une direction et **retourne la nouvelle situation** après déplacement.

Déplacement
~~~~~~~~~~~
Cette méthode doit réaliser le déplacement de la voiture. A l'aide de l'énumération ``Direction``, il est facile de calculer les prochaines coordonnées d'une voiture.

Il suffit d'ajouter les coordonnées de déplacement aux coordonnées de la voiture.

Mise à jour
~~~~~~~~~~~
N'oubliez pas de mettre à jour les coordonnées des cases dans l'attribut ``case`` et de régénérer la grille de la nouvelle situation.

Attention aux problèmes de mutabilité, il faudra effectuer une copie de la liste des voitures pour la nouvelle situation.

Question 21
-----------
Dans la classe ``Mouvement``, écrire une méthode ``execute(situation)`` qui retourne la nouvelle situation après déplacement. Cette méthode utilisera la méthode ``move()``.

Question 22
-----------
Dans la classe ``Situation``, écrire une méthode ``est_gagnante()`` qui indique si une situation est gagnante ou non. 
Une situation est gagnante lorsque la voiture "XX" est aux coordonnées ``[4;2]``.

Question 23
-----------
Dans la classe ``Situation``, écrire une méthode ``get_situation_suivantes_possibles()`` qui retourne la liste des situations suivantes. Vous utiliserez la méthode écrite ci-dessus ``get_mouvements_possibles()``
Chaque élément de la liste sera un tuple de la forme ``( <situation>,<mouvement_effectue> )``.

Question 24
-----------
Dans la classe ``Situation``, écrire la méthode ``résoudre()`` qui trouve la solution gagnante du Rush-Hour. 
Cette méthode génère toutes les situations possibles et construit un arbre au fur et à mesure. 
Chaque nœud de l'arbre est un tuple de la forme ( <situation>,<mouvement_effectue> ).


Pour vous aider
~~~~~~~~~~~~~~~
La recherche de la solution consiste à parcourir l'arbre de toutes les situations possibles. Les nœuds sont des situations et les branches sont les mouvements à effectuer pour atteindre une situation.

.. image:: img/image3.png

Pour trouver la solution en un minimum de coups, on effectuera un parcours en largeur de cet arbre grâce à une file.

Au départ, la file ne contient que notre situation initiale. Ensuite, on y ajoute les situations suivantes possibles après notre situation initiale.

Tant que la situation n'est pas gagnante, on défile la file afin de trouver de nouvelles situations et on y ajoute les nouvelles situations trouvées.

Afin d'éviter un arbre infini, on ajoute les situations dans la file uniquement si : 

* La situation n'est pas encore connue
* La situation n'est pas déjà dans la file (cad, en attente de traitement)

Question 25
-----------
Dans la classe ``Situation``, écrire une méthode ``get_mouvement_solutions(arbre)`` qui retourne une liste de mouvements ordonnée à faire pour résoudre le Rush-Hour.

Chaque élément de la liste sera une liste de la forme [ [<mouvement_à_faire>,<occurrence>] ].
Elle permettra un meilleur affichage des données pour l'utilisateur.

Pour trouver la liste des mouvements, il suffit de remonter l'arbre contenant la situation finale grâce à l'attribut ``parent`` de chaque arbre. 


Question 26
-----------
Dans un fichier ``Main.py``, écrire un programme permettant de résoudre cette situation et qui affiche la liste des mouvements à faire pour résoudre la situation.

.. code:: python

        v = Voiture(0,0,"V", Sens.HORIZONTAL, Taille.DEUX)
        l = Voiture(0,1,"L",Sens.VERTICAL, Taille.TROIS)
        j = Voiture(5,0,"J",Sens.VERTICAL,Taille.TROIS)
        o = Voiture(0,4,"O",Sens.VERTICAL,Taille.DEUX)
        x = Voiture(1,2,"X",Sens.HORIZONTAL, Taille.DEUX)
        t = Voiture(2,5,"T",Sens.HORIZONTAL, Taille.TROIS)
        c = Voiture(4,4,"C",Sens.HORIZONTAL, Taille.DEUX)
        b = Voiture(3,1,"B",Sens.VERTICAL, Taille.TROIS)

        situation = Situation([v,l,j,o,t,c,b,x])

