166
Recherche de plus court chemin sur une carte
}
}
w h il e ( s tac k A t f [ c u r r e n t f ] . s i z e () == 0 ) {
currentf++;
}
if (currentf >= height * width )
return currentf ;
current = stackAtf [currentf ].back ();
stackAtf [currentf ].pop_back ();
return currentf ;
Lorsque les déplacements diagonaux sont autorisés, en supposant que les déplacements horizontaux et verticaux coûtent 2 et que les déplacements diagonaux coûtent 3,
l ' heuristique de Manhattan devient :
int manhattan (Point p, Point goal ) {
int dx = abs (p.x - goal .x);
int dy = abs (p .y - goal .y);
return 3 * min ( dx , dy ) +
2 * (max (dx, dy ) - min (dx, dy ));
}
8.5.3 L'heuristique triangulaire
Avec les deux équations on obtient :
llD, All 2 lllD, Pll - llA, Plll
D 'où une heuristique admissible qui utilise les distances pré calculées :
h = lllD,Pll - llA, P lll
L' implémentation de l 'heuristique est la suivante :
const int nbPointsTriangular = 8;
Point pointTriangular [ nbPointsTriangular ];
int distFrom [ nbPointsTriangular ] [MaxEdge ] [MaxEdge ];
int manhattan (Point p, Point goal ) {
int h = abs (p.x - goal .x) + abs (p.y
goal .y);
fo r (int i = O; i < nbPointsTriangular ; i++) {
(8.3)
(8.4)