TD 9 : Finding Nemo

 Login :  Mot de passe :

Préambule

En ce jour le monde aquatique est en émoi : le petit Nemo a été enlevé ! Marin, son pauvre papa, doit partir à sa recherche. Mais attention : l'océan est un vrai labyrinthe, peuplé de requins affamés ! Sauras-tu aider Marin à retrouver Nemo le plus rapidement possible, et en évitant les requins tant que faire se peut ?

Comme tout le monde le sait, l'océan se présente sous la forme d'un labyrinthe carré, comme dans l'image ci-dessus. Marin occupe initialement la case rouge, Nemo la case orange, et les requins les cases noires. Les cases gris foncé sont des falaises infranchissables.

À télécharger

Extraire le répertoire src de l'archive src.zip et placer son contenu dans celui du projet.

Extraire le contenu du fichier data.zip à la racine du projet (avec le dossier data).

Contrairement aux TDs précédents, vous allez voir d'autres paquets que (default package):

Le paquet (default package) contient, comme d'habitude, les fichiers que vous allez utiliser pour votre travail : les classes à modifier et les tests. Les autres paquets contiennent les classes utilisés pour mettre en place l'infrastructure du TD.

Bref résumé de la structure du code fourni

Un résumé plus long de la structure du code fourni est disponible ici. Par ailleurs, tout le code fourni est commenté en utilisant la convention JavaDoc. Vous pouvez consulter la documentation générée à partir de ces commentaires.

En machine (et dans le paquet ocean), l'océan est modélisé par une matrice pleine dont chaque cellule — identifiée par la paire de ses coordonnées en utilisant la classe Coordinate (voir Coordinate.java) — correspond à une case du labyrinthe. Les relations d'adjacence sont implicites, chaque cellule ayant par convention 4 voisines : une à gauche (ouest), une en-dessous (sud), une à droite (est), une au-dessus (nord). La classe Coordinate fournit, entre autres, les méthodes suivantes pour manipuler les cellules :

Vous allez implémenter plusieurs algorithmes de parcours de l'océan. Chaque algorithme devra être implémenté dans la méthode traverse(Ocean ocean, Coordinate start) d'une classe dérivée de la classe abstraite Traversal (dans le fichier Traversal.java). Traversal est une classe abstraite puisque cette méthode y est déclarée sans justement être implémentée. La signification des arguments de cette méthode est la suivante :

La plupart de temps, start désignera les coordonnées de la case où se trouve Marin, mais, en général, ça peut être n'importe quelle cellule !

L'affichage de l'océan est codé dans le paquet graphics, dans les classes OceanCanvas (pour la partie générique) et BasicOceanCanvas (pour la partie spécifique au maillage carré). Vous n'avez pas à vous préoccuper de ces classes. Toutefois, vous pouvez exécuter celle BasicOceanCanvas si vous le désirez : cela affichera simplement l'image en début de l'énoncé dans une fenêtre.

1. Parcours en profondeur

Note : Dans cette partie du TD, on ne se préoccupe pas des requins.

De tempérament obtus et inquiet, Marin a tendance à foncer droit devant sans trop réfléchir. Ce comportement, que certains pensent typique pour un poisson clown, sera modélisé par un parcours en profondeur, que vous devez implémenter dans la méthode traverse(Ocean ocean, Coordinate start) de la classe DepthFirst. Cette méthode doit être récursive et renvoyer true si, dans ocean, il existe un chemin de start à Nemo.

Afin de ne pas se perdre dans l'océan et pouvoir suivre Marin à la trace, nous adopterons l'approche classique, qui consiste à marquer les cellules par lesquelles nous sommes déjà passés. Tout objet dont la classe implémente l'interface Mark (voir Mark.java) peut servir de marque. Ici, nous utiliserons trois marques : la marque par défaut, que l'on pose avec ocean.setMark(c) (pour une cellule c) et deux marques, deadEnd et path, définies dans la classe Traversal. Puisque la classe DepthFirst est dérivée de celle Traversal, vous pouvez utiliser ces marques directement. Par exemple, on pose la marque path dans la cellule c avec ocean.setMark(c, path).

Nous allons procéder ainsi :

Cela nous conduit à l'algorithme récursif suivant :

Attention : Lorsque vous parcourez les voisines d'une cellule, il faut bien vérifier qu'elles soient effectivement à l'intérieur de l'océan. Remarquez que le nôtre est entouré d'une falaise, mais ce ne sera pas forcément le cas en général. Cette vérification peut se faire en utilisant la méthode isValid(Coordinate c) de la classe Ocean, qui renvoie true si c est bien la coordonnée d'une cellule de l'océan.

Visualisez l'exploration avec la classe DepthFirst.

Le comportement de l'algorithme est illustré dans l'animation ci-dessous (l'image de droite montre l'état final). Vous voyez la couleur rouge (correspondant à la marque par défaut) apparaître quand la pile d'appels se remplit et les couleurs bleu (path) et violet (deadEnd) quand elle se vide.

NB : L'ensemble des cellules déjà visitées est encodé dans les marques. Il n'est donc pas nécessaire de les stocker explicitement par ailleurs.

Testez votre code en utilisant Test1.java, puis déposez DepthFirst.java

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

2. Parcours en largeur

Note : Dans cette partie du TD, on ne se préoccupe toujours pas des requins.

Bonne nouvelle ! Grâce à l'intervention de Dory, Marin va recevoir l'aide d'un banc de poissons argentés. Il va donc pouvoir les lancer dans toutes les directions à la fois, et le premier d'entre eux qui trouvera Nemo le signalera immédiatement. Ce processus sera modélisé par un parcours en largeur.

2.1 Parcours simple

Complétez la méthode traverse(...) de la classe BreadthFirst. La méthode doit implémenter (itérativement) le parcours en largeur, s'arrêtant dès que Nemo est trouvé.

Afin de réaliser le parcours en largeur, on stockera les coordonnées des cases en cours de traitement dans une file d'attente représentée par LinkedList<Coordinate>. On commencera par mettre start dans la file. À chaque itération, on piochera une cellule au début de la file pour la traiter (en y posant la marque par défaut), puis on rajoutera toutes ses cellules voisines (pas les murs !) à la fin de la file.

On ne demande pas de reconstituer le chemin de Marin à Nemo pour l'instant.

Visualiser l'exploration avec la classe BreadthFirst. Le comportement de l'algorithme est illustré dans l'animation ci-dessous :

Testez votre code en utilisant Test21.java, puis déposez BreadthFirst.java

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

2.2 Distances au point de départ

Complétez la méthode traverse(...) de la classe BreadthFirstWithDistance. Cette méthode implémente le même parcours en largeur, mais, à la place de la marque par défaut, utilise des nombre entiers, les augmentant au fur et à mesure du parcours. Pour le marquage des nombres entiers, vous disposez de deux méthodes suivantes :

À la fin du parcours, la distance entre Marin et Nemo sera affichée automatiquement dans la console (vous n'avez rien à faire pour cela). Visualiser l'exploration avec la classe BreadthFirstWithDistance. Dans la console, vous devez obtenir la sortie suivante :

    Distance : 104

Attention : On demande un algorithme de complexité linéaire ! Son comportement est illustré dans l'animation ci-dessous. Les couleurs changent au fur et à mesure que la distance à la cellule initiale augmente (comme pour les exercices précédents, vous n'avez pas à vous préoccuper de l'affichage, c'est fait automatiquement dans la classe fournie OceanCanvas).

Testez votre code en utilisant Test22.java, puis déposez BreadthFirstWithDistance.java

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

2.3 Chemin le plus court

Complétez la méthode traverse(...) de la classe BreadthFirstWithShortestPath. Cette méthode implémente le même parcours en largeur, mais marque chaque cellule par la direction de retour (c'est-à-dire, la direction opposée à celle par laquelle nous y sommes arrivés). On peut obtenir la direction opposée à une direction dir donnée avec la méthode getOpposite() de l'interface Direction : dir.getOpposite().

Complétez maintenant la méthode backTrack(Ocean ocean, Coordinate current) de la classe BackTrackingTraversal, qui part de la cellule current et retrace le chemin parcouru, en sens inverse, suivant les marques. Pour récupérer la direction marquée dans une cellule, vous pouvez utiliser la méthode getDirection(Coordinate c) fournie par la classe Traversal. Cette méthode renvoie null si la marque posée dans la cellule c n'est pas une direction. Chaque cellule traversée durant ce rebroussement sera marquée par path. (Attention : La condition d'arrêt ne devra pas faire appel à la méthode isMarlinAt(Coordinate) de la classe Ocean.)

Remarquez que la classe BreadthFirstWithShortestPath étend celle BackTrackingTraversal, qui, elle-même, étend Traversal. Par conséquence, toutes les méthodes de ces deux dernières classes sont accessibles dans BreadthFirstWithShortestPath. Ainsi, on peut utiliser la méthode backTrack(...) dans BreadthFirstWithShortestPath.traverse(...). Elle devra être appelée lorsque Nemo est retrouvé afin de marquer le chemin de Marin à lui.

Visualiser l'exploration avec la classe BreadthFirstWithShortestPath. Le comportement de l'algorithme est illustré dans l'animation ci-dessous :

Testez votre code en utilisant Test23.java.

Déposez BackTrackingTraversal.java

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

Déposez BreadthFirstWithShortestPath.java

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

3. Éviter les requins

Ça y est, cette fois on se préoccupe des requins ! Nous utiliserons le même océan, sauf qu'une falaise a été remplacé par un requin. Si vous exécutiez à nouveau la méthode main(...) de la classe BreadthFirstWithShortestPath en y remplaçant au préalable "no-sharks.txt" par "one-shark.txt", vous constateriez qu'elle calcule un chemin passant par ce requin, tandis que d'autres chemins certes plus longs l'évitent. On désire maintenant modifier le parcours afin qu'il calcule un chemin rencontrant un minimum de requins.

Pour cela on va simplement remplacer la file utilisée dans le parcours par une file à double entrée (double-ended queue ou simplement dequeue en Anglais). Le principe de cette file est d'avoir deux entrées, l'une par l'avant, l'autre par l'arrière, et une seule sortie par l'avant. Pour l'implémentation on utilisera encore une LinkedList<Coordinate>.

Complétez la méthode traverse(...) de la classe AvoidSharks. Le parcours en largeur est modifié comme suit : lorsqu'on se trouve à une cellule donnée et qu'on inspecte ses voisines accessibles, on insère celles qui ont des requins par l'arrière dans la file, et celles qui n'en ont pas par l'avant. Ainsi, les cellules du labyrinthe accessibles sans passer par aucun requin sont visitées en premier, puis c'est au tour des cellules accessibles en passant par un seul requin, puis en passant par 2 requins, et ainsi de suite. Ce comportement est illustré dans l'animation ci-dessous obtenue en lançant la méthode public static void main(String[] args) de la classe AvoidSharks. La preuve est très similaire à celle de l'invariant de distance pour le parcours en largeur.

Vous pouvez maintenant tester votre code sur d'autres labyrinthes. La classe FindNemo lance tous les algorithmes de parcours à la suite sur la carte "many-sharks.txt" (vous pouvez changer la carte pour "no-sharks.txt" ou "one-shark.txt"). Voici ci-dessous les comportements des divers parcours implémentés durant le TD sur cet océan (de haut en bas : parcours en profondeur, parcours en largeur classique, parcours en largeur modifié) :

Testez votre code en utilisant Test3.java, puis déposez AvoidSharks.java

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

4. Question complémentaire

Vous avez dû vous apercevoir que le parcours ainsi réalisé n'est ni un parcours en largeur, ni un parcours en profondeur, mais un mix des deux. Cela se voit bien sur les océans de la partie 3. La raison de ce comportement est qu'une dequeue est la concaténation d'une pile et d'une file. Lors du parcours, on vide d'abord la pile, puis, lorsque celle-ci est vide, on commence à vider la file qui elle-même se transforme alors en pile, et ainsi de suite. La conséquence de ce comportement est que le chemin obtenu en sortie n'est pas toujours le plus court parmi ceux qui rencontrent le moins de requins. C'est ennuyeux car le pauvre Marin risque de se fatiguer inutilement ! Comment remédier à ce défaut ? Plus précisément, comment modifier le parcours pour qu'il calcule un chemin de longueur optimale parmi ceux qui rencontrent le moins de requins? Saurez-vous le faire en restant de complexité linéaire ?

Complétez la méthode traverse(...) de la classe Bonus, puis lancez sa méthode main(...) :

Testez votre code en utilisant la classe Test4.java, puis déposez Bonus.java

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer


Une solution vous est proposée.