Discussion :

[fabetvince]

Bonjour,
J'essaie de trouver le chemin le plus court dans un labyrinthe. Mon labyrinthe ressemble à ça :
111111111111111
101010101000001
101010101010111
100010101000021
111011101010111
100003100010001
101011101010101
101010001000101
101011101010101
101000000010001
101110101010111
100010001010001
101010101010111
100000101000001
111111111111111

Les 1 sont des murs, et les 0 des passages. Et je veux aller du point 2 au point 3 (par le chemin le plus court). (les deux est sur la droite, et le trois vers le milieu.
La je regarde pour le faire avec l'algorithme de Dijkstra, mais j'ai quelques petits problèmes pour commencer. Car mon tableau ne ressemble pas beacoup aux exemples que j'ai pu voir qui contennaient des graphes. Si quelqun pouvait me dire comment commencer.
Merci.

PS : C'est une pour une programmation en C.

[Graffito]

Bonjour,

Voir la routine Delphi (pas en C ) dans un post précédent, ca devrait répondre à ton problème.

http://www.developpez.net/forums/sho...ghlight=chemin

la fonction Map_isPathOK(i,j) vaudra true quand la case (i,j) est à 0.

[fabetvince]

Je ne comprends pas tout dans ton algo.

Sinon, la j'ai trouvé une explication de "A*" sur le net mais je n'arrive pas à trouver l'algo. Car je ne vois pas comment créer la liste ouverte et la liste fermée. Quels doit être leur type ?

Merci

[Graffito]

Bonjour,

Le principe est assez simple :
- on gère une liste de cases de plus en plus éloignées du départ,
- on commence avec une seule case : la case de départ,
- on traite succesivement chaque case de liste,
- on regarde pour toutes les cases voisines (non encore traitées) si il y a obstacle ou si c'est la fin,
- lorsque la case n'a pas encore été traitée et n'est pas un obstacle, on l'empile dans la liste.
- lorsqu'on tombe sur la fin, il reste plus qu'à remonter le chemin jusqu'au début.

[fabetvince]

Que signifie :

var PointX,PointY,PointP : array of integer ;

int*PointX ?

(**)procedure AddPoint(X,Y:integer) ;

C'est quoi "procedure" ?

inc(iend) ;

"inc " C'est pour incrementer ?

if MAP_IsPathOk(StartPathX,StartPathY) and MAP_IsPathOk(EndPathX,EndPathY)C'est quoi le MAP_IsPathOk ?

SetLength(PointX,grid.nbx*grid.nby) ;

SetLength ??


En fait je comprends pas grand chose dans cette algo.

[Charlemagne]

Quand on connait le plan du labyrinthe, on utilise en général cette méthode:
http://math.berkeley.edu/~sethian/Mo...erobotics.html
L'auteur a juste corsé le problème en se promenant avec une échelle dans le labyrinth.
Ca consiste grosso modo à simuler la propagation d'une onde ou d'un liquide. Tu verses du liquide à ton point de départ et tu chronomètre sa progression en incrémentant un compteur.
J'ai simulé le commencement de la diffusion sur ton exemple.

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
 
***************
*0*0*0*0*76567*
*0*0*0*0*6*4***
*000*0*0*54321*
***0***0*6*4***
*0000!*007*567*
*0*0***0*0*6*0*
*0*0*000*007*0*
*0*0***0*0*0*0*
*0*0000000*000*
*0***0*0*0*0***
*000*000*0*000*
*0*0*0*0*0*0***
*00000*0*00000*
***************

[fabetvince]

J'avais déjà vu ça. A faire à la main, je y arrive, mais à le mettre en C, c'est déjà plus dur.

[Charlemagne]

Ca doit pas être trop sorcier de manière récursive, sinon il faut surement prévoir une pile pour conserver en mémoire les endroits où le liquide rencontre un embranchement.
->Autour d'une position, appeler l'algorithme récursivement sur chaque direction possible

Le problème peut-être d'une technique récursive, c'est qu'elle explorerait complêtement une direction, et qu'il faudrait revenir en arrière pour explorer les autres voies.
A priori je collerais plus à la réalité en simulant la réelle progression du liquide, en créant un vecteur retenant toutes les coordonnées atteintes par le liquide à l'instant t.
Sur ton exemple:
t=1: (4,14)
t=2: (4,13)
t=3: (4,12)
t=4: (3,12) (4,11) (5,12)
Pour simuler l'instant t+1, il faut parcourir toutes les coordonnées de l'instant t et vérifier si le liquide peut aller aux points aux allentours. Il faut bien entendu inscrire dans ta matrice (labyrinth) l'instant ou le liquide arrive.

[fabetvince]

Le problème, c'est que (dans l'exemple) à partir du 3 il y a deux direction possibles. Après, pour les deux 5, ont à encore deux directions possibles. AInsi de suites.
Et à chaque fois, je dois regarder si le "liquide" n'est pas déjà passer à cette endroit et regarder lequel des deux chemin est le plus court pour ariver à ce point.
Et comment enregistrer les chemin, car au début il y a un chemin après deux, après 4, après 8... ??

[Charlemagne]

Le problème, c'est que (dans l'exemple) à partir du 3 il y a deux direction possibles. Après, pour les deux 5, ont à encore deux directions possibles. AInsi de suites.

C'est bien pour ça qu'un algo récursivif marcherait. Mais il peut être lent dans le cas de chemins multiples.

Et comment enregistrer les chemin, car au début il y a un chemin après deux, après 4, après 8... ??

Ta question me fait penser au "paradoxe" des ancêtres. J'ai 2 parents, qui eux-mêmes ont 2 parents, ... Et pourtant au bout de 1000 générations il ne faut pas croire que j'ai 2^1000 ancêtres. En fait il y en a des ancêtres communs qui se "chevauchent".
Il n'y aura pas non plus une infinité de croisements dans ton labyrinth.
Il faut prévoir un vecteur assez grand pour contenir touts les coordonnées des points.

Et à chaque fois, je dois regarder si le "liquide" n'est pas déjà passer à cette endroit et regarder lequel des deux chemin est le plus court pour ariver à ce point.

C'est pour ça qu'il faut marquer au fur et à mesure la progression du liquide dans la matrice avec le temps t.
Donc une règle pour verifier qu'une position autour est possible consiste à dire qu'elle n'est pas encore marquée et que ce n'est pas un mur.

En fait enregistrer les coordonnées dans un vecteur n'est pas strictement nécessaire pour l'algorithme. Ca permet de ne pas avoir à rechercher toutes les positions d'une valeur particulière t dans la matrice.

[fabetvince]

t=1: (4,14)
t=2: (4,13)
t=3: (4,12)
t=4: (3,12) (4,11) (5,12)

Par exemple, il me faut un tableau qui contient tout les "passages" (c'est à dire toutes les cases à 0).
Ensuite, Je fais avancer "mon onde", au fur est à mesure qu'elle avance, j'enleve le "passage" dans mon premier tableau qui contennait tout les 0.
Et à chaque fois que mon onde avance de 1, j'enregistre le parcourt dans un autre tableau.

Il me faut donc pour assurer le cou, pour tout les chemins, un tableau de "nombre de 0" au carré.
C'est ça ?

[Charlemagne]

Par exemple, il me faut un tableau qui contient tout les "passages" (c'est à dire toutes les cases à 0).

Non, je me servirais de la matrice (=le labyrinth) elle même, car elle permet un accès direct avec les coordonnées d'un point.
Avec par exemple la convension suivante
- Lab[N*i+j]=0 -> les murs
- Lab[N*i+j]=grand nombre -> pas encore d'eau
- Lab[N*i+j]=temps qu'a mis l'eau pour arriver

Il suffit de 2 tableaux (T1,T2)pour se rappeler les positions de l'étape t et de l'étape t+1. Tu les remplis à tour de rôle.
t=0 t=1 t=2 t=3
T1->T2->T1->T2

Tu arrêtes l'algorithme dès que le point d'arrivée est atteint. Et tu lis la matrice à l'envers (à partir du point d'arrivée vers le point de départ) pour connaître le plus court chemin.

Il me faut donc pour assurer le cou, pour tout les chemins, un tableau de "nombre de 0" au carré.
C'est ça ?

La taille de tes tableaux est un peu délicate à choisir, si tu programmes en C et que leur taille doit être fixée. On pourrait par exemple l'établir sur la largeur du labyrinth (et espérer que ça suffise...je pense que ça suffit mais faudrait vérifier dans le pire des cas)

[Charlemagne]

A la réflexion:
-La méthode proposée par Graffito semble y ressembler beaucoup...
-Je crois qu'il faut une taille de vecteur 2 fois plus grande que la largeur du labyrinth, le "pire" des cas étant un labyrinth completement sans mur.

[Graffito]

Que signifie :

var PointX,PointY,PointP : array of integer ;

Tableaux d'entiers pour les coordonnées X et Y et pointeur sur le point précédent dans le chemin

(**)procedure AddPoint(X,Y:integer) ;

C'est comme une fonction en C sans paramètre de retour

inc(iend) ;

"inc " C'est pour incrementer ? : OUI

if MAP_IsPathOk(StartPathX,StartPathY) and MAP_IsPathOk(EndPathX,EndPathY)C'est quoi le MAP_IsPathOk ?

MAP_IsPathOk fonction qui te dira si le point (X,Y) est un obstacle ou non.
Au début, on vérifie que ni le départ ni l'arrivée ne sont sur un obstacle.

SetLength(PointX,grid.nbx*grid.nby) ;

SetLength : allocation dynamique de la taille du tableau

[fabetvince]

J'ai regardé l'algo, et j'ai encore pas mal de question dessus.

PointP[iend]:=istart ;
PointX[iend]:=X ;
PointY[iend]:=Y ;

Que représente iend et istart, car ici ils n'ont pas de valeurs, ils ont justes étaient déclarées.

Workarray[X,Y] ;

Ce tableau est mon labyrinthe ? Sauf que dans ton algo un mur est -1, et que dans le mien c'est 1.

SetLength(PointX,grid.nbx*grid.nby) ;
SetLength(PointY,grid.nbx*grid.nby) ;
SetLength(PointP,grid.nbx*grid.nby) ;

La tu alloues de la mémoir aux trois variables.
Du style PointX = (int*) malloc (grid.nbx*grid.nby*sizeof(int)) ou c'est un malloc à deux dimensions, un sur les X et un sur les Y ??

// on traite les points voisins de Istart en évitant le point précédent (P)
// si le point voisin n'est pas un obstacle et s'il n'a pas été traité, on l'ajoute à la pile
P:=PointP[istart] ;
if (P>=0) and (PointX[P]<>X)

Je ne comprends pas la gestion de ta pile

[Graffito]

Que représente iend et istart, car ici ils n'ont pas de valeurs, ils ont justes étaient déclarées.

il s'agit des variables qui définissent l'intervalle à traiter dans la liste.
Au départ, l'intervalle ne comporte qu'un élément : la case de départ.

Ce tableau WorkArray est mon labyrinthe ? Sauf que dans ton algo un mur est -1, et que dans le mien c'est 1.

Comme son nom l'indique, WorkArray est un tableau interne temporaire utilisé par l'algorithme. Les valeurs des murs (-1) doivent être utilisées dans la fonction IsMapPathOK qui dit si la case est un obstacle ou non.

La tu alloues de la mémoir aux trois variables.
Du style PointX = (int*) malloc (grid.nbx*grid.nby*sizeof(int)) ou c'est un malloc à deux dimensions, un sur les X et un sur les Y ??

c'est la première option : 1 dimension (mais la liste des points à traiter peut contenir autant d'éléments qu'il y a de cases.

Pour la gestion de la pile, essayons une analogie avec la situation suivante :
- On veut aller à un point sur lequel est marqué "arrivée",
- On dispose d'un robot qui a la faculté de se cloner à sa convenance,
- Le robot est sur la case départ,
- Le robot est myope : sur une case, il ne voit que les cases contigues,
TRAVAIL DU ROBOT :
- le robot regarde si dans les cases voisines il y un obstacle,
- pour chaque case voisinne libre qui n'a pas été visitée, il se clone et envoie son clone sur cette case
- après avoir envoyé tous ses clones, le robot se suicide,
- lorsqu'un clone arrive sur une case, il met une petite fleche qui indique la direction de la case d'où il est venu (celà indique aussi que la case a été visitée).
- s'il n'est pas à l'arrivée le clone fait son travail
- s'il est à l'arrivée, grace aux petites flêches il peut refaire le chemin vers le départ.

[Trap D]

Salut

Je te propose cet algo qui utilise une file

la structure des éléments de la file est

• une copie du labyrinthe avec la trace du chemin parcouru
• le nombre de pas effectués
• la position actuelle

on intialise la file avec la position de départ

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
Algo de recherche
 
tant que la file n'est pas vide faire
  on extrait un element e de la file
  si on est sur la case d'arrivée alors
    on affiche la longueur du chemin
    on affiche le chemin
    on sort de la boucle
  fin si
   on marque la case courante comme visitée
  remarque on explore maintenant les quatre directions
  si la case du labyrinthe dans une direction n'est ni le mur ni déjà visitée alors
    on crée un nouvel élément de file avec 
         la recopie du labyrinthe courant
         le nombre de pas augmenté de 1
         la position de la case
    on met l'element dans la file
  fin si
fin tant que

J'ai joint le source si celà intéresse quelqu'un. (C sous Visual Studio 2005).

[fabetvince]

Merci Trap D pour ton algo et ton prog. Je vais le regarder et essayé de le comprendre.
J'ai réussi à trouver le chemin le plus court avec un autre algo. Il est un peu spécial, et très simple, je crée un tableau aussi grand que mon labyrinthe, je l'inistialise à 0. Je part du point de départ, je met un 1 dans ma copie à l'endroit de départ. Ensuite je balaye le tableau en cherchant un 1 et je regarde à coté de cette case si l'on peut avancer, et si l'on peux, je met un deux. Ensuite je cherche un 2 dans mon tableau et ainsi de suite.
Donc si mon chemin le plus court contient 50 cases, je parcourerai 50 fois mon labyrinthe.

[Trap D]

J'avoue que je ne comprends pas ton algo, peux-tu l'écrire en détail ?
Le mien correspond à une exploration systématique du labyrinthe à partir du départ, l'intérêt de la file est qu'on ne part pas dans l'exploration inutile d'une branche particulière, tous les chemins de longueur n sont explorés ensemble et avant tout chemin de longueur supérieure, ce qui fait que le premier chemin trouvé est obligatoirement le plus court.

[fabetvince]

Bon, en 1 je crée un tableau de la meme taille que mon lab, et je l'initialise à 0.
Ensuite je met à "1" la case ou se situe le départ.
Après je parcourt tout le tableau pour trouver le "1", et la si c'est possible, je met un deux dans les case adjacentes.
Après je reparcourt tout mon tableau à la recherche du "2", et je met à trois toutes les cases adjacentes qui peuvent etre parcouru par mon pion.
Apres pareille avec le 3, 4..... Jusqu'à la sortie. Et si un moment je ne peux plus avancer, c'est qu'il n'y a pas de chemin possible.
Ensuite j'ai pu qu'à reparcourir tout mon tableau pour trouver le chemin.

J'espere que c'est plus clair.