Vous souhitez écrire un programme qui puisse se débrouiller tout seul pour amener un objet d'un point à un autre, le plus rapidement possible et en évitant les obstacles éventuels, l'algorithme A* (prononcer A star) est fait pour vous.
C'est un algorithme de recherche de chemin dans un graphe. C'est l'un des plus efficaces en la matière. Il ne donne pas toujours la solution optimale mais il donne très rapidement une bonne solution.
II. Principe de l'algorithme
Au premier abord, on pourrait se dire que pour trouver un chemin d'un point à un autre il faut commencer par se diriger vers la destination. Et bien ... c'est justement cette idée qu'utilise l'algorithme A*. L'idée est très simple : à chaque itération (oui, c'est un algorithme itératif), on va tenter de se rapprocher de la destination, on va donc privilégier les possibilités directement plus proches de la destination, en mettant de côté toutes les autres.
Toutes les possibilités ne permettant pas de se rapprocher de la destination sont mises de côté, mais pas supprimées. Elles sont simplement mises dans une liste de possibilités à explorer si jamais la solution explorée actuellement s'avère mauvaise. En effet, on ne peut pas savoir à l'avance si un chemin va aboutir ou sera le plus court. Il suffit que ce chemin amène à une impasse pour que cette solution devienne inexploitable.
L'algorithme va donc d'abord se diriger vers les chemins les plus directs. Et si ces chemins n'aboutissent pas ou bien s'avèrent mauvais par la suite, il examinera les solutions mises de côté. C'est ce retour en arrière pour examiner les solutions mises de côté qui nous garantit que l'algorithme nous trouvera toujours une solution (si tenté qu'elle existe, bien sûr).
On peut donc lui donner un terrain avec autant d'obstacles qu'on veut, aussi tordus soient-ils, s'il y a une solution, A* la trouvera.
II-1. Les listes A*
A* utilise deux listes, ces listes contiennent des points. Pour être plus général, on peut même dire que ces listes contiennent des noeuds d'un graphe, lequel graphe représentant notre terrain.
La première liste, appelée liste ouverte, va contenir tous les noeuds étudiés. Dès que l'algorithme va se pencher sur un noeud du graphe, il passera dans la liste ouverte (sauf s'il y est déjà).
La seconde liste, appelée liste fermée, contiendra tous les noeuds qui, à un moment où à un autre, ont été considérés comme faisant partie du chemin solution. Avant de passer dans la liste fermée, un noeud doit d'abord passer dans la liste ouverte, en effet, il doit d'abord être étudié avant d'être jugé comme bon.
II-2. Déroulement de l'algorithme
Pour déterminer si un noeud est suceptible de faire partie du chemin solution, il faut pouvoir quantifier sa qualité. Vous êtes entièrement libre de ce côté là, vous pouvez mesurer la pertinence d'un noeud de la manière qui vous plait. Néanmoins, une méthode souvent utilisée et qui donne de bons résultats est de mesurer l'écartement entre ce noeud et le chemin à vol d'oiseau. On calcule donc la distance entre le point étudié et le dernier point qu'on a jugé comme bon. Et on calcule aussi la distance entre le point étudié et le point de destination. La somme de ces deux distances nous donne la qualité du noeud étudié. Plus un noeud à une qualité faible, meilleur il est.
Vous pouvez calculer ces distances de la manière que vous voulez, distance euclidienne, distance de Manhattan ou autre, elles peuvent convenir.
Attention cependant avec la distance euclidienne : elle fait intervenir une racine carrée et donc des nombres flottants, beaucoup plus lents à manipuler que des nombres entiers. Vous pouvez donc aussi manipuler la carré de la distance euclidienne. Les résultats peuvent être légèrement différents, mais c'est beaucoup plus rapide.
La caractère minorant ou non de l'heuristique utilisée pour calculer la distance va également jouer sur la convergence optimale ou non de l'algorithme : l'utilisation d'une heuristique minorante fournira le résultat optimal.
On ne sait pas grand chose du chemin solution si ce n'est que le point qui pourra nous rapprocher de la solution est un point voisin du point que nous étudions. On va donc étudier chacun des noeuds voisins du noeud courant pour déterminer celui qui a le plus de chances de faire partie du chemin solution.
La recherche du chemin commence par le premier point, en étudiant tous ses voisins, en calculant leur qualité, et en choisissant le meilleur pour continuer. Chaque point étudié est mis dans la liste ouverte et le meilleur de cette liste passe dans la liste fermée, il va servir de base pour la recherche suivante.
Pour déterminer le meilleur point pour continuer le chemin, il ne faut pas uniquement chercher celui qui a la meilleure qualité dans ses voisins, mais dans toute la liste ouverte. C'est comme ça qu'on pourra abandonner un chemin qui avait l'air bon au début et qui ne l'était pas.
Ainsi, à chaque itération on va regarder parmi tous les noeuds qui ont été étudiés (et qui n'ont pas encore été choisis) celui qui a la meilleure qualité. Et il est tout à fait possible que le meilleur ne soit pas un voisin direct du point courant. Cela signifira que le point courant nous éloigne de la solution et qu'il faut corriger le tir.
L'algorithme s'arrête quand la destination a été atteinte ou bien lorsque toutes les solutions mises de côté ont été étudiées et qu'aucune ne s'est révélée bonne, c'est le cas où il n'y a pas de solution.
II-3. Détermination des noeuds voisins
Si on considère notre domaine de recherche comme un graphe, tous les noeuds voisins d'un noeud courant sont les noeuds adjacents. Mais si on considère notre domaine de recherche comme une carte (ou une image), ce sont tous les points adjacents (en haut, en bas, à gauche, à droite et les points en diagonale) sauf si ceux-ci contiennent des obstacles infranchissables (mur, montagne, rivière ...).
Donc, avant de se lancer dans l'étude de la qualité de chacun des noeuds adjacents, il ne faut prendre que ceux qui sont vraiment utilisables. Il faut aussi mettre de côté tous les noeuds déjà présents dans la liste ouverte ou dans la liste fermée. Et pour être plus précis, je dirais qu'il ne faut pas prendre un point s'il est déjà dans la liste ouverte, à moins qu'il ne soit meilleur, auquel cas on va mettre à jour la liste ouverte.
Ce qu'il faut regarder sur chacun des noeuds voisins potentiels :
Est-ce un obstacle ? si oui, on oublie ce noeud.
Est-il dans la liste fermée ? si oui, ce noeud a déjà été étudié ou bien est en cours d'étude, on ne fait rien.
Est-il dans la liste ouverte ? si oui, on calcule la qualité de ce noeud, et si elle est meilleure que celle de son homologue dans la liste ouverte, on modifie le noeud présent dans la liste ouverte.
Sinon, on l'ajoute dans la liste ouverte et on calcule sa qualité.
II-4. Notion de parent d'un noeud
Chaque noeud a un parent, c'est par lui qu'on arrive là où on est. Le parent représente le meilleur chemin entre deux noeuds. Le parent est très important à la fin de l'algorithme, pour retrouver ton chemin.
Il joue aussi un rôle important lors de la mise à jour d'un noeud dans la liste ouverte. Nous avons vu qu'il fallait mettre à jour la liste ouverte dans le cas où un noeud avait une meilleure qualité que ce même noeud dans la liste ouverte. Nous avons mis à jour la qualité du noeud dans la liste ouverte, mais il faut aussi mettre à jour son parent, pour bien sigifier que cette qualité est possible par tel parent précis.
Une fois que la destination a été atteinte, il faut retrouver le chemin en suivant à chaque fois les parents des noeuds présents dans la liste fermée. On remonte le fil jusqu'à arriver au point de départ.
II-5. Résumé des étapes
On commence par le noeud de départ, c'est le noeud courant
On regarde tous ses noeuds voisins
si un noeud voisin est un obstacle, on l'oublie
si un noeud voisin est déjà dans la liste fermée, on l'oublie
si un noeud voisin est déjà dans la liste ouverte, on met à jour la liste ouverte si le noeud dans la liste ouverte a une moins bonne qualité (et on n'oublie pas de mettre à jour son parent)
sinon, on ajoute le noeud voisin dans la liste ouverte avec comme parent le noeud courant
On cherche le meilleur noeud de toute la liste ouverte. Si la liste ouverte est vide, il n'y a pas de solution, fin de l'algorithme
On le met dans la liste fermée et on le retire de la liste ouverte
On réitère avec ce noeud comme noeud courant jusqu'à ce que le noeud courant soit le noeud de destination.
Voici une illustration d'une itération de l'algorithme. On souhaite aller du point orange au point bleu. Les noeuds voisins de la case orange sont les cases marquées en vert, ils passent en liste ouverte. Et de chacune d'elles on calcule les couts G et H pour aller à la case orange et pour aller à la destination. J'ai choisi la distance à vol d'oiseau. Et la case qui aura le cout le plus faible sera la case verte du dessous, elle va donc passer en liste fermée. L'algorithme va réitérer à partir de cette case.
III. Implémentation
Tout ceci est très théorique, je vais expliquer mon implémentation en C++, elle pourra éclaircir mes propos. Je choisi de travailler sur une image, donc sur un espace discret. Les noeuds voisins d'un pixel sont donc les pixels directement voisins.
Boost.graph implémente l'algorithme A* pour les parcours de graphe, ça peut donc être une alternative très intéressante si vous developpez en C++.
III-1. Choix des structures de données
Il nous faut de quoi représenter la liste ouverte et la liste fermée. Un noeud ne peut apparaître qu'une fois dans chaque liste. S'il y a des doublons, c'est une erreur dans l'implémentation. J'ai choisi de représenter mes listes par des std::map. Chaque noeud ayant pour clé une position (x,y) représentée par un std::pair<int,int>. Un noeud n'étant rien de plus que le regroupement des informations suivantes :
le coutG (le cout pour aller du point de départ au noeud considéré)
le coutH (le cout pour aller du noeud considéré au point de destination)
le coutF (somme des précédents mais mémorisé pour ne pas le recalculer à chaque fois)
le parent, représenté par ses coordonnées (suffisantes pour retrouver ensuite l'élément dans les listes car les coordonnées sont les clés dans les std::maps)
Le parent peut être considéré comme un pointeur vers le noeud parent. Mais il ne faut en aucun cas le représenter avec un pointeur mémoire. En effet, rien ne nous dit que la STL ne va pas réarranger l'espace mémoire des maps lors des ajouts/suppression successifs, modifiant les adresses mémoires de nos objets (et par la même, déréférençant nos pointeurs). C'est la raison pour laquelle j'ai choisi un système d'adressage indépendant des adresses mémoires : les pair<int,int>
Il faudra aussi une structure représentant un point (x,y), bien qu'on aurait pu prendre un simple std::pair<int,int> :
struct point{int x,y;
};
Le type représentant nos listes se résume donc à un simple
typedef map< pair<int,int>, noeud> l_noeud;
III-2. Outils nécessaires
Je vais avoir besoin de plusieurs traitements annexes : les fonctions d'acquisition des données, d'enregistrement, et la calcul des distances. Pour des raisons de simplicité, j'ai choisi d'utiliser de représenter mes données entrantes par une image (le noir représentant les obstacles) et de présenter les résultats également sous forme d'une image (l'image de départ, avec le chemin solution dessiné en bleu).
Chargement des données
SDL_Surface *s =SDL_LoadBMP("carte.bmp");
Enregistrement des résultats
SDL_SaveBMP(s, "resultat.bmp");
Calcul des distances
/*calculeladistanceentrelespoints(x1,y1)et(x2,y2)*/floatdistance(int x1, int y1, int x2, int y2){/*distanceeuclidienne*/returnsqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
/*carrédeladistanceeuclidienne*//*return(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);*/}
Et une petite fonction pour tester l'existence d'un élément dans une liste donnée :
booldeja_present_dans_liste(pair<int,int> n, l_noeud& l){l_noeud::iterator i = l.find(n);
if (i==l.end())
returnfalse;
elsereturntrue;
}
III-3. L'algorithme proprement dit
Une grosse partie de l'algorithme consiste à repérer les noeuds adjacents et à les ajouter ou non à la liste ouverte.
On recherche les noeuds voisins du noeud dont les coordonnées sont passées en paramètre. tmp sera un noeud temporaire.
/*onmettouslesnoeudadjacentsdanslalisteouverte(+vérif)*/for (int i=n.first-1; i<=n.first+1; i++){if ((i<0) || (i>=s->w)) /*endehorsdel'image,onoublie*/continue;
for (int j=n.second-1; j<=n.second+1; j++){if ((j<0) || (j>=s->h)) /*endehorsdel'image,onoublie*/continue;
if ((i==n.first) && (j==n.second)) /*caseactuellen,onoublie*/continue;
if (*((Uint8 *)s->pixels + j * s->pitch + i * s->format->BytesPerPixel) == NOIR)
/*obstace,terrainnonfranchissable,onoublie*/continue;
pair<int,int>it(i,j);
Le code ci-dessus détermine si un pixel voisin peut faire partie de la solution, il élimine tous les cas ne correspondant pas : les pixels en dehors de l'image, ceux infranchissables et celui occupé par le pixel courant.
Ce code s'occupe de l'insertion d'un noeud dans la liste ouverte si besoin est. Il vérifié si un noeud est présent ou non dans la liste fermée et dans la liste ouverte, et il met à jour la liste ouverte si le nouveau noeud s'avère meilleur que celui déjà présent.
Il nous faut aussi une fonction permettant d'obtenir le meilleur noeud de la liste ouverte :
pair<int,int>meilleur_noeud(l_noeud& l){float m_coutf = l.begin()->second.cout_f;
pair<int,int> m_noeud = l.begin()->first;
for (l_noeud::iterator i = l.begin(); i!=l.end(); i++)
if (i->second.cout_f< m_coutf){
m_coutf = i->second.cout_f;
m_noeud = i->first;
}return m_noeud;
}
Ce code se contente de parcourir la liste pour repérer le noeud qui a le cout F le plus faible. Il retourne les coordonnées (x,y) de ce noeud.
Il peut être très intéressant d'utiliser une structure triée. La recherche de maximum s'en trouve donc considérablement accélérée.
Le jeu entre la liste ouverte et la liste fermée est fait par la fonction d'ajout en liste fermée :
Pas grand chose à dire sur cette petite fonction. Elle passe un noeud de la liste ouverte vers la liste fermée.
Le dernier traitement dont nous avons besoin est celui qui consiste à retrouver le chemin une fois que la destination a été atteinte. On remonte les noeuds de parent en parent. Chaque noeud est ajouté en tête d'une liste, de manière à reconstituer le chemin à partir de la fin
Voici quelques exemples plus ou moins tarabiscotés de recherche de chemin :
Aucun obstacle, le chemin est direct
Un obstacle, la solution le contourne
La solution n'est pas le chemin direct
V. Améliorations possibles
Essayez de lancer cet algorithme sur une très grande carte et vous verrez que ça commence à prendre du temps. Et si vous avez besoin d'un réponse rapide de votre programme vous ne pourrez pas vous permettre de prendre plusieurs secondes pour calculer le chemin. Une solution est donc de découper le chemin entre plusieurs points connus.
Utilisez une structure de liste triée pour repérer rapidement le meilleur noeud
Faites des calculs en valeurs entières
V-1. Applications dans les jeux
Quand vous demandez à un bonhomme de se rendre à l'autre bout de la carte, il n'est pas nécessaire de calculer dès le début tout le chemin. Définissez des points clés et faites déjà la recherche de chemin vers le point clé qui correspond à sa position et à sa destination. Vous aurez ensuite le temps de préparer la suite du chemin.
Le jeu connais la carte, vous pouvez donc précalculer des parcours type ou des morceaux de parcours entre des points clés
Si vous calculez tout le chemin dès le début, votre bonhomme évitera dès le début toutes les impasses et tous les culs de sac qu'il aurait pu rencontrer. Pas très réaliste. Découpez la recherche en fonction de l'avancement du personnage.
Si le chemin proposé par l'algorithme passe dans une zone dangereuse, il n'est pas très réaliste d'y aller. Prévoyez un indicateur de danger selon l'endroit et tenez-en compte dans la recherche de chemin en alourdissant le cout pour se rendre à un noeud dangereux. Il cherchera d'abord les chemins les moins dangereux.
Toute mon implémentation a été faite à partir d'une image. Mais dans le cas où vous devez manipuler une grille de jeu ou toute autre structure différente, il y a des modifications à apporter au code. Bien évidemment l'algorithme reste le même.
Les modifications auront lieu dans la recherche des noeuds voisins. Sur une image, les noeuds voisins sont les pixels voisins, mais sur une grille de jeu différente, les noeuds voisins peuvent être représentés différemment. C'est pourquoi il sera peut-être nécessaire de réaliser une conversion entre votre grille de jeu et une structure plus facilement exploitable par A*. Mais ceci n'est qu'une question d'implémentation et ne dépend pas directement de l'algorithme.
VI. Conclusion
Voilà, vous savez comment fonctionne l'algorithme A*. Il ne donne pas toujours la meilleure solution mais il en donne une bonne. On pourrait comparer ses performances avec celles de l'algorithme de Dijkstra. Dijkstra donne la meilleure solution, mais A* est plus rapide.
Et comme dans beaucoup d'algorithmes, le programmeur a une grande liberté dans son implémentation : vous pouvez modifier les méthodes de calcul de distances, pondérer certains noeuds, en privilégier d'autres ...
