Voici l'article qui m'a fait comprendre le pathfinding ! :D

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 :

  1. Nous la supprimons de la "liste ouverte" et la rajoutons à la "liste fermée"
  2. 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.
  3. 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 :

  1. Ajouter le point de départ à la "liste ouverte"
  2. Répéter les instructions suivantes :
    1. Cherche la case ayant le coût F le plus faible dans la "liste ouverte". Elle devient la case en cours.
    2. Passer la case en cours de la "liste ouverte" à la "liste fermée"
    3. 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.
    4. 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.
  3. 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 ! :D

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!