Projet 2:

Marquer toutes les cases d'un labyrinthe

Dans ce projet, le robot devra marquer les 81 cases d'un labyrinthe 9x9. Les labyrinthes à explorer sont formés uniquement de couloirs, comme ceux générés sur le site MAFALDA. La position et l'orientation initiales du robot sont aléatoires.
Pour fixer les idées, voici les deux labyrinthes que vous devrez explorer à l'aide d'un seul et même programme:

(cliquez avec le bouton de droite sur les noms des fichiers RobotProg et enregistrez ces fichiers sur votre disque dur)

Vous devrez rendre un rapport, rédigé à l'aide d'un traitement de texte, le 1er décembre 2005.

Structure du rapport (suggestion)

  1. Enoncé (voir ci-dessus).

  2. Analyse du problème
    1. Stratégie(s) générale(s) expliquées en français. Des schémas sont aussi bienvenus.
    2. Décomposition du problème. Descriptions des sous-programmes.
    3. Votre programme marchera-t-il avec tous les types de labyrinthes ? Si non, donnez un exemple où cela ne marche pas.

  3. Sous-programmes et programme principal (programme à donner sur disquette ou par email).
    Je dois pouvoir comprendre le programme aisément, donc il faut choisir de bons noms pour les sous-programmes. Je conseille de faire suffisamment de sous-programmes pour ne pas avoir de problèmes de place sur la feuille de RobotProg.

  4. A choisir entre les deux options suivantes:
    1. Comment améliorer votre programme, avec les contraintes de RobotProg, pour explorer des labyrinthes où les murs ne sont pas tous interconnectés?
    2. Expliquer une autre méthode d'exploration trouvée sur le web ou dans des livres ou des revues. Ne pas oublier de mentionner vos sources.

Références


Didier Müller, 11.11.05