Discussion :

[boutoudebou]

Bonjour, je suis en section MPSI option informatique, et pour la présentation d'un sujet type TIPE info

sur l'algorithme de pledge, je suis censé programmer en langage Caml cet algorithme. :hum:

Pour ceux qui ne le connaissent pas déja, voilà un lien introductif :

http://interstices.info/jcms/c_46065...thme-de-pledge

Mon problème est le suivant : je suis un débutant de la programmation, et je ne sais même pas par quoi

commencer pour écrire un programme (avec interface graphique, si possible) illustrant le fonctionnement

de l'algorithme. Pourriez-vous m'aider ? Merci d'avance.

[aubanel]

Bonjour,
À la lumière du site que tu lies (très clair et bien fait au demeurant), voici ce que je te conseille.
D'abord, oublie l'interface graphique dans un premier temps, il faut que ton algorithme fonctionne correctement avant de penser à comment le montrer.
Ensuite, il y a clairement deux parties. L'une qui correspond à l'implémentation de l'algorithme tel qu'embarqué dans le khepera, et qui est somme toutes hyper trivial :

->Aller tout droit jusqu’au mur, passer à l'instruction 2 ;
->Longer le mur par la droite (ou par la gauche, mais toujours dans le même sens) jusqu’à ce que le décompte des changements de direction atteigne zéro, passer à l'instruction 1 ;

Pour cela, il te va falloir définir l'interface de ton robot : quelles informations sont disponibles en entrée ? (par exemple, mur en face, mur à droite, mur à gauche) quelles actions peut-il entreprendre ? (par exemple tourner 90° à gauche, à droite, avancer).
Une fois cela fait, tu implémentes l'algorithme, qui est la production des sorties en fonction des entrées. Pour cela, tu auras certainement besoin d'une ou plusieurs mémoires, qui sont persistantes entre chaque appel à la fonction de résolution de ton algorithme (typiquement, le décompte des changements de direction est une mémoire).

Tu as donc un robot qui sait se comporter comme il faut, mais tu seras un peu embêté pour montrer son fonctionnement sur une machine. Il te va donc falloir modéliser son environnement : où sont les murs ? où est la sortie ? Comment repères tu le position du robot et des murs afin de pouvoir les dessiner dans une IHM sympa ? Cela me semble la seule vraie difficulté. Pour simplifier le problème, tu peux commencer avec un concept de grille, et représenter le terrain par un tableau où chaque cellule est soit un mur, soit vide.

Voilà, je te souhaite bon courage, je ne doute pas que tu auras d'autres questions, n'hésite pas !

[boutoudebou]

Merci beaucoup pour cette première réponse...

Je pensais, pour la mémoire et l'environnement du programme, utiliser une matrice, le problème c'est que je ne maîtrise pas encore la syntaxe Caml et que le cours d'info s'est résumé aux notions de listes et de vecteurs pour le moment; or il me semble que l'environnement de travail est la première procédure à implémenter...

Ensuite, je comprends assez bien la nécessité, une fois l'environnement posé, d'instaurer une représentation numérique des éléments du labyrinthe : murs, couloirs, entrée, sortie(s)...

Enfin, je suppose que des modifications de l'environnement au cours du temps pourrais bien correspondre à des modifications des valeurs de la matrice si on en utilise une...

[TropMDR]

Je pense que la première étape, avant toutes autres choses, est d'apprendre un minimum à programmer en caml. J'imagine que tu fais du caml light. Dans ce cas les TD de Vincent Simonet sont excellent

http://www.normalesup.org/~simonet/teaching/caml-prepa/

Bon courage

[boutoudebou]

tant que la case devant soit n'est pas un mur :
on avance d'une case
fin tant que

Si la case à droite est un mur :
on tourne à gauche; on décrémente le compteur
Sinon :
on tourne à droite; on incrémente le compteur
Peut on me dire déja si ce pseudo-code tient la route ?

tant que le robot est dans l'environnement (n'est pas sorti) :
Si il y a devant soi un mur :
on tourne à droite; on incrémente le compteur
Sinon :
on avance d'une case;
Fin Si

Si il y n'y a pas à gauche de soi un mur :
on tourne à gauche; on décrémente le compteur;


Si le compteur = 0 :
tant que la case devant soit n'est pas un mur :
on avance d'une case
fin tant que

fin tant que

[boutoudebou]

Pardon, je reprends :

Pouvez-vous me dire si ce pseudo-code tient la route ?

tant que la case devant soit n'est pas un mur :
on avance d'une case
fin tant que

Si la case à droite est un mur :
on tourne à gauche; on décrémente le compteur
Sinon :
on tourne à droite; on incrémente le compteur
Fin Si

tant que le robot est dans l'environnement (n'est pas sorti) :
Si il y a devant soi un mur :
on tourne à droite; on incrémente le compteur
Sinon :
on avance d'une case;
Fin Si

Si il y n'y a pas à gauche de soi un mur :
on tourne à gauche; on décrémente le compteur;
Fin si


Si le compteur = 0 :
tant que la case devant soit n'est pas un mur :
on avance d'une case
fin tant que
Fin si

fin tant que