Intelligence artificielle pathfinding – Astar

L’algorythme Astar: une solution? Dans l’article Intelligence Artificielle – Crash and Turn, j’ai abordé une problématique courante dans le domaine du jeu vidéo. La poursuite d’un joueur par un adversaire dirigé par l’intelligence artificielle. Cette solution un peu brutale n’est pas la plus optimisée ni la plus probante. Je vous montre comment à l’aide de l’algorithme A star, il est possible de le faire plus efficacement. Tout ça en javascript.

L’algorithme A star, c’est quoi ?

A star est un algorithme de recherche de chemin dans un graphe qui date de 1968. Un graphe qui est un ensemble de nœuds dont certains sont reliés entre eux trouve son emploi dans de multiples domaines. Dans le cas présent la recherche de chemins entre 2 nœuds.

A star a l’excellence de trouver une solution quand il y en a une, ceci rapidement. Son emploi s’en trouve donc un bon choix dans le cadre du jeu vidéo. Cependant, la solution trouvée ne sera pas toujours la meilleure.

L’algorithme de Dijkstra qui lui date de 1959 dont est dérivé A star, est quant à lui un algorithme de recherche du plus court chemin. Il est plus consommateur en ressources et en temps.

L’environnement d’expérimentation de l’algorithme A star

Pour cette démonstration, je vous invite à reprendre quelques éléments issus de l’article Intelligence Artificielle – Crash and Turn, notamment tout ce qui est connexe au labyrinthe et son affichage. J’ai regroupé toutes ces fonctions dans un fichier nommé display.js.

Je rappelle la liste des fonctions que vous retrouverez dans l’article Intelligence Artificielle – Crash and Turn .
– createCanvasContext crée un canvas pour gérer l’affichage du labyrinthe;
– clearCanvas efface un canvas;
– initGameGrid initialise le labyrinthe en une structure de données, affiche le labyrinthe avec les 2 protagonistes poursuivant et poursuivi;
– showSquare affiche un carré à une position et une couleur données dans le labyrinthe;
– showPlayer affiche le poursuivi (la fin du chemin);
– showEnemy affiche le poursuivant;
– showWall affiche un mur;
– displayWall affiche tous les murs.

Que faire avec l’algorithme A star ?

A star permet de déterminer un chemin entre 2 points A et B, qu’il y ait des obstacles ou pas. Pour aller de A vers B, il faut passer par une série de points intermédiaires. C’est A star qui se charge de trouver la liste des points entre A et B, en faisant en sorte que le chemin soit le plus court possible. On appelle A et B ainsi que les points intermédiaires des nœuds.

C’est un algorithme très prisé dans le domaine du jeu vidéo.

Les nœuds

Le chemin solution commence à un nœud A. Le point A, lieu où commence le chemin, là où est le poursuivant. Se termine à un nœud B. Le point B, lieu où se termine le chemin, là où se trouve le poursuivi. Il est une liste des nœuds par lesquels il faut passer pour aller de A vers B, A est le point (nœud) départ et B est le point (nœud) d’arrivée. Pour le présent exercice, en dehors des murs, des points de départ et d’arrivée, tous les lieux de passage possible (tous les autres points du labyrinthe) sont des nœuds.

Deux piliers constituent l’algorithme A star.
– une liste de nœuds dite ouverte;
– une liste de nœuds dite fermée.

La liste ouverte comporte tous les nœuds candidats pouvant appartenir au chemin solution. Cette liste se remplit au fur et à mesure de l’exploration du labyrinthe.
Lorsqu’un nœud de la liste ouverte est considéré comme faisant partie du chemin à l’instant où il est examiné, il est basculé dans la liste fermée.

La liste fermée comporte tous les nœuds qui à un moment ou un autre ont fait partie de la solution. Un nœud se trouve donc dans la liste ouverte ou la liste fermée, jamais les 2 à la fois.
Une fois qu’un nœud a basculé dans la liste fermée, il n’en ressort pas, il y reste.

Evaluation de la qualité d’un nœud

Pour évaluer la qualité d’un nœud, on utilise la somme de:
– la distance entre lui et le dernier nœud du chemin, le point d’arrivée;
– et la distance entre lui et leur dernier considéré comme valide pour le chemin.

Il y a plusieurs façons de faire, plus ou moins exactes, pour calculer ces distances, entre autres :
– la distance à vol d’oiseau appelé aussi la distance euclidienne calculée sur la base du théorème de Pythagore;
– la distance de manhattan appelée aussi taxi-distance (la distance entre deux points parcourue par un taxi lorsqu’il se déplace dans une ville américaine où les rues sont agencées selon un réseau ou quadrillage).

Illustration avec en vert la distance euclidienne, en bleu, rouge ou jaune la distance de manhattan.

Plus le calcul sera précis, meilleur sera le chemin trouvé. Alors pourquoi choisir la distance de manhattan ?
La distance euclidienne fait appel à des nombres à virgule flottante. Cela rend le temps de calcul plus long qu’avec la distance de manhattan qui n’utilise que des nombres entiers.

A l’échelle de cet exercice, la différence est imperceptible. Mais sur des parcours plus longs avec des calculs plus nombreux, cela peut devenir critique en temps d’exécution rendant le calcul par la distance de manhattan plus pertinent.

L’algorithme A* (A Star), comment ça marche ?

Comme dit précédemment, notre environnement est composé :
– d’une position de départ (qui est un nœud);
– d’une position d’arrivée (qui est aussi un nœud);
– du labyrinthe avec ses obstacles (composé aussi de noeuds).

Pour l’algorithme, nous utilisons,
– une liste ouverte vide;
– une liste fermée vide;
– une fonction d’évaluation de la qualité d’un nœud.

Un nœud est déterminé par :
– sa position dans le labyrinthe exprimée avec l’abscisse et l’ordonnée, et prend pour origine le point en haut à gauche du labyrinthe;
– son nœud parent;
– sa qualité.

L’algorithme commence à partir de la position/nœud de départ, qu’il place d’emblée dans la liste fermée et à partir duquel sont déterminés les points/nœuds adjacents.

Ici, l’exploration se fait à la verticale et l’horizontale, mais rien n’interdit de le faire aussi sur les diagonales. Quatre nœuds possibles, dont les coordonnées sont respectivement :
– 1er nœud à droite : même ordonnée que le point de départ, abscisse + 1;
– 2ème nœud au dessus : même abscisse que le point de départ, ordonnée – 1;
– 3ème nœud à gauche : même ordonnée que le point de départ, abscisse – 1;
– 4ème nœud en dessous : même abscisse que le point de départ, ordonnée + 1.

Ensuite, vient l’analyse de chacun des 4 nœuds.
– s’il est un obstacle, il est oublié;
– s’il appartient à la liste fermée, cela indique qu’il a déjà été analysé, il est oublié.

En dehors des 2 cas précédents.
– si le nœud examiné n’est pas dans la liste ouverte, on calcule sa qualité et on l’insère dans la liste;
– si le nœud examiné est dans la liste ouverte, on calcule sa qualité, on la compare à la qualité du même nœud de la liste : si la qualité du nœud de la liste est moindre, il est remplacé par le nœud examiné.

On parcourt ensuite la liste ouverte pour en extraire le nœud ayant la meilleure qualité et le mettre dans la liste fermée.
Si la liste ouverte est vide, il n’y a pas de chemin solution.

Si ce nœud correspond au nœud du point d’arrivée, le chemin solution est trouvé. Il suffit de remonter de ce nœud jusqu’au nœud de départ par le biais des nœuds parents. L’algorithme s’arrête là.
Sinon ce même nœud devient le nœud à partir duquel on reprend l’exploration à l’étape où sont déterminés les nœuds voisins à la verticale et à l’horizontale qui seront analysés à leur tour.

L’algorithme A* (A Star) en javascript

Quelques fonctions utilitaires relatives à l’affichage ont été créées et placées dans un fichier dédié display.js. Nous ajoutons un objet utilitaire que nous appelons utils et que nous définissons aussi dans un fichier dédié util.js.

Cet objet comporte 3 méthodes.
– la première appelée equalJsonByValue qui compare 2 objets json;
– la deuxième appelée isJsonByValueInList indique en renvoyant un booléen si une structure de données se trouve dans une liste;
– la troisième appelée getNodeFromList renvoie depuis une liste et un nœud passés en paramètres, un nœud de la liste dont les données ont en partie des valeurs identiques. Seules les données relatives au parent et à la qualité diffèrent.

Cette dernière méthode est appelée lorsqu’un nœud analysé est déjà dans la liste ouverte. Elle permet de récupérer le nœud avec ses données (notamment sa qualité) en vu de le comparer au nœud analysé.

Il ne reste plus qu’à implémenter la classe Astar en javascript afin de mettre en harmonie tout cela et vous aider à trouver le chemin solution. A suivre dans la deuxième partie.