algorithme de Pledge

**misterhide** · 14/01/2016, 23h15

Bonjour,

Je me présente, je suis en ecole d'ingénieur,plutôt orienté chimie...mais malgré tout on échappe pas à l'informatique XD

J'ai donc un projet à faire en C, en seulement 3 semaines. Il s'agit de créer aléatoirement un labyrinthe, et de le resoudre de maniere automatique. J'ai donc réussi a créer un algorithme qui crée le labyrinthe aléatoirement. Les murs sont représentés par des 1 et les cases vides par des 0. Les labyrinthes que je génèrent ont obligatoirement des solutions (j'ai codé plusieurs conditions pour que le labyrinthe soit réalisable). Je dois maintenant trouver un algorithme qui permet de sortir à coup sûr du labyrinthe. Le prof m'a conseillé l'algorithme de Pledge. Pour ceux qui ne connaissent pas, cet algorithme est expliqué ici : https://interstices.info/jcms/c_4606...thme-de-pledge

Et là, j'avoue que je bloque depuis plus d'une semaine. Je n'arrive pas du tout a voir comment coder cet algorithme....Donc si une âme charitable (qui trouve cet algorithme facile), voudrait bien m'aider, ce serait avec plaisir !!!!!

**BufferBob** · 15/01/2016, 00h08

salut,

en fait dans le lien que tu donnes, l'algorithme est bien résumé en deux étapes :

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

donc si le compteur est à 0, tu vas jusqu'au prochain mur qui te fait face (selon la direction dans laquelle tu avances évidemment)
sinon tu longes le mur jusqu'au prochain "coin" (il faut donc pouvoir identifier un coin dans ton tableau qui symbolise le labyrinthe, en fonction de la direction que tu prends), quand tu tournes à gauche tu rajoutes 1 au compteur, à droite tu enlèves 1 c'est assez simple
l'algorithme s'arrête quand tu es devant la sortie et que le coup d'après tu es en dehors du labyrinthe

après à implémenter je sais pas si c'est le plus facile ou le plus pertinent, l'algorithme A* est un grand classique du genre

Edit: j'ai pas précisé mais c'est implicite; concrètement on parle de créer une fonction récursive pour l'implémentation

**misterhide** · 15/01/2016, 11h00

Salut,

Merci pour ta réponse

Au fait j'ai bien compris comment l'algorithme fonctionne, je bloque juste sur le coté technique du codage. Le truc c'est que je ne voit pas comment "dire" à mon robot de tourner à gauche (ou a droite). Parce que en fonction d'où je me situe dans le labyrinthe (qui est un tableau), l'instruction tourner à gauche peut vouloir dire, "descendre d'une case", "monter d'une case" ou si le robot descend tourner à gauche reviendra a aller a droite par exemple... C'est le codage de l'instruction tourner à gauche qui me bloque...

**Matt_Houston** · 15/01/2016, 11h14

Envoyé par BufferBob

après à implémenter je sais pas si c'est le plus facile ou le plus pertinent, l'algorithme A* est un grand classique du genre

Le gros avantage qu'aurait A* ici est que le chemin trouvé serait - avec un heuristique adéquat - optimal. Mais vu l'énoncé et le peu d'expérience que semble avoir misterhide ce serait hors-sujet : l'implémentation d'un A* ou d'un Djikstra est autrement plus complexe. Le C ne propose même pas d'implémentation toute faite de listes dynamiques (ce que l'on pourrait contourner avec IDA* mais je digresse..).

Envoyé par misterhide

Le prof m'a conseillé l'algorithme de Pledge. Pour ceux qui ne connaissent pas, cet algorithme est expliqué ici : https://interstices.info/jcms/c_4606...thme-de-pledge

Et là, j'avoue que je bloque depuis plus d'une semaine. Je n'arrive pas du tout a voir comment coder cet algorithme....Donc si une âme charitable (qui trouve cet algorithme facile), voudrait bien m'aider, ce serait avec plaisir !!!!!

Je ne connaissais pas cet algorithme, il est adapté et en effet assez simple. Je le résume :

soit dir égal à 0 la somme des changements de direction
tant que l'on n'est pas sorti du labyrinthe faire :
1. avancer en ligne droite jusqu'à :
  - avoir un mur en face de soi :
    - tourner à droite et incrémenter dir
    - aller en 1
  - ne plus avoir de mur à main gauche :
    - si dir est différent de 0 alors
      - tourner à gauche et décrémenter dir
    - aller en 1

EDIT:

Envoyé par misterhide

Au fait j'ai bien compris comment l'algorithme fonctionne, je bloque juste sur le coté technique du codage. Le truc c'est que je ne voit pas comment "dire" à mon robot de tourner à gauche (ou a droite). Parce que en fonction d'où je me situe dans le labyrinthe (qui est un tableau), l'instruction tourner à gauche peut vouloir dire, "descendre d'une case", "monter d'une case" ou si le robot descend tourner à gauche reviendra a aller a droite par exemple... C'est le codage de l'instruction tourner à gauche qui me bloque...

Ok donc tu vois à peu près comment transcrire cet algo avec les constructions dont tu disposes en C (boucles, branchements...) ?

Tourner à droite ou à gauche revient à altérer le sens de parcours de ta matrice de cases (labyrinthe). Ce sens de parcours est donc dynamique : c'est l'orientation de ton robot. Ce qui est dynamique doit être stocké dans une variable.
Attention : mettre à jour le sens de parcours n'implique pas forcément d'avancer d'une case en même temps. D'ailleurs faire cela risque de te causer du souci lors du parcours d'un couloir en cul-de-sac de largeur 1 (au fond, il faut effectuer un demi-tour soit deux rotations de 90° en un cycle).

**stendhal666** · 15/01/2016, 14h08

pour le problème des changements de direction, pas la peine de te prendre trop la tête: tu recenses les directions dans une enum

Code :

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

1
2
 
enum DIRECTION { GAUCHE = 0, HAUT, DROIT, BAS };

Ton robot contient la direction où il va, par exemple:

Code :

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

typedef struct Robot { int x, y; Direction d; } Robot;

et ensuite tu fais des fonctions:

Code :

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

1
2
3
4
5
6
7
DIRECTION a_gauche(DIRECTION d) {
  return d == GAUCHE ? BAS : --d; // s'il va vers le haut, à gauche, vers la droite, en haut, vers le bas, à droite et vers la gauche, en bas.
}
 
DIRECTION a_droite(DIRECTION d) {
  return d == BAS ? GAUCHE : ++d; // gauche -> haut, haut -> droite, droite -> bas, bas -> gauche
}

**misterhide** · 16/01/2016, 10h29

Bonjour tout le monde

merci pour vos réponses.

Je vais être honnête, j'ai découvert le C en école d'ingé il y a seulement 2/3 mois

du coup je suis désolé stendhal666 mais j'ai pas bien compris ton post ... Au fait je connaissais les structures mais pas les énumérations. Je me suis renseigné, donc si j'ai bien compris, dans une énumération les seules valeurs possibles sont celles que l'on indique (ici gauche haut droit bas) ?

J'ai codé le "squelette" de l'algorithme en fonction du post de Matt_Houtson (merci

). Est ce que vous pouvez me dire si c'est correct ?
Les instructions écrites en français sont celles que je n'arrivent pas à écrire en C...

**BufferBob** · 16/01/2016, 14h59

alors ok, tu débutes en C et il s'agit d'un pseudo-code mais même en tenant compte de ça t'es pas sorti du sable là

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
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 void algorithme de Pledge () {
 
 
     int compteur=0;
     int m=15, n =15;  // je crée un tableai qui ici symbolisera le labyrinthe. En réalité, le lbyrinthe est déjà crée
     int tab2D[m][n];  // par un autre programme de manière aléatoire et correcte (il contient forcément une solution)
 
     typedef struct Robot { int x, y; Direction d; } Robot;
        Robot.x=3;  // on place le robot à la case de coordonnées 3,3. Le programme qui génère le labyrinthe, génère aussi aléatoirement
        Robot.y=3;  // une case de départ symbolisée D... mais commme on ne connait pas d'avance la position de D, on va dire qu'ici on commance à la case 3.3
 
 
     While (on est pas sortie du labyrinthe){
 
        Robot.y++; //le robot va tout droit
 
        if (tab2D[y+1][x]=1){  // si on rencontre un mur, le robot tourne à gauche et on incrémente le compteur
 
            tourne à gauche;
            compteur++;
 
        }
 
        if (tab2D[y][x+1]=!1){
 
            if (compteur=!0){
 
                tourne à gauche ou à droite;  // si on ne longe plus le mur et que le compteur est différent de 0 on tourne à gauche ou a droite pour rester en contact avec le mur
                compteur ++; // ou compteur --
            }
 
        }
 
     }
 
return 0;
}

déjà parceque c'est un peu court si tu ne fais que du pseudo-code, t'as pas cherché très loin, d'autre part parceque la logique du programme n'est pas bonne du tout, par quoi tu symbolises la partie "avancer en ligne droite jusqu'à avoir un mur en face de soi ou ne plus avoir de mur à (la) main gauche" ?

la première chose à faire quand on est dans la boucle "tant qu'on a pas trouvé la sortie" c'est de checker le compteur, lequel pourrait tout à fait être lié à la structure Robot par ailleurs
c'est le compteur qui te dit si tu vas tout droit jusqu'au prochain mur qui te fait face ou si tu longes les murs par la gauche

tu devrais essayer de comprendre l'algorithme, ce n'est pas si compliqué que c'en a l'air, et ce sera de toutes façons plus pertinent que de te fier aveuglément au pseudo-algorithme d'une personne qui elle, même si son explication n'est pas parfaite, a compris comment ça fonctionne (donc son algo a du sens pour elle, mais pas forcément le même sens pour toi qui n'a pas compris le principe)

à la question

Envoyé par Matt_Houston

Ok donc tu vois à peu près comment transcrire cet algo avec les constructions dont tu disposes en C (boucles, branchements...) ?

la réponse est clairement non (no offense comme on dit)

algorithme de Pledge

C

Discussions similaires

Partager

Partager