TD 9

Rush Hour

Préambule

Création d'un projet dédié au TD9

1. Lancez Visual Studio Code (VS Code par la suite), par exemple en exécutant la commande code dans le terminal, ou en cliquant sur un raccourci; la touche [Alt] fait apparaître / disparaître la barre du menu horizontale.
2. Dans VS Code tapez la combinaison de touches [Ctrl]+[Shift]+[P] (ou [Alt]+[V] puis cliquez sur command Palette) puis tapez «java: create» dans la barre qui apparaît et sélectionnez Create Java Project et l'option No build tools.
3. Une fenêtre s'ouvre et vous invite à choisir votre espace de travail.
4. Indiquez le nom de votre projet (TD9) dans la barre de texte.

Activer assert dans votre machine virtuelle Java

Consignes de programmation

Nommez les classes, variables et méthodes exactement comme le demande l'énoncé.

Pour des questions relatives à la syntaxe de Java, consultez ce mémento.

Documentation

Pour obtenir la description d'une classe Java standard, consultez internet. Il suffit souvent d'effectuer une recherche en indiquant Java suivi du nom de la classe dont vous souhaitez la documentation (e.g. Java LinkedList ou Java Array).

La documentation officielle (internet) est ici : Java 11.

Afin de minimiser les risques d'erreurs de manipulation lors des dépôts de fichiers, toutes les classes que vous avez à modifier sont réunies dans un même fichier TD9.java que vous devez déposer après chaque question.

On rappelle néanmoins qu'en dehors de circonstances exceptionnelles, on écrit plutôt des classes différentes dans des fichiers différents, tant pour la lisibilité du code que pour l'efficacité de la compilation.

Jeu Rush Hour et but du TD

Rush Hour est un jeu de la société Thinkfun dont le but consiste à dégager une voiture d'un embouteillage. Les véhicules se déplacent sur une grille 6x6, soit horizontalement, soit verticalement. Chaque véhicule occupe 2 ou 3 cases de long. Les véhicules ne peuvent pas sortir du plateau, à l'exception de la voiture rouge qui peut sortir par la droite du plateau ; c'est là le but du jeu. Voici un exemple de configuration de départ :

L'objectif de ce TD est d'écrire un programme qui trouve la solution d'un tel problème, en un minimum de déplacements.

Si vous souhaitez vous familiariser avec ce jeu, vous pouvez jouer par exemple ici.

À télécharger

1. Représentation du problème

On adopte la représentation suivante du problème. Les 6 lignes sont numérotées de haut en bas, de 0 à 5, et les 6 colonnes de gauche à droite, de 0 à 5. La classe RushHour modélise un plateau de jeu général décrit par les cinq champs suivants :

• int nbCars : le nombre de véhicules ;
• String[] color : un tableau donnant la couleur de chaque véhicule (pour l'affichage de la solution) ;
• boolean[] horiz : un tableau de booléens indiquant pour chaque véhicule s'il se déplace horizontalement ;
• int[] len : un tableau donnant la longueur de chaque véhicule (len[i] représente le nombre de cases occupées par le véhicule i, et vaut 2 ou 3);
• int[] moveOn : un tableau indiquant sur quelle ligne (resp. colonne) se déplace un véhicule horizontal (resp. vertical).

Par convention, la voiture rouge est le véhicule d'indice 0 et de longueur 2.

L'état du plateau à un moment du jeu est représenté par un objet de la classe State qui contient les champs suivants :

• RushHour plateau : un pointeur vers un objet de la classe RushHour qui modélise les invariants du plateau de jeu.
• int[] pos : un tableau indiquant la position de chaque véhicule (la colonne la plus à gauche d'un véhicule horizontal ou la ligne la plus haute d'un véhicule vertical) ;
• int c, int d et State prev : indiquent que cet état a été obtenu à partir de l'état prev en déplaçant la voiture c de d cases (d vaut -1 ou +1 : -1 indique un déplacement vers la gauche ou vers le haut, +1 indique un déplacement vers la droite ou vers le bas);

• Complétez le constructeur State(RushHour plateau, int[] pos) de la classe State qui construit un état initial (les champs c, d et prev ne sont pas significatifs dans ce cas).
• Complétez le constructeur State(State s, int c, int d) de la classe State qui construit un nouvel état à partir de s en déplaçant la voiture c de d case (d vaut -1 ou +1). On suppose que ce déplacement est possible.
  Attention : Il faut bien penser à instancier le champ plateau et le champ prev.
• Complétez la méthode boolean success() de la classe State qui indique s'il s'agit d'un état correspondant à une fin de partie (i.e. la voiture rouge est située immédiatement devant la sortie).

Déposez le fichier TD9.java :

• boolean equals(Object o) de State qui renvoie true si l'objet o correspond au même état de jeu que l'état courant (quelque soit leur champ prev).
• boolean[][] free() qui renvoie un tableau result de booléens indiquant quelles sont les places libres dans l'état courant. On adoptera la convention que result[i][j] représente la case sur la ligne i et la colonne j. On utilisera le pointeur plateau pour accéder aux champs nbCars, horiz, len et moveOn de la configuration générale du jeu.

Déposez le fichier TD9.java :

2. Déplacements possibles

À partir de maintenant, on ne travaille plus que dans la classe RushHour.

Déposez le fichier TD9.java :

3. Recherche d'une solution

On s'attaque maintenant à la recherche d'une solution, grâce à un parcours d'exploration des états du jeux.

3.1 Parcours en profondeur

• il faut mémoriser les états que l'on a déjà rencontrés, et pour cela on va utiliser un ensemble visited de type HashSet<State> ; pour l'utiliser, on dispose des méthodes contains et add;
• On utilise une pile qui contiendra au départ l'état initial. Tant qu'elle n'est pas vide, on extrait le premier état de la pile. S'il correspond à une solution on a terminé. Sinon on ajoute tous ses voisins non déjà rencontrés dans la pile et dans l'ensemble visited.

Déposez le fichier TD9.java :

3.2 Parcours en largeur

Si on représente l'ensemble des états par un arbre dont la racine est l'état de départ et dont chaque noeud s a pour enfants les états que l'on peut atteindre à partir de s en effectuant un déplacement, on souhaite parcourir les noeuds de cet arbre « par niveaux », comme ceci :

                   1
                  / \
                 /   \
                2     3
              / | \   | \
             4  5  6  7  8
            /...

Déposez le fichier TD9.java :

4. Affichage d'une solution

Question 4 : Compléter la méthode void printSolution(State s) qui affiche une solution, étant donné l'état s correspondant à la solution (l'état final). On note que les états formant la solution sont chaînés à partir de s en suivant le champ prev. On s'appliquera à afficher la solution dans le bon ordre.

Cette méthode doit également afficher le nombre total de déplacements. On pourra ajouter un champ statique nbMoves à la class RushHour pour cela.
On utilisera possiblement une version récursive pour ce faire.

Testez votre code en exécutant le fichier Test4.java, qui doit donner quelque chose comme :

46 déplacements
on déplace le véhicule bleu vers la droite
on déplace le véhicule noir vers la droite
on déplace le véhicule vert vers le haut
on déplace le véhicule rose vers le bas
....

Note : votre solution peut différer de celle-ci (cela dépend de la façon dont la liste est construite par moves) mais elle doit comporter le même nombre de déplacements (46).

Déposer le fichier TD9.java :