Implementer l'A* en c++

**juloss** · 14/05/2008, 17h04

Bomjour, je suis entrain de faire un programme qui cherche le chemin le plus court entre deux points.
Ces deux points sont sur une carte (tableau d'entier [20][20]).
J'ai implementer un algorithme qui ne marche pas...

Je ne suis pas très fort en IA, donc si quelqu'un connait un peu l'A*, est ce qu'il serait possible qu'il m'explique. Merci.

Voici mon 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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
 
#include <cstdlib>
#include <iostream>
#include <deque>
 
 
using namespace std;
 
int MAP[20][20]={ {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, //1
                  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, //2
                  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, //3
                  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, //4
                  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, //5
                  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, //6
                  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, //7
                  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, //8
                  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, //9
                  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, //10
                  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, //11
                  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, //12
                  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, //13
                  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, //14
                  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, //15
                  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, //16
                  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},//17
                  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, //18
                  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, //19
                  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} };//20
 
// Ce tableau represente la carte
 
class Case
{
public:
int x,y;
double Cout;
double Cout_Depart;
double Poids;
Case *parent;
 
  Case (int X, int Y, int COUT) //
  {                                     //
  x=X;                                 // Construsteur
  y=Y;                                //
  Cout=COUT;                     //
  }
 
  Case (const Case &A) 
  {
  x=A.x;
  y=A.y;
  Cout=A.Cout;
  parent=NULL;
  }
 
  void Calcul(const Case A,const Case B)
       {
       Cout= (A.x-x)*(A.x-x)+(A.y-y)*(A.y-y); 
       Cout_Depart= (B.x-x)*(B.x-x)+(B.y-y)*(B.y-y);  
       Poids = Cout_Depart+Cout;
       }
 
 double Calcul_G(const Case B)
       {
       return (B.x-x)*(B.x-x)+(B.y-y)*(B.y-y);  
       } 
 
 void Parent(Case &A)
      {
      parent=&A;
      }
  void Af()
 {
 MAP[x][y]==9;
 parent->Af(); 
 }
 
 
 
Case & operator=( const Case &a ) { x = a.x; y = a.y; Poids = a.Poids; return (*this);} 
bool operator<( const Case &a ) { return (Poids < a.Poids); } 
bool operator==( const Case &a ) { return ( a.x == x && a.y == y ); } 
};
 
 
 
 
deque<Case> Open;
deque<Case> Closed;
// Liste ouverte et liste fermée.
 
 
 
 
void Affiche()
{
Closed[0].Af();
}
 
 
 
 
 
 
int main(int argc, char *argv[])
{
int Xdep=100,Ydep=100,Xfin=100,Yfin=100;
bool C=true;
bool O=true;
int j=0;
 
// C et O servent à tester si une case est dans une des  
//deux listes.                
 
for(int i=0; i < 20 ; ++i)// POur afficher la carte.
{ 
   for(int j=0; j < 20 ; ++j)
    cout <<MAP[i][j];
 
cout <<endl;
}
cout <<endl
     <<"Entrer les coordonnees du points de depart (x,y,)"
     <<endl
     <<"puis les coordonnees du points d'arriver (x',y')"   
    <<endl;
 
 
while (Xdep >=20 || Xdep <0 || Xfin >=20 || Xfin <0) 
{
cin  >>Xdep>>Ydep>>Xfin>>Yfin;
}
//Teste la validité des coordonnées.
 
Case depart(Xdep,Ydep,100);
Case Arrive(Xfin,Yfin,0);
Case Test_Poids(0,0,0);
Case Test_Cardinaux(0,0,0);
// on creé 4 case :
//    celles de départ et d'arriver,
//    deux cases temporaire pour le calcul des poids.
 
 
Open.push_front( depart );
 
 
while(!Open.empty())
{
 
   for(int i=0;i <=Open.size() ; i++)
    if( Open[i] < Test_Poids)
      Test_Poids=Open[i];
// On cherche la case avec le cout le plus faible.
 
Closed.push_front(Test_Poids);
// On l'ajoute a la liste fermée
 
 
if(Closed[0]==Arrive)
{
Affiche();
break;
} 
// Si on est arrrivé.
 
C=true;
O=true;
 
// Case x+1 
Test_Cardinaux.x=Test_Poids.x+1;
Test_Cardinaux.y=Test_Poids.y;
 
  if(MAP[Test_Cardinaux.x][Test_Cardinaux.y]==0)
   {   
       for(int i=0;i <=Closed.size() ; i++)
         if(Test_Cardinaux==Closed[i])
            C=false;
 
       for( j=0;j <=Open.size() ; j++)
         if(Test_Cardinaux==Open[j])
           O=false;
 
      if(C && !O)
      {
      Test_Cardinaux.Calcul(Arrive, depart);
      Test_Cardinaux.Parent(Test_Poids);
      Open.push_front(Test_Cardinaux);
      }
      else if(O && C)
       if(Test_Cardinaux.Cout_Depart > Test_Cardinaux.Calcul_G(depart))
        {
        Test_Cardinaux.Cout_Depart=Test_Cardinaux.Calcul_G(depart);
        Test_Cardinaux.Parent(Test_Poids);
        Test_Cardinaux.Calcul(Arrive, depart); 
       Open[j]=Test_Cardinaux;
        }  
   }
 
C=true;
O=true;
 
// Case x-1 
Test_Cardinaux.x=Test_Poids.x-1;
Test_Cardinaux.y=Test_Poids.y;
 
  if(MAP[Test_Cardinaux.x][Test_Cardinaux.y]==0)
   {   
       for(int i=0;i <=Closed.size() ; i++)
         if(Test_Cardinaux==Closed[i])
            C=false;
 
       for( j=0;j <=Open.size() ; j++)
         if(Test_Cardinaux==Open[j])
           O=false;
 
      if(C && !O)
      {
      Test_Cardinaux.Calcul(Arrive, depart);
      Test_Cardinaux.Parent(Test_Poids);
      Open.push_front(Test_Cardinaux);
      }
      else if(O && C)
       if(Test_Cardinaux.Cout_Depart > Test_Cardinaux.Calcul_G(depart))
        {
        Test_Cardinaux.Cout_Depart=Test_Cardinaux.Calcul_G(depart);
        Test_Cardinaux.Parent(Test_Poids);
        Test_Cardinaux.Calcul(Arrive, depart); 
       Open[j]=Test_Cardinaux;
        }  
   } 
 
C=true;
O=true;
 
// Case y+1 
Test_Cardinaux.x=Test_Poids.x;
Test_Cardinaux.y=Test_Poids.y+1;
 
  if(MAP[Test_Cardinaux.x][Test_Cardinaux.y]==0)
   {   
       for(int i=0;i <=Closed.size() ; i++)
         if(Test_Cardinaux==Closed[i])
            C=false;
 
       for( j=0;j <=Open.size() ; ++j)
         if(Test_Cardinaux==Open[j])
           O=false;
 
      if(C && !O)
      {
      Test_Cardinaux.Calcul(Arrive, depart);
      Test_Cardinaux.Parent(Test_Poids);
      Open.push_front(Test_Cardinaux);
      }
      else if(O && C)
       if(Test_Cardinaux.Cout_Depart > Test_Cardinaux.Calcul_G(depart))
        {
        Test_Cardinaux.Cout_Depart=Test_Cardinaux.Calcul_G(depart);
        Test_Cardinaux.Parent(Test_Poids);
        Test_Cardinaux.Calcul(Arrive, depart); 
       Open[j]=Test_Cardinaux;
        }  
   }
 
C=true;
O=true;
 
// Case y-1 
Test_Cardinaux.x=Test_Poids.x;
Test_Cardinaux.y=Test_Poids.y-1;
 
  if(MAP[Test_Cardinaux.x][Test_Cardinaux.y]==0)
   {   
       for(int i=0;i <=Closed.size() ; i++)
         if(Test_Cardinaux==Closed[i])
            C=false;
 
       for( j=0;j <=Open.size() ; ++j)
         if(Test_Cardinaux==Open[j])
           O=false;
 
      if(C && !O)
      {
      Test_Cardinaux.Calcul(Arrive, depart);
      Test_Cardinaux.Parent(Test_Poids);
      Open.push_front(Test_Cardinaux);
      }
      else if(O && C)
       if(Test_Cardinaux.Cout_Depart > Test_Cardinaux.Calcul_G(depart))
        {
        Test_Cardinaux.Cout_Depart=Test_Cardinaux.Calcul_G(depart);
        Test_Cardinaux.Parent(Test_Poids);
        Test_Cardinaux.Calcul(Arrive, depart); 
       Open[j]=Test_Cardinaux;
        }  
   }   
}
 
for(int i=0; i < 20 ; ++i)
{ 
   for(int j=0; j < 20 ; ++j)
    cout <<MAP[i][j];
 
cout <<endl;
}
 
    system("PAUSE");
    return EXIT_SUCCESS;
}

**Davidbrcz** · 14/05/2008, 17h45

Pas d'erreur donné , pas le moindre commentaire.
On peut faire quoi là ?
A part dire :

Tient un code de 3Km de long !

**Feriaman** · 14/05/2008, 17h48

Envoyé par juloss

Bomjour, je suis entrain de faire un programme qui cherche le chemin le plus court entre deux points.

Salut,

c'est assez amusant l'Astar et j'aurais vraiment bien aimé te répondre.

peux-tu clarifier ton code en :
- le divisant en fonctions que tu prendras soin de nommer de façon intelligible.
- séparant les déclarations (.h) des implémentations (.cpp), ce qui te permettra de ne pas coder toute l'implémentation sur une même ligne, en rendant ainsi ton code encore plus clair.
- uniformisant les indentations
- adoptant une attitude systématique pour les noms de tes variables, voir en en renommant certaines COUT devrait par exemple s'appeler NewCout ou quelque chose comme ça.
- ajoutant des commentaires

et aussi corriger quelques petites erreurs comme :
- remplacer les "const Case" par des "const Case&"
- vérifier que tes pointeurs ne sont pas nulls avant de les utiliser (parent)

Comme ça, je pourrais lire ton code et te dire ce que j'en pense

**Alp** · 14/05/2008, 18h03

Bonjour,

Une petite recherche de ta part n'aurait pas été de trop

http://khayyam.developpez.com/articles/algo/astar/

**Feriaman** · 14/05/2008, 18h28

Envoyé par Alp

Bonjour,
Une petite recherche de ta part n'aurait pas été de trop

http://khayyam.developpez.com/articles/algo/astar/

Je pense qu'il a cherché et qu'il essaie de la recoder à sa sauce. C'est comme cela que l'on apprend n'est-ce pas ? En tout cas, je trouve que la démarche se justifie :
- lire la théorie
- coder à sa sauce
- lire les solutions proposées par d'autres.
Voilà qui ne peut qu'être bénéfique à tous.

C'est un processus d'apprentissage qui ma parait assez sain. Si on peut être utile et lui donner des pistes pour apprendre, profitons-en.

Implementer l'A* en c++

C++

Discussions similaires

Partager

Partager