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.
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.
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 :
public boolean equals(Object o) permet, comme
d'habitude, de comparer deux cellules,
Coordinate moveTo(Direction dir) : renvoie les
coordonnées de la cellule voisine dans la direction dir (voir l'interface Direction dans Direction.java).
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) qui renvoie un booléen : true s'il existe un chemin qui mène à Némo en partant de start, false sinon. traverse est une méthode 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 :
ocean est l'océan à explorer,
start est la cellule de départ.
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.
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 :
deadEnd.path.
Cela nous conduit à l'algorithme récursif suivant :
is...(Coordinate c) de la classe Ocean) :
true.
false.
c on peut itérer sur toutes les directions
dans ocean.directions(), puis pour chacune appeler
c.moveTo(dir); une autre option consite à faire appel à la methode neighbours(Directions[] dir)) définie dans la classe Coordinate, qui renvoie la collection des coordonnées de tous les voisins d'une cellule.).
true, alors la cellule
courante fait partie d'un chemin qui mène à Nemo, on la
marque, donc, avec path et on renvoie true.
deadEnd et on
renvoie false.
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
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.
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, puis on inspèctera toutes ses cellules voisines qu'on rajoutera (pas les murs !) à la fin de la file (en y posant la marque par défaut).
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
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 :
Mark setMark(Coordinate c, int mark) de la
classe Ocean pose
une marque de valeur mark dans la cellule
c,
Integer getInteger(Ocean ocean, Coordinate c) de la classe Traversal récupère la marque de la cellule c sous forme d'un entier.
À 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
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(Ocean ocean, 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.
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
Déposez BreadthFirstWithShortestPath.java
Ç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
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