Voici l'article qui m'a fait comprendre le pathfinding ! 
Je l'ai traduit en français afin que le plus grand nombre puisse en
profiter. L'auteur se nomme Patrick Lester et l'article original se situe à
l'adresse suivante : http://www.policyalmanac.org/games/aStarTutorial.htm
Pathfinding A* pour les débutants
Alors qu'il est relativement facile à utiliser une fois que l'on a pris le
coup, l'algorithme A* (prononcer "A star") peut être difficle à aborder pour
des débutants. Il existe beaucoup d'articles sur le web qui expliquent A*, mais
la plupart sont destinés à ceux qui en comprennent dejà les bases. Celui-ci est
destiné aux vrais débutants du pathfinding.
Cet article n'est pas spécifique à un langage donc vous devrier facilement
pouvoir l'adapter a n'importe quel langage de programmation.
Introduction : la zone de
recherche.
Considérons que quelqu'un veut aller d'un point A à un opint
B. Considérons également qu'un mur est situé entre ces deux points. Cette
situation est illustrée par l'image ci-contre, où le point A (départ) est
affiché en vert, le point B (arrivée) est en rouge, et où les cases en bleu
représentent le mur.
La première chose que vous remarquerez est que la zone de recherche est
divisée en cases. Simplifier la zone de recherche, comme nous l'avons fait ici,
est la première étape en pathfinding. Cette méthode particulière réduit notre
zone de recherche à un simple tableau a deux dimensions. Chaque élément du
tableau représente une case de notre grille, est son statut est notifié comme
étant "traversable" ou "non traversable". Le chemin va être la succession de
cases à parcourir pour passer de la case A à la case B. Une fois le chemin
trouvé, notre personnage va passer du centre d'une case au centre de la
prochaine case, jusqu'à ce qu'il atteigne sa cible.
Ces points au centre de chaque case sont appelés "noeuds" (nodes). Quand
vous lisez un texte traitant du pathfinding, vous retrouverez souvent ce terme
de noeuds. Pourquoi ne pas appeler ca simplement une case ? Tout simplement
parce qu'il est possible de diviser une zone de recherche en autre chose qu'une
case "carrée". Cela peut-être une forme rectangulaire, ou hexagonale, ou en
fait n'importe quelle forme. Ces noeuds peuvent égelement être placés n'importe
ou sur les formes - au centre ou sur les contours, ou n'importe où ailleurs.
Nous utilisons ici ce système tout simplement parce que c'est le plus simple
...
Commencer la recherche
Une fois la zone de recherche simplifiée à un nombre de noeuds facilement
gérable, comme nous l'avons fait avec la grille ci-dessus, la prochaine étape
consiste à effectuer la recherche pour trouver le chemin le plus court. En
pathfinding A*, on commence cette recherche par le point A, puis en vérifiant
les cases adjacentes, et en général en cherchant encore à l'extérieur jusqu'à
ce que la cible soit trouvée.
Nous commencons notre recherche de la manière suivante :
Commencons au point de départ et ajoutons le a une "liste ouverte" (open
list) de cases à étudier. La liste ouverte est une sorte de "shopping list".
Pour l'instant, nous n'avons qu'un seul point à l'intérieur (le point A), mais
il y en aura bientôt plus. Elle contient une liste de cases qui pourraient
éventuellement faire partie de notre chemin, mais pas forcément. En fait, c'est
une liste de pionts que nous devrons vérifier. Regardez maintenant toutes les
cases ateignables (ou "traversables") adjacentes au point de départ, en
ignorant les cases avec les murs, ou de l'eau, ou toute case qu'on ne peut pas
traverser. Ajoutez les a la liste ouverte également. Pour chacune de ces cases,
enregistrez la case A comme son étant son "parent". Cette notion de "parent"
est trés importante ensuite pour pouvoir retracer le chemin. Une explication
vous est donnée plus loin.
Supprimez maintenant le point A de la "liste ouverte", et ajoutez le à une
"liste fermée" (closed list), qui va contenir les points que nous n'aurons plus
besoin de vérifier.
A cette
étape, vous devriez avoir quelquechose comme l'image ci-contre. Sur ce schéma,
la carré vert foncé au centre est notre case de départ. Elle est entourée de
bleu clair pour signifier que la case a bien été ajoutée à notre "liste
fermée". Toutes les cases adjacentes sont maintenant dans la "liste ouverte" de
case à vérifier, et sont entourées de vert clair. Chacune d'elle possède une
"pointeur" vers son parent, qui n'est autre que la case de départ.
Ensuite, choisissons une case de la "liste ouvert", et répétons plus ou
moins le raisonnement précédent. Mais quelle case choisir ? Celle avec le coût
F le plus bas.
Cout d'un chemin.
La clé servant à déterminer quelle case utiliser parmi celles contenues dans
la "liste ouverte" est l'équation suivante :
F = G + H
avec
- G est le coût de mouvement pour aller de la case A à une case donnée sur la
grille, en suivant le chemin généré jusqu'ici.
- H est le coût de mouvement pour aller d'une case donnée sur la grille
jusqu'au point de destination, le point B. Il est souvent appelé "heuristique",
ce qui peut-être troublant. La raison pour laquelle on le nomme ainsi est que
ce coût est estimé. En effet, nous ne connaissons pas vraiment la distance
qu'il nous reste à parcourir, car toute sortes d'obstacles peuvent se trouver
sur le parcours (mur, eau, etc..). Un moyen de calculer ce coût est donné dans
ce tutoriel, mais il en existe d'autres que vous pourrez trouver dans d'autres
articles sur le net.
Notre chemin est généré récursivement en parcourant notre "liste ouverte" et
en y choisissant le case ayant le coût F le plus faible. Ce raisonnement sera
abordé un peu plus loin dans cet article, mais regardons d'abord
commentutiliser l'équation que nous venons de voir.
Comme décris précédemment, G est le coût de mouvement du point de départ
jusqu'à la case donnée en parcourant le chamin généré jusque là. Dans cet
exemple, nous allons assigner un coût de 10 pour chaque déplacement horizontal
ou vertical, et un coût de 14 pour un mouvement en diagonale. Nous utilisons
ces données car la distance nécessaire pour se déplacer est la racine carrée de
2 (ne prenez par peur, restez la ! ;)), ou approximativement 1.414 fois le coût
d'un déplacement vertical ou horizontal. Nous utiliserons 10 et 14 pour des
raisons évidentes de simplification. Le rapport est à peu prés correct, et nous
évitons ainsi les calculs de racines carrées et le nombres à virgule. Mais cela
n'est pas seulement pour que nous n'aimons pas les maths : utiliser des nombres
entiers est aussi bien plus rapide pour l'ordinateur également. Comme vous
allez bientôt le constater, le pathfinding peut être trés lent si vous
n'utilisez pas ce genre d'astuces.
Etant donné que nous calculont le coût G le long d'un chemin donné, le moyen
de trouver ce coût est de prendre le coût G de son parent, et de lui ajouter 10
ou 14 selon qu'il soit situé en diagonale ou pas par rapport à son parent.
L'interêt de cette méthode deviendra plus clair lorsque nous serons plus loin
qu'à une case du point de départ.
Le coût H peut être estimé d'un grand nombre de facons. La méthode que nous
utiliserons ici est nommée la méthode "Manhattan", avec laquelle vous calculez
le nombre de cases verticales et horizontales pour parvenir au point d'arrivée
(en ignorant les mouvements en diagonale). Nous multiplions alors ce total par
10. Cette méthode s'appelle "Manhattan" parce qu'elle revient à calculer le
nombre de patés de maisons d'un endroit à un autre, sans couper à travers un
bloc en diagonale.
En lisant ceci, il est courant de penser que l'heuristique est simplement
une estimation de la distance restant à parcourir à vol d'oiseau. Or, ce n'est
pas le cas. Nous essayons en fait de calculer la distance restant à parcourir
via le chemin à trouver (qui est généralement plus long). Plus cette estimation
est proche, plus l'algorithme trouvera le chemin facilement (et rapidement). Si
le chemin estimé est sur-évalué, il n'est pas certain de trouver le chemin
optimal. Dans ce cas, l'heuristique est dite "inadmissible".
Techniquement, dans cet exemple, la méthode "Manhatan" est inadmissible, car
elle surévalue quelque peu la distance restante. Mais nous l'utiliserons
quand-même, car elle est la plus facile à comprendre dans ce cas là, et qu'il
s'agit d'une surestimation assez légère. Dans les rares cas où le chemin trouvé
n'est pas le plus court, il n'en sera pas trés éloigné. Si vous voulez en
savoir plus, rendez vous ici.
Le coût F est
calculé en ajoutant G et H. Vous pouvez constater le résultat sur le schéma
ci-contre. Les coûts F, G et H sont notés dans chaque case. Comme indiqué, F
est situé en haut à gauche, G en bas à gauche et H en bas à droite.
Jetons maintenant un coup d'oeil à ces cases. Dans celle qui contient les
lettres, nous avons G=10. C'est parce qu'elle est située à une case du point de
départ, dans une direction horizontale. Les cases en dessous et au dessus de la
case de départ, ainsi que celle située à sa gauche ont toutes le même coût de
10. Les cases en diagonales ont un coût de 14.
Les coûts H sont calculés en estimant la distance "Manhattan" jusqu'à la
case d'arrivée, en se déplacant horizontallement et verticalement, et en
ignorant le mur qui est sur le chemin. Avec cette méthode, la case située juste
à droite du départ est à trois déplacement horizontaux de l'arrivée, soit un
coût H de 30. La case située juste en dessous est à quatre cases de l'arrivée
(souvenez-vous, on se déplace uniquement horizontalement et verticalement) pour
un coût H de 40. Vous constaterez facilement le calcul des coûts H des autres
cases.
Le coût F de chaque case est calculé par une simple addition de G et H.
Continuer la recherche
Pour continuer la recherche, nous choisissone tout simplement la case ayant
le coût F le plus faible parmi les case de la "liste ouverte". Puis, avec cette
case nous faisons le processus suivant :
- Nous la supprimons de la "liste ouverte" et la rajoutons à la "liste
fermée"
- Nous vérifions toutes ses cases adjacentes, en ignorant celles qui font
partie de la "list fermée", ainsi que celle qu'on ne peut pas traverser, que
nous ajoutons à la "liste ouverte" si elles n'y sont pas déjà. Assignez la case
en cours comme étant le "parent" des cases nouvellement ajoutées.
- Si une des cases adjacentes est déjà dans la "liste ouverte", vérifiez si
le chemin pour y arriver n'est pas meilleur. En d'autres termes, vérifiez si le
coût G de cette case est inférieure si nous utilisons la case en cours pour y
parvenir. Si ce n'est pas le cas, ne changez rien.
D'un autre côté, si le coût G du nouveau chemin est inférieur, faites que la
case en cours soit le nouveau parent de cette case adjacente (dans le schéma
précédent, chagez la direction du pointeur pour pointer vers la case en cours).
Pour finir, re-calculez les coût F et G de cette case. Cela semble assez
confus, mais vous le verrez illustré graphiquement ci-dessous.
Bon, voyons
maintenant comment cela fonctionne. Sur nos 9 cases initiales, nous en avons 8
qui font partie de la "liste ouverte" aprés que la case de départ ait été
envoyée vers la "liste fermée". De ces 8 cases, celle ayant le coût F le plus
faible est celle qui se situe immédiatement à droite de la case de départ, avec
un coût F de 40. Donc, nous choisissons cette case comme étant la prochaine.
Elle est entourée en bleu dans l'illustration ci-contre.
Tout d'abord, nous supprimons cette case de la "liste ouverte" pour
l'envoyer dans la "liste fermée" (c'est pourquoi elle est maintenant entourée
en bleu). Puis, nous vérifions ses cases adjacentes. Celle qui est
immédiatement à droite est un mur, donc nous l'ignorons. Celle immédiatement à
gauche est la case de départ. Comme elle fait partie de la "liste fermée", on
l'ignore également.
Les quatre autres cases sont deja dans la "liste ouverte", donc nous devons
vérifier si les chemins qui y vont sont meilleurs en passant par notre case en
cour, en utilisant le coût G comme point de comparaison. Regardons la case
située juste en dessous de notre case actuelle. Son coût G est de 14. Si nous y
allions en passant par notre case en cours, le coût serait de 20 (10 de coût G
de la case, plus 10 de déplacement vertical depuis la case en cours). Un coût G
de 20 est supérieur à 14, donc le chemin en cours n'est pas meilleur. Il suffit
de regarder le schéma pour que cela saute aux yeux : il est plus direct d'eller
sur cette case depuis le départ en se déplacant en diagonale, plutôt qu'en se
déplacant d'abord horizontalement d'une case puis verticalement d'une case.
Lorsque nous répétons ce processus pour les quatre cases adjacentes deja
dans la "liste ouverte", nous nous rendons compte qu'aucun chemin n'est
amélioré en passant par la case en cours, donc nous ne changeons rien.
Maintenant que nous avons traité toutes les cases adjacentes, nous en avons
fini avec la case en cours, et nous sommes prêts à passer à la suivante.
Donc nous parcourons a nouveau notre "liste ouverte", qui est maintenant
composée de 7 cases, et nous prenons celle qui a le coût F le plus faible. Il
est interessant de constater que dans ce cas, il y a deux cases avec un coût de
54. Dans ce cas, laquelle choisir ? En fait, cela a peu d'importance. Pour des
raisons d'optimisation, il peut être plus rapide de choisir le dernier que vous
avez ajouté à la "liste ouverte". Cela oriente la recherche en faveur des cases
qui sont trouvées le plus tard au cours de la recherche, quand vous êtes
arrivés plus prés de votre destination. Mais cela n'a réellement pas
d'importance (différentes approches de cette notion peuvent faire que deux
algorithmes A* peuvent trouver des chemins différents de longueurs égales).
Choisissons
la case située juste en dessous et à droite de la case de départ, comme
illustré dans le schéma ci-contre.
Cette fois-ci, quand nous vérifions les cases adjacentes, nous voyons que
celle située immédiatement à droite est un mur, donc nous l'ignorons. Nous
faisons la même constatation pour celle située juste au dessus. Nous ignorerons
également celle qui est située en dessous du mur. Pourquoi ? Parce que vous ne
pouvez pas vous y rendre directement depuis la case en cours sans passer au
dessus du coin du mur. Vous avez en fait besoin d'aller vers le bas d'abord,
pour ensuite vous rendre sur cette case (Note : cette règle est optionnelle.
Elle dépend en fait de l'endroit ou sont situés les "noeuds").
Ceci nous laisse cing autres cases. Les deux cases situées en dessous de la
case en cours ne sont pas encore dans la "liste ouverte", donc nous les
ajoutons avec la case en cours comme parent. En ce qui concerne les trois
autres cases, deux sont deja dans la "liste fermée" (la case de départ et celle
située à sa droite, toutes les deux entourées en bleu sur le schéma), donc nous
les ignorons. Et la dernière case, immédiatement à gauche de la case en cours,
est vérifiée pour voir si le coût G est inférieur en passant par la case en
cours. Ce n'est pas le cas, donc nous pouvons vérifier la case suivante dans
notre "liste ouverte".
Nous allons
répeter ce processus jusqu'à ce que la case d'arrivée soit ajoutée à la "liste
fermée", ce qui nous donne quelque chose comme le schéma ci-contre.
Vous contaterez que le parent de la case située deux cases en dessous du
départ a changé par rapport au précédent schéma. Avant, elle avait un coût G de
28, et pointait vers la case situé en haut à droite. Maintenant elle a un score
de 20 et pointe vers la case juste au dessus d'elle. Ceci est arrivé quelque
part au long de notre recherche, alors que le coût G a été vérifié et modifié
pour être plus faible en utilisant un autre chemin - donc le parent a été
changé, et les coûts F et G recalculés. Bien que ce changement paraisse anodin
ici, il existe beaucoup de situations ou cette vérification constante va faire
la différence pour déterminer le meilleur chemin jusqu'à votre destination.
Maintenant, comment déterminer le chemin lui-même ? Tout simplement en
partant de la case d'arrivée, et en remontant le chemin en sens inverse d'une
case à sa case parent, en suivant les flèches. Cela va vous ramener à votre
chemin de départ, et voila votre chemin ! Cela devrait ressembler à
l'illustration ci-contre. Se déplacer du point A ou point B consiste maintenant
à vous déplacer du centre d'une case au centre de la prochaine case de votre
chemin, jusqu'à ce que vous atteignez votre destination. Simple non ?!?
Récapitulatif de la méthode
A*
Maintenant que nous avons effectué la totalité de nos explications, faisons
un petit récapitulatif étape par étape :
- Ajouter le point de départ à la "liste ouverte"
- Répéter les instructions suivantes :
- Cherche la case ayant le coût F le plus faible dans la "liste ouverte".
Elle devient la case en cours.
- Passer la case en cours de la "liste ouverte" à la "liste fermée"
- Pour les 8 case adjacentes à la case en cours
- Si on ne peut pas la traverser, on l'ignore.
- Si elle n'est pas dans la "liste ouverte", on l'y ajoute. La case en cours
devient le parent de cette case. On calcule les coûts F, G et H de cette
case.
- Si elle est déjà dans la "liste ouverte", on teste si le chemin passant par
la case en cours est meilleur en comparant les coûts G. Un coût G inférieur
signifie un meilleur chemin. Si c'est le cas, on change le parent de la case
pour devenir la case en cours, en on recalcule les coûts F et G. Si vous
conservez une "liste ouverte" triée par coût F, la liste doit être retriée à ce
moment la.
- On s'arrête quand
- La case de destination est ajoutée à la "liste fermée"
- Vous ne trouvez pas la case de destination et la "liste ouverte" est
vide.
- Enregistrez le chemin. En partant de la case de destination, remontez d'un
case à son parent jusqu'à atteindre la case de départ. Vous avez votre chemin !

Petit
apparté
Excusez moi pour ce hors-sujet, mais il est important de noter qu'à de
nombreuses discussions concernant le pathfinding A* sur le web et dans des
forums, vous trouverez parfois certains codes qui sont dit A*, mais ne le sont
pas. Pour utiliser la méthode A*, il faut absolument inclure les notions
abordées précedemment, et plus précisemment la "liste ouverte" et la "liste
fermée", ainsi que le calcul des coûts F, G et H. Il existe beaucoup
d'algorithmes de pathfinding, mais ces autres méthodes ne sont pas A*, qui est
générallement considéré comme étant le meileur de tous. Bryan Stout aborde
beaucoup d'entre eux dans cet article,
incluant leurs avantages et inconvénients. Parfois, une alternative est
mailleure dans certaine circonstances, mais réflechissez à ce dans quoi vous
mettez les pieds!