8.5 Corrigés des exercices
int astar (Point start , Point goal ) {
for (int i = O; i < height ; i++)
fo r (int j = O; j < width ; j++)
g [i] ( j] = -1;
fo r ( int i = O; i < height * width ; i ++)
stackAtf [i]. clear ();
nodes = l;
int currentf = O;
Node current , tmp ;
current .p = start ;
current . g = O;
g [start .x] [start .y] = O;
while ( current . p != goal ) {
i f ( c u r r e n t . g <= g [ c u r r e n t . p . x ] [ c u r r e n t . p . y ] ) {
11 if ( true ) {
}
nodes ++;
Point p [4] ;
p [O]. set (current .p.x + 1, current .p.y);
p [l]. set (current .p.x - 1, current .p.y);
p [2]. set (current .p.x, current .p.y + l);
p [3]. set (current .p.x, current .p.y - l);
for (int i= O; i < 4; i++)
if ((p [i].x >= 0) && (p [i].x < width ) &&
( p [ i ] . y >= 0 ) && ( p [ i ] . y < h e i g h t ) )
if ( map [ p [ i ] . x] [ p [ i ] . y] -- 0) {
}
int f = current .g + l +
manhattan (p [ i], goal );
if (f < curr entf)
fprintf (stderr , "not�consistent ");
i f ( g ( p ( i ) . X ) ( p ( i ) . y ) == - l) {
}
g [p [i].x] [p [i].y] = current . g + l;
tmp . p = p [ i ] ;
tmp .g = current .g + l;
stackAtf [f].push_back (tmp);
else if (g [p [i].x] [p [i ].y] >
}
current .g + 1) {
g [p [i].x] [p [i].y] = current .g + l;
tmp . p = p [ i ] ;
tmp .g = current .g + l;
stackAtf [f].push_back (tmp);
165