156
Recherche de plus court chemin sur une carte
Algorithm 7 Recherche du plus court chemin sur une carte avec l ' algorithme A*
A* (depart, arrivee)
for tous les points de la carte do
g [point]+--1
end for
positions à développer +-0
point +-depart
point.g +-0
g [point] +-0
while point =f. arrivee do
if point.g ::; g [point] then
for tous les voisins de point do
if voisin est accessible then
f +-point.g + 1 + manhattan (voisin, arrivee)
if g [voisin] = -1 ou g [voisin]> point.g + 1 then
g [voisin] +-point.g + 1
voisin.g +-point.g + 1
aj outer voisin dans les positions à développer de rang f
end if
end if
end for
end if
retirer le point qui a le plus petit f des positions à développer
end while
retourner g [arrivee]