Pathfinding avec A* (A star)

Bien souvent, il est nécessaire lorsque l'on réalise un jeu, de mettre en place un algorithme de pathfinding. Le plus connu d'entre eux est probablement le A* (prononcer ''A' star').

1- Principes

Les prérequis indispensables à l'utilisation de cet algorithme sont :
-  de formaliser la zone à parcourir sous la forme d'un réseau. Ce dernier peut se présenter sous la forme d'une grille, mais ce n'est pas une obligation. Il va de soit que chaque noeud de ce réseau doit permettre de trouver les noeuds avec lesquels il a un lien.
- connaître le noeud de départ et le noeud d'arrivée.

On utilisera aussi deux listes :
- une liste 'ouverte' : qui contiendra tous les noeuds accessibles depuis le noeud de départ.
- une liste 'fermée' : qui contiendra la liste des tous les noeuds qui ont déjà été étudiés.

Chaque liste contiendra : l'identifiant du noeud, l'identifiant du noeud précédent, un coût.

Le déroulement est très simple :
- En partant du noeud de départ, on identifie les noeuds voisins.
- Pour chaque noeud voisin, on calcule un coût constitué du coût pour atteindre le noeud précédent, plus le coût pour aller du noeud précédent à ce noeud.
- On passe le noeud de départ dans la liste des noeuds 'fermés', et ses noeuds voisins dans la liste des noeuds 'ouverts'.
- Ensuite, dans la liste ouverte, on étudiera le noeud ayant le coût le plus faible . Il faudra aller chercher ses noeuds voisins. Si le noeud voisin est dans la liste 'fermée', il a déjà été étudié et est donc ignoré : le nouveau coût calculé sera forcément au moins égal, voir supérieur.
Sinon, il faudra en calculer le coût associé :
Si le noeud voisin est dans la liste 'ouverte', et que le nouveau coût calculé est inférieur au dernier enregistré, on met à jour la liste avec le nouveau coût, et on change l'identifiant de son noeud précédent pour le noeud étudié.
Si le noeud voisin est dans la liste 'ouverte', mais que le nouveau coût calculé est supérieur au dernier enregistré, on ne change rien.
Si le noeud voisin n'est dans aucune des listes, on le passe dans la liste ouverte.

On arrête la recherche lorsque le noeud de destination est trouvé, il est alors à son tour passé dans la liste 'fermée', ou qu'il n'y a plus de noeud dans la liste ouverte. Dans ce dernier cas, cela signifie qu'il n'y a pas de chemin permettant d'aller du noeud de départ au noeud d'arrivée.

Au final, s'il existe un chemin, on obtient une liste chaînée des différents noeuds à parcourir.

L'A star permet de toujours trouver le chemin le plus court en terme de coûts.

2- Calcul des coûts

Le coût pour passer d'un noeud à un autre n'est pas forcément une constante unique à tous les noeuds : il pourra varier en fonction de différents critères.
Dans un RTS, s'agissant de parcourir une carte, on trouvera généralement une variation du coût en fonction du terrain à parcourir, de la météo, de la nature de l'unité,.... Par ailleurs, il peut aussi être pertinent de tenir compte de facteurs comme la dangerosité de certaines zones ou leur éloignement.

3- Optimisation de la recherche

3.1 Heuristique et A star

A la base, nous avons vu que la liste ouverte se parcourait dans l'ordre croissant des coûts. Le but va être de prendre en compte d'autres critères que le simple coût du chemin parcouru pour choisir la séquence des noeuds à étudier dans la liste 'ouverte', afin de privilégier un chemin 'probablement' plus court.

Il faudra toutefois être particulièrement attentif au fonctionnement de la liste fermée : ne doivent se trouver dans cette liste que les noeuds dont le coût est définitivement acquis. Dans le cas contraire, il faudrait non seulement mettre à jour ce noeud, mais aussi recalculer tous les coûts de tous les noeuds dont le chemin passerait par un noeud ayant fait l'objet d'une réévaluation de son coût suite à ce simple changement.

Outre ce point, il y a de fortes probabilités pour qu'une heuristique mise en place sur un algorithme comme le A star ne fournisse plus systématiquement le chemin le plus court, mais un chemin parmi d'autres.

3.2 Maillage

Un des inconvénients de A star est que sur des réseaux de grandes tailles, et plus particulièrement des cartes, son temps d'exécution va augmenter de façon disproportionnée.

Une autre méthode pour optimiser la recherche, s'appliquant plus particulièrement à la recherche de chemin sur une carte, consiste donc à calculer à l'avance les coût relatifs à des points particuliers de la carte.
L'algorithme sera alors utilisé trois fois successivement : une première fois pour estimer le trajet du point de départ vers un premier noeud particulier, une deuxième pour aller du point de destination vers un second point particulier, et une troisième fois pour rejoindre les deux points particuliers.

Ci dessous, en jaune, la zone approximativement étudiée avec le A star standard : on remarque que la recherche couvre une grande partie de la carte, et que le chemin trouvé est très optimisé.


A l'opposé, avec le maillage, la surface de recherche est beaucoup plus réduite. D'autre part, le maillage permet d'élargir un peu le chemin trouvé si le besoin s'en fait sentir.


Là encore, il faut savoir adapter en fonction de ses besoins.

3.3 Perfection et réalité

Comme indiqué, l'A star permet de toujours trouver le chemin le plus court en terme de coût. Or, dans la réalité, lorsque l'on cherche son chemin, on ne trouve que très rarement le parcourt optimal au premier essai : ainsi conçu, cet algorithme ne permet d'avoir cette sensation d'hésitation dans la recherche.

Il peut donc être intéressant, par exemple, de diviser la recherche en plusieurs étapes successives en fonction de l'éloignement du point d'arrivée ou de la vision du réseau qu'en a l'objet cherchant son chemin. Une illustration simple de cette problématique est la gestion d'un brouillard de guerre : il parait inconcevable de rester sur une solution où une unité irait directement au but dans une zone non découverte, en évitant des troupes ennemies qu'elle ne voit pas et en contournant des obstacles invisibles.