Discussion :

[poly128]

Je fais présentement un jeux (du style age of empire) avec delphi 6. Mais j'ai un probleme. Lorceque je demande a mes unités de se déplacer ils vont au point indiquer en ligne droite sans éviter les obstacle(maison,arbre,falaise, etc...). J'aimerais savoir comment faire pour trouver le chemin le plus court entre deux pixels à l'écran tout en évitant les obstacles pour qu'enfin les unités ne marche plus sur les maisons.

[Graffito]

Bonjour,

Voilà un bout de code qui fonctionne (bien).
Malheuresement, c'est un vieux code que j'avais pas commenté.
La fonction MAP_IsPathOk indique si'il la case n'est pas un obstacle.

CODE SUPPPRIME : voir code commenté dans message suivant.

[poly128]

Merci mais je ne comprend pas très bien ton code. J'ai esseyer de plusieur facon et il me sort toujours des erreur (workArray non déclaré),(la fonction nessesite un type de résultat). Est que tu pourais m'expliquer un peu.

[anapurna]

Salut

fait une recherche sur l'algoritme "pathfinding" il exite beaucoup d'exemple

@+ Phil

[DMO]

Salut,

En effet, anapurna te donne le "bon mot" à chercher.

Ce que tu cherches a déjà été maintes fois débattu sur le forum Algo.
Par exemple ce fil te donne plein de pistes :
http://www.developpez.net/forums/sho...g+court+chemin

Bonne recherche, puis bon dev' !

[Graffito]

Bonjour,
Mes messages précédents sont partis tout seul (il semble que l'utilisation de la touche TAB pose problème).

J'ai commenté le code :

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
function TMapObj.Map_PathFind(StartPathX,StartPathY,EndPathX,EndPathY:integer):integer ;
// input : coordonnées des positions de départ et d'arrivée. result = longueur du plus court chemin
var PointX,PointY,PointP : array of integer ;
    istart,iend : integer ;
(**)procedure AddPoint(X,Y:integer) ;
    // Ajout d'un nouveau point à traiter  dans la pile
    // PointP est un lien sur le point précédent du chemin
    begin
    inc(iend) ;
    PointP[iend]:=istart ;
    PointX[iend]:=X ;
    PointY[iend]:=Y ;
    Workarray[X,Y]:=1 ; // indique que le point de la carte est dans la pile de traitement
    end ;
var X,Y,i,j,k,P :  integer ;
begin
// teste si les points de départ et d'arrrivée sont sur des obstacles
if MAP_IsPathOk(StartPathX,StartPathY) and MAP_IsPathOk(EndPathX,EndPathY)
   then begin
        // allocation d'espace dans la pile
        result:=-1 ;
        SetLength(PointX,grid.nbx*grid.nby) ;
        SetLength(PointY,grid.nbx*grid.nby) ;
        SetLength(PointP,grid.nbx*grid.nby) ;
        // il faut aussi allouer le tableau workarray à 2 dimensions
        // qui comporte autant de cases que la carte + bordure exterieure
        // init du tableau à 0 sauf obstacle à -1
        // toutes les cases de la bordure extérieure en tant qu'obstacle
        for i:=0 to grid.nby-1 do for j:=0 to grid.nbx-1 do
            if Map_isPathOK(i,j)
               then workarray[i,j]:=0
               else workarray[i,j]:=-1 ;
        // mettre le point de départ dans la pile
        // istart/iend=premier/dernier point à traiter
        istart:=0 ;
        iend:=0 ;
        for i:=0 to grid.nby do workarray[grid.nbx,i]:=-1 ;
        for i:=0 to grid.nbx do workarray[i,grid.nby]:=-1 ;
        PointP[0]:=-1 ;
        PointX[0]:=StartPathX ;
        PointY[0]:=StartPathY ;
        while (iend>=istart) do begin
        // traiter tous les points de la pile jusqu'à tomber sur le point d'arrivée
             X:=PointX[istart] ; Y:=PointY[istart]   ;
             if (X=EndPathX) and (Y=EndPathY)
                then begin
                     // on tombe sur l'arrivee : bingo
                     result:=0 ;
                     iend:=-1 ;
                     end
                else begin
                // 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)
                        then begin
                             if (Y>0) and (workArray[X  ,Y-1]=0) then AddPoint(X  ,Y-1) ;
                             if           (workArray[X  ,Y+1]=0) then AddPoint(X  ,Y+1) ;
                             if (X>0) and (workArray[X-1,Y  ]=0) then AddPoint(X-1,Y  ) ;
                             if           (workArray[X+1,Y  ]=0) then AddPoint(X+1,Y  ) ;
                             end
                        else begin
                             if (X>0) and (workArray[X-1,Y  ]=0) then AddPoint(X-1,Y  ) ;
                             if           (workArray[X+1,Y  ]=0) then AddPoint(X+1,Y  ) ;
                             if (Y>0) and (workArray[X  ,Y-1]=0) then AddPoint(X  ,Y-1) ;
                             if           (workArray[X  ,Y+1]=0) then AddPoint(X  ,Y+1) ;
                             end ;
                     inc(istart) ;
                     end ;
             end ;
        end
   else result:=-1 ;
if result=0 then begin
  // on réutilise les tableaux POintX/PointY en partant du dernier élément pour stocker le chemin
  // istart = dernier point traité de la pile (en début de while, c'est l'arrivée, à la fin c'est 0 =départ)
  // iend = point du chemin stocké dans la fin de tableau
  iend:=grid.nbx*grid.nby-1 ;
  //  on trouve la longueur et le chemin parcourt les liens de la pile (liste des prédecesseurs en partant de l'arrivée)
  while istart>=0 do begin
        PointX[iend]:=PointX[istart] ; PointY[iend]:=PointY[istart] ;
        dec(iend) ; inc(result) ;
        istart:=PointP[istart] ;
        end ;
  dec(result) ;
  // tracé du chemin (on parcourt la fin de tableau en déscendant)
  for i:=grid.nbx*grid.nby-1 downto iend+1 do begin
      MapCell[PointX[i],Pointy[i]]:=-3 ;  //  marque la case comme apparenant au chemin
      Map_DrawCell(PointX[i],Pointy[i]) ;
      end ;
  end ;

end ;

[Fabrice ROUXEL 1]

Tu as un exemple d'algorithme de tracé de chemin avec obstacle dans le package pédagogique de RM Di Scala télechargeable sur le site.

[poly128]

Enfin ca marche!!! Merci graffito, ta fonction marche a merveille.

[Kahiba]

Oublie pas de mettre "resolu" dans ton titre