Un Bug et des labyrinthes

../../_images/laby0.png

Les objectifs de ce TP sont :

  • Écrire des algorithmes simples mettant en œuvre des structures alternatives et itératives, puis les traduire en programme à l’aide de l’API des Bugs.

  • Concevoir des variantes plus ou moins élaborées pour résoudre le problème.

  • Utiliser la méthode random() de la classe Math.

Défi n°1 : L’idiot du Bug world

État initial

  • Un Bug dans un labyrinthe de 4x4 cases, avec pour position initiale la case (0,0).

  • Un biscuit sur la case (3,0).

Résultat attendu

  • Le Bug est parvenu jusqu’à la case du biscuit en n’utilisant que les méthodes avance(), droite() et gauche().

  • Le bug a ramassé le biscuit.

  • Le Bug a émis un message signalant qu’il avait pris le biscuit.
../../_images/init0.png ../../_images/result0.png

À faire

  1. Récupérer l'archive du programme et l’enregistrer dans le dossier du TP.

  2. Se placer dans le dossier puis décompresser l’archive :

    file-roller --extract-to=. TP_Buglaby.tar.gz

    Le programme comprend les mêmes classes et fichiers que pour le TP précédent. Se reporter à l’énoncé de ce dernier pour les détails et pour la référence de l’API (en cliquant ici).

  3. Récupérer le fichier de définition des murs et biscuits mazeData1.txt et l’enregistrer dans le dossier des sources.

  4. Ajuster les paramètres du bug world comme suit

    final int[][] casesColorees = {

};
final int N_BUGS=1;  // nombre de Bugs
final int Y_BUGS=0;  // position initiale Y des bugs
final int HAUTEUR = 4; // en nb de cases
final int LARGEUR = 4; // en nb de cases
final int TAILLE_CASE = 80
boolean readMaze = true;

  1. Compiler alors le programme tel quel, pour vérifier qu’il n’y a pas d’erreur.

Grâce au fait que le labyrinthe est de petite taille, on se propose d’écrire en premier lieu un algorithme particulièrement idiot. Cet algorithme repose sur le hasard et est très inefficace et reproduit assez fidèlement le comportement d’un étudiant moyen devant un problème de programmation.

Tant que notre Bug n’a pas trouvé le biscuit, il doit se comporter de la façon suivante :

  1. Choisir un entier entre 0 et 2 au hasard à l’aide de la méthode Math.random()

  2. Prendre l’une des décisions suivantes selon l’entier choisi :

    • Tirage =0 : avancer.

    • Tirage =1 : tourner à droite.

    • Tirage =2 : tourner à gauche.

À faire

  1. La méthode Math.random() renvoie une valeur réelle (double) comprise entre 0.0 (inclus) et 1.0 (exclu). Écrire l’expression permettant de générer une valeur entière dans l’intervalle \([0;2]\).

  2. Écrire un algorithme simple traduisant le comportement du Bug décrit ci-dessus.

  3. Traduire cet algorithme en programme dans la méthode enRoute().

  4. Compiler() puis exécuter votre programme.

  5. Analyser le comportement du Bug. A-t-il trouvé le biscuit ? S’est-il cogné au murs ?

  6. Afin de réduire le temps moyen nécessaire au Bug pour trouver les biscuit, positionner la fréquence des mouvements à 1000 mvts/seconde à l’aide de la méthode setVitesse(1000).

  7. Compiler puis exécuter de nouveau votre programme.

Correction

Bug.java

Défi n°2 : Le bug démotivé

Il peut arriver parfois, qu’à force de tourner en rond sans succès, le Bug se décourage et abandonne sa quête.

À faire

  1. Modifier le programme de sorte à ce que le Bug signale son abandon si il n’a pas trouvé le biscuit après 3000 mouvements. L’arrêt du programme peut s’obtenir en utilisant l’instruction exit(1) et en ajoutant, au tout début du fichier Bug.java, la ligne

    import static java.lang.System.exit;

Correction

Bug.java

Défi n°3 : Le bug douillet

Les précédentes variantes généraient des traumatismes à répétition chez le Bug qui ne cessait de se cogner aux murs. Notre Bug est maintenant prudent et sonde l’espace devant lui avant d’avancer. La méthode isFaceMur() lui permet cela.

À faire

  1. Modifier le programme de sorte que le Bug ne se cogne plus aux murs. Plus aucun message de douleur ne doit donc apparaître dans la console.

Pour les plus rapides

  1. Reprendre la variante du Bug démotivé et modifer le programme pour qu’il comptabilise le nombre de fois où le Bug heurte un mur au cours de sa quête. Attention, la solution à cette question n’est pas aussi immédiate que les précédentes !

  2. Modifier ensuite le programme pour que le Bug abandonne après s’être heurté 1000 fois aux murs.

Correction

Bug.java

Défi n°4 : Le Bug qui se croit malin

Cette fois-ci le labyrinthe est beaucoup plus compliqué. Le hasard ne sera pas suffisant, il va falloir être intelligent !

Heureusement, ce labyrinthe est plus simple qu’il n’y paraît : tous les murs sont connectés les uns aux autres. Pour sortir de ce genre de labyrinthe, il suffit de longer un mur (celui à sa droite, ou celui à sa gauche: c’est sans importance). Tout en gardant sa patte posée sur ce mur, votre Bug doit avancer jusqu’à trouver la sortie du labyrinthe et ce biscuit qu’il apprécie tant.

../../_images/laby.png

État initial

  • Un Bug dans un labyrinthe de 12x12 cases.

  • Un biscuit qui représente la sortie à atteindre.

Résultat attendu

  • Le Bug est parvenu jusqu’à la case du biscuit en longeant les murs à sa gauche.
../../_images/init.png ../../_images/result.png

À faire

  1. Récupérer la définition des murs et du biscuit mazeData2.txt, l’enregistrer dans le dossier des sources.

  2. Ajuster les paramètres du bug world comme suit

    final int[][] casesColorees = {

};
final int N_BUGS=1;  // nombre de Bugs
final int Y_BUGS=6;  // position initiale Y des bugs
final int HAUTEUR = 12; // en nb de cases
final int LARGEUR = 12; // en nb de cases
final int TAILLE_CASE = 40
boolean readMaze = true;

  1. Compiler le programme tel qu’il est fourni, pour vérifier qu’il n’y a pas d’erreur.

  2. Écrire un algorithme qui permette au Bug d’avancer tout en gardant la patte sur le mur du côté gauche. Vous devez vous assurer qu’il garde toujours la patte sur le mur et également qu’il ne risque pas de percuter un mur.

  3. Écrire le programme implémentant l’algorithme que vous avez rédigé. N’oubliez pas de récompenser le Bug avec le biscuit !

  4. Ajouter la fonctionnalité permettant de colorier les cases parcourue par le Bug.

  5. Modifier la position initiale du Bug pour le placer sur la case (2,1). Utiliser pour cela la méthode setX() en début de méthode enRoute().

  6. Analyser le comportement du Bug dans ces nouvelles circonstances et proposer une modification algorithmique permettant de pallier ce défaut. L”implémenter et vérifier le résultat.

Correction

Bug.java

Défi n°5 : Le Bug des îles

À faire

  1. Modifier cette fois la position initiale du Bug pour le placer sur la case (6,1) et analyser de nouveau le comportement observé. S’agit-il du même défaut ?

  2. Récupérer le fichier mazeData3.txt décrivant un labyrinthe illustrant plus clairement ce défaut. La position initiale du Bug est la case (4,0).

Pour gérer ces situations de mur(s) non connecté(s) (appelés îles) on propose de modifier légèrement l’algorithme de notre Bug :

  • L’idée est de chercher à atteindre un mur extérieur, ou au moins un mur connecté aux murs extérieurs.

  • Lorsque ce but est atteint, on peut employer la technique précédente du suivi main gauche (ou droite).

Pour cela, on va se donner une direction privilégiée pour chercher à atteindre un mur extérieur ; prenons par exemple le nord. Ensuite, on va distinguer deux modes de fonctionnement :

  • Tant qu’il le peut, le Bug reste en mode avance plein nord (mode 0).

  • Lorsqu’il ne peut plus (mur en face), il passe en mode suivi main gauche (mode 1), jusqu’à ce qu’il puisse repasser en mode avance plein nord.

Esquisse d’algorithme

 1mode := 0
 2direction := nord
 3TANT QUE biscuit pas atteint
 4FAIRE
 5  SELON mode
 6    cas 0:
 7      avance plein nord tant que possible
 8      mode := 1
 9    cas 1:
10      suivi main gauche tant que avance plein nord impossible
11      mode := 0
12  FIN_SELON
13FIN_TQ

À faire

  1. Implémenter un programme fonctionnel traduisant l’algorithme ci-dessus.

État initial

  • Un Bug dans un labyrinthe à îles de 12x12 cases.

  • Un biscuit qui représente la sortie à atteindre.

Résultat attendu

  • Le Bug est parvenu jusqu’à la case du biscuit en alternant les deux modes d’avance.
../../_images/init31.png ../../_images/result31.png

Correction

Bug.java

Défi n°6 : Pledge sauve le Bug

Nommé d’après John Pledge qui le conçut, selon la légende, à l’âge de douze ans, cet algorithme permet de se sortir de situations de type escargot. Une explication illustrée et détaillée est accessible ici

À faire

  1. Lire l’explication de l’algorithme de Pledge.

  2. Récupérer le fichier mazeData4.txt décrivant un labyrinthe à escargot.

  3. Proposer une implémentation de l’algorithme de Pledge et sauvez le Bug.

État initial

  • Un Bug dans un labyrinthe à île et escargot de 12x12 cases.

  • Un biscuit qui représente la sortie à atteindre.

Résultat attendu

  • Le Bug est parvenu jusqu’à la case du biscuit en appliquant l’algorithme de Pledge.
../../_images/init4.png ../../_images/result4.png

Correction

Bug.java ainsi qu’un mazeData plus dur pour tester vos programmes.