164
Recherche de plus court chemin sur une carte
}
}
while (stackAt [currentg ]. size ()
currentg+ +;
}
if (currentg >= height * width )
return currentg ;
current = stackAt [currentg ].back ();
stackAt [currentg ].pop_back ();
return currentg ;
8.5.2 A*
A* est une généralisation de Dijkstra car A* avec h
Dijkstra.
0) {
0 simule l'algorithme de
Ne pas ré-explorer les points déjà atteints par un chemin plus court ou de longueur
égale au chemin courant est important dans la recherche de plus court chemin sur une
carte.
Une méthode simple pour ne pas ré-étudier ces points est de parcourir la liste des
noeuds de A* pour vérifier si le point a déjà été atteint avec un chemin plus court. To utefois cette méthode devient vite inefficace lorsque le nombre de noeuds de A* grandit.
On peut tirer partie de la taille réduite en mémoire des cartes de jeux pour utiliser un
tableau de la taille de la carte qui mémorise le plus court chemin étudié pour chaque point.
On appelle ce tableau g puisqu'il contient pour chaque point le plus petit g qui a conduit
à ce point. A chaque passage par le point, la valeur de g de la feuille est comparée à ce
plus court chemin. Si le g de la feuille est strictement plus petit, la valeur est remplacée
et la recherche continue. Si g est plus grand ou égal au plus court chemin, la recherche
est arrétée. Notez qu'on peut encore accélerer le programme en utilisant une initialisation
paresseuse pour le tableau g.
Le code pour A* sur une carte est :
int manhattan (Point p, Point goal ) {
return abs (p.x - goal .x) + abs (p.y - goal .y);
}
class Node {
public :
} ;
Point p;
int g;
list stackAtf [MaxEdge * MaxEdge ];