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*
***************