Le pathfinding avec A*

L'IA prend de nos jours une place de plus en plus importante dans nos jeux. Le nombre de programmeurs se consacrant à l'IA dans les jeux commerciaux a grandement augmenté, tout comme la part d'occupation du CPU dédiée à l'IA. Eh oui, l'IA ça consomme et comme nous allons le voir, certains algorithmes sont plus rapides que d'autres, ce qui est très profitable. Le premier algorithme qui vient à l'esprit lorsqu'on se demande comment aller d'un point à un autre, c'est d'y aller à la "bourrin". Sans entrer dans les détails, ce genre d'algorithme explore tout le graphe (c'est comme ça qu'on appellera le "monde") et repère le temps minimum nécessaire pour aller à chaque node (c'est comme ça que nous appellerons les cases) du graphe.
Tout cela peut paraître un peu compliqué, sachez seulement que :

• la méthode dite récursive est simple, mais TRÈS lente ;
• le "monde" à explorer s'appelle un graphe et c'est un ensemble de nodes interconnectés. Les nodes peuvent être des cases (triangles, carrés, hexagones, ...) ou simplement des points reliés les uns aux autres.

Il faut savoir qu'il y a quelques petites choses extrêmement difficiles à implémenter dans le pathfinding, les jeux commerciaux le font mais ils gardent leurs petites techniques bien secrètes. Ce sont le déplacement de groupes d'unités, par exemple.

L'algorithme A* (prononcez "A star") est fait pour la performance. Il trouvera en général la solution (c'est-à-dire le chemin le plus court) plus vite qu'un autre algorithme (par exemple Djikstra) mais il se peut que si le graphe est étrange (un labyrinthe par exemple où vous devez souvent vous éloigner de l'objectif pour mieux l'atteindre ensuite) il aille moins vite que d'autres.
Avant de nous attarder précisément sur le fonctionnement de cet algorithme, nous devons définir quelques petites choses.

Le graphe et les nodes

Vous vous souvenez que j'ai parlé de graphes et de nodes ? Eh bien voici un exemple en image sur lequel nous allons travailler :


Expliquons maintenant ce graphe : les cases sont des nodes qui sont reliés aux cases adjacentes. Notez qu'on aurait très bien pu interdire le déplacement en diagonale. La case verte est le node de départ et la rouge la case d'arrivée. Les cases bleues représentent un obstacle, ce ne sont pas des nodes, la case à droite de la verte n'a donc que 5 liaisons.

Analyse en détail du fonctionnement d'A*

Nous allons reconstituer pas à pas le fonctionnement de l'algorithme A*. Chacune des notions sera décortiquée à l'aide de schémas, ne vous inquiétez pas.

Début de la recherche de A*

Comme première action, l'algorithme A* ajoute la case de départ à la liste ouverte.
Liste ouverte : Késaco ?
Il y a deux listes utilisées par A*. Ces listes contiennent des nodes (ici, des cases). Les deux listes sont :

• La liste ouverte, elle contient les nodes à analyser.
• La liste fermée, elle contient les nodes déjà analysés.

Comme je vous l'ai dit, chaque liste contient des nodes mais contient aussi des informations sur ce node. Nous allons voir prochainement à quoi servent ces informations.
L'algorithme A* commence par étudier la case de départ puisqu'elle est la seule dans la liste ouverte. Il ajoute à la liste ouverte toute les cases adjacentes en indiquant leur parent et leur poids. Cette phrase contient de nombreux mots-clés.
Premièrement, leur parent, c'est la case de départ. Cette notion de parent est très importante car c'est elle qui va nous permettre de retrouver le chemin à partir de la case d'arrivée.
Deuxièmement, le poids. On le note F. Il est la somme de la distance parcourue pour arriver à ce point depuis le point A (G) et de celle à "vol d'oiseau" restant jusqu'au point B (H). Nous utiliserons pour les distances 10 pour celle d'une case à une autre en ligne droite, 14 en diagonale. Pour la distance à vol d'oiseau, nous utiliserons la distance de Manhattan. Cette distance correspond à la distance entre deux points en abscisse plus celle en ordonnée.
Ensuite, on enlève la case de départ de la liste ouverte pour la mettre dans la liste fermée.
Voyons maintenant ce que ça donne.



Les petits traits sur chaque case montrent leur case parent. Les cases cerclées de vert sont dans la liste ouverte. La case de départ est cerclée de bleu cyan car elle est dans la liste fermée.

La boucle de recherche

Premièrement, nous allons chercher une case à étudier dans la liste ouverte. Mais laquelle ? Il y en a 8 ! Nous allons prendre celle qui a le poids F le plus faible, c'est-à-dire celle qui est à droite de la case de départ.
Nous retirons cette case de la liste ouverte pour la mettre dans la liste fermée.
Nous analysons maintenant les cases adjacentes.

• Si elles sont occupées par des obstacles, nous les ignorons (comme les 3 cases du mur bleu).
• Si elles sont dans la liste fermée, nous les ignorons aussi.
• Si elles sont dans la liste ouverte, nous recalculons G et regardons s'il est inférieur : si oui, nous remplaçons son ancien parent par la case que nous étudions.
• Si la case n'est dans aucune liste, nous l'ajoutons à la liste ouverte et nous calculons F, G et H et indiquons la case que nous étudions comme parent.

Nous ignorons donc la case de départ et les cases bleues. En recalculant la valeur des autres cases, nous nous apercevons que G est supérieur à sa valeur actuelle (ce qui est normal, puisqu'en passant par la case à droite de celle d'arrivée, c'est plus long qu'en y allant directement) : donc, nous ne touchons à rien.
Voilà : c'est fini pour ce tour de boucle, on passe au suivant avec un petit schéma tout de même.



On voit que la case qu'on a étudiée est passée dans la liste fermée.
NOUVEAU TOUR DE BOUCLE !
Choisissons la case de la liste ouverte ayant le F le plus bas.
Et là se pose un problème... comment choisir la case à étudier puisqu'on en a deux qui ont un F de 54, le plus bas. Ce n'est pas vraiment un problème, on peut prendre celle que l'on veut.
Et on recommence ce que l'on a déjà fait.
Après quelques tour de boucles, on arrive à quelque chose comme ça :



Et lorsque nous commençons à analyser la case d'arrivée, A* se rend compte qu'il a réussi. Il stoppe alors la boucle.

Fin de l'algorithme

Pour finir, nous devons remonter le chemin à partir de la case d'arrivée et ce, grâce aux informations sur les parents. Cela donne quelque chose comme ça :



Et nous avons fini !

Ce n'est pas tout ça, mais le but n'est pas de le faire de tête mais de le faire faire par le PC. Je ne peux pas actuellement vous donner un programme de mon propre cru, pour la simple et bonne raison que je n'en ai pas fait par manque de temps. Par contre, vous pouvez en trouver à la pelle sur le net.
Pour vous aider tout de même un peu, je vais vous résumer l'algorithme.

Code : Autre

Je vais ici vous donner quelques petites choses à faire si vous voulez de nouveaux challenges !

• Utiliser les hauteurs des différents points afin de calculer G de manière plus réaliste : si deux points sont très éloignés en hauteur, ça sera plus long que s'ils sont au même niveau. Ainsi, le chemin pourra contourner l'Himalaya, par exemple.
• Faire en sorte qu'un endroit soit inconnu (comme quand c'est noir dans les RTS) ; pour ça, il faut faire comme si toutes les cases de la région inconnue étaient libres de tout obstacle. Le chemin ira donc dans le mur jusqu'à ce que la carte soit dévoilée.

Voilà : vous avez de quoi faire, maintenant !