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

[aubanel]

Mmmh, je ne découperai pas la chose comme ça. Sortir les boucles en dehors de l'algo et faire une fonction de réaction simple (pas de boucle) me semble plus approprié et propre, et ça te permettra par exemple de dessiner la position de ton robot à chaque pas. Ensuite, définis ton interface avant de penser à l'algo lui même. Je verrais quelque chose du style (en ocaml, je ne connais pas caml light):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
type inst = Tout_droit | Longer
type khepera_etat = {
compteur : int;
instruction : inst
}
 
type ordre = Avancer | Droite | Gauche
 
let etat_initial = { compteur = 0; instruction = Tout_droit}
 
let cyclique devant droite etat =
  match etat.instruction with
    | Tout_droit | Longer when devant (* mur en face, on tourne à gauche *) 
        -> {compteur = etat.compteur +1; instruction = Longer},Gauche
    | Longer when etat.compteur = 0 -> { compteur = 0; instruction = Tout_droit}, Avancer
    | Longer when not droite (* plus de mur à longer et rien devant, tourner à droite pour suivre le mur *)
        -> {compteur = etat.compteur -1; instruction = Longer}, Droite
    | Tout_droit 
    | Longer -> etat,Avancer

Tu as donc une fonction cyclique, qui à partir des entrées : mur devant, mur à droite; et l'état, te calcule un nouvel état (pour le cycle suivant) et un ordre.
À toi de mettre cette fonction cyclique dans une boucle, d'y intégrer l’environnement (coordonnées (x,y) du robot, matrice des murs) et finalement la fonction cyclique de dessin (qui dessine l'environnement à chaque cycle). C'est ce qu'on appelle l'approche synchrone, très utilisée dans l'embarqué.
Attention à la valeur de l'état pour le premier cycle, il faudra utiliser etat_initial, alors que pour les autres cycles il faut utiliser l'état retourné par la fonction cyclique.

[boutoudebou]

Très bien, maintenant j'ai écrit le pseudo-code et un petit programme d'interaction avec Caml pour sortir du labyrinthe en décrivant le labyrinthe "à la main", mais il me reste l'algorithme en lui-même à implémenter en Caml...

Le problème c'est que je ne maîtrise l'emploi des matrices...

[Cacophrene]

Bonsoir,

Le problème c'est que je ne maîtrise l'emploi des matrices...

Avec Caml ce ne sera pas très difficile. Si tu as un tableau, tu as une matrice... dès lors que les éléments de ce tableau sont eux-mêmes des tableaux. Tu peux donc utiliser la syntaxe matrice.(x).(y).

Cordialement,
Cacophrène

[boutoudebou]

Qu'appelles-tu un tableau ?

Un vecteur [|x1;x2;...;xn|] ?

[aubanel]

Une matrice, ce n'est qu'une façon d'associer une valeur (dans notre cas la présence d'un mur) à une paire de coordonnées : pour un X,Y donné, on doit pouvoir retrouver s'il y a un mur ou pas. Maintenant à toi de choisir comme tu veux implémenter ça : une liste de booléens, un tableau de tableau, un Map, voire un Set.
Le choix de ta structure dépend des performances que tu souhaites obtenir, de la façon dont tu souhaites y accéder, et de son remplissage typique. Par exemple, une grande matrice typiquement creuse utilisera des structures différentes qu'une petite matrice habituellement pleine.

Personnellement, je pencherais pour un Set dans lequel tu insères les coordonnées de tes murs. Tu peux par la suite tester la présence d'un mur par Murs.mem (x,y) s.
Si tu ne sais pas te servir d'un Set, je te donne un petit exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
module Murs = Set.Make ( 
  struct 
    type t = int * int 
    let compare = Pervasives.compare 
  end)

créer un ensemble vide et y ajouter un mur aux coordonnées 3,5

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
let murs = Murs.empty in
let murs = Murs.add (3,5) mur in

La fonction Murs.iter te permet de passer sur tous les murs présents dans ton ensemble, par exemple pour dessiner un rectangle pour chaque...

[Cacophrene]

Bonjour,

Utiliser les set c'est judicieux et approprié dans le cas présent. Ça introduit aussi une notion nouvelle, sans compter qu'il faut passer par les foncteurs, ça fait assez ésotérique... je ne recommanderai pas cela aux débutants, au moins au début.

Les tableaux (pour répondre à la question plus haut : oui, ce sont bien les vecteurs de caml light) ont l'immense mérite de permettre d'écrire une première version simplement. Ensuite, on pourra l'inviter à se questionner sur le remplissage du tableau, l'utilisation inutile de mémoire en l'absence de mur, etc. et l'amener doucement à découvrir d'autres types de données. Il y a déjà eu pas mal de nouveautés depuis l'ouverture de ce fil

Cordialement,
Cacophrène

[boutoudebou]

Donc dans ce tableau je créé un labyrinthe de dimension 12x12 par exemple, c'est-à-dire 144 vecteurs... ?

Et dans chaque vecteur, je met un couple de coordonnées, et quoi d'autre ?

l'information de direction du robot peut-elle être sous forme de reférence sur un entier 1,2,3,4.. ?

Merci beaucoup de votre aide

[boutoudebou]

j'ai essayé de créer un labyrinthe 12x12 sous forme de vecteurs de vecteurs avec ce code :

let labyrinthe =
let v = make_vect 144 [|0;0|] in
for k = 0 to 143 do
let x = (k/12) + 1 in
let y = (k mod 12) + 1 in
v.(k) <- [|x;y|]
done;
v
;;

Bref, ça avance un peu, mais pas beaucoup : il me manque des murs, et puis.. ben l'algo. de pledge

[aubanel]

Cher boutoudebou,
je crois qu'il y a quelque chose que tu n'as pas compris
Ta matrice représente ton terrain, elle doit donc pouvoir associer à une coordonnée x,y la présence ou l'absence de mur.
Dans ton exemple (d'ailleurs, utilise s'il te plait la balise CODE et indente ta prose, ça fera du bien à nos yeux et à nos cerveaux), tu associes à un entier (l'index de ton tableau) une paire d'entiers, qui est d'ailleurs lié à la valeur de l'index. Bref, ça sert à rien. D'ailleurs tu le dis presque toi même.
Si on faisait plutôt une matrice (soit un tableau de tableau, qui prend deux index, le premier représentant les X, le deuxième les Y) de booléens, qui te donnent l'info : y'a un mur ou y'a rien ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
(*Création d'un terrain vide : matrice 12x12, ne contenant que false : y'a pas d'mur ! *)
let terrain = Array.make_matrix 12 12 false in
(* On ajoute un mur : *)
terrain.(5).(7) <- true ;
terrain.(5).(8) <- true ;
terrain.(5).(9) <- true ;
 (*fonction de test de présence de mur * )
let test_mur terr x y =
  terr.(x).(y)
(* A ton avis, que donneront 
  test_mur terrain 0 3 
  test_mur terrain 5 8
*)

Tu peux écrire facilement la fonction test_dehors x y qui te renvoie vrai lorsque les coordonnées x y que tu donnes sont au bord du terrain.

Sinon l'algo de pledge je crois qu'on te l'a déjà donné, non ?

Concernant la direction du robot, tu l'as déjà dans l'état. Ce qu'il te faut stocker se sont les coordonnées actuelles du robot pour pouvoir le représenter graphiquement et tester les murs alentour.

[boutoudebou]

En effet, j'ai maintenant créé un tableau de booléens et je comprends que c'est ce qu'il faut faire, mais je ne sais toujours pas comment afficher le terrain par exemple...

[TropMDR]

En même temps, on n'est pas là pour faire ton TIPE.
Si tu veux faire un TIPE avec une composante programmation, la première étape, c'est d'apprendre un minimum à programmer... Et ce n'est pas en nous demandant de faire ton boulot que tu vas y arriver. Donc je réitère ma suggestion

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/

[boutoudebou]

Je pense être de bonne foi en disant que j'y met du mien et que j'ai envie d'avancer... D'ailleurs, pour l'instant, ce que j'ai fais ne relève QUE de moi.

Maintenant, si on ne peux plus chercher de l'aide sur un forum, très bien...

[Cacophrene]

Bonjour,

Maintenant, si on ne peux plus chercher de l'aide sur un forum, très bien...

N'exagérons pas, ce n'est pas le sens du message de TropMDR. On veut juste te faire comprendre qu'un algorithme, quel qu'il soit, présente en lui-même des difficultés de compréhension et de mise en œuvre. Aussi, pour t'éviter d'y ajouter des problèmes de programmation (par exemple : comment travailler sur des matrices en caml), il serait judicieux que tu t'entraînes d'abord un peu sur les notions dont tu auras besoin. Il ne s'agit pas de maîtriser à fond ces notions, mais seulement d'acquérir les bases pour être plus à l'aise de ce côté-là.

Comment procéder ? Pour ma part, je ferai la liste des outils dont je pense avoir besoin (ce n'est pas grave s'il en manque, on pense rarement à tout), et je chercherai d'abord à voir si je sais les utiliser convenablement. Tu obtiendras aussi de l'aide là-dessus sur ce forum, si tu le souhaites.

Cordialement,
Cacophrène

[aubanel]

Disons que l'impression de ce côté de l'écran est que tu ne te foules pas des masses, ou que pour le moins les choses ne sont pas très claires quant à ta démarche. Cela étant certainement dû au fait que tu es débutant en programmation.

Essayer des petites choses simples avant de se lancer dans ton projet comme suggéré par TropMDR est certainement une bonne idée.

Enfin, pour ta partie graphique, regarde du côté du module ... Graphics.