Bonjour et bienvenue dans ce tuto qui va vous aider à comprendre et à implémenter l'un des algorithmes de pathfinding les plus connus, j'ai nommé A* ( prononcez “A STAR” ).

Dans une seconde partie nous verrons comment implémenter (coder) cet algorithme en Actionscript 3.

Mais tout d'abord, qu'est-ce que le pathfinding ?

Décortiquons un instant le mot Pathfinding voulez-vous ? Pathfinding est un mot anglais qui peut se décortiquer en deux mots: path et find.

En anglais, le “path” c'est le chemin, la voie. Le mot find, vient du verbe “to find” qui signifie trouver. On peut donc en déduire qu'un pathfinder est un “trouveur de chemin” et que le pathfinding est un domaine de l'informatique qui étudie les différentes façons de trouver un chemin entre un point A et un point B ( si chemin il y a ).

Dans ce domaine, pas mal de choses ont déjà été réalisées, beaucoup de chercheurs et de programmeurs se sont déjà penchés sur la question. Dans le domaine du jeux, l'un des algorithmes de pathfinding le plus implémenté est l'algorithme A*. Ce qui nous amène à notre prochain chapitre…

La encore l'explication est très simple, l'efficacité d'un algorithme ( et ce quel que soit le domaine ) se mesure à l'aide de son rapport qualité/complexité. Que signifient ces mots ?

La qualité de l'algorithme, c'est sa capacité à résoudre plus ou moins correctement le problème qu'on lui pose.

Exemple:

Posons la problématique suivante: Je veux que mon algorithme me permette de calculer une dizaine de nombre premiers, cependant tout ces nombres devront être compris dans un intervalle.

1. Considérons l'algorithme A: Il sait calculer dix nombres premiers mais ne prends pas en compte la notion d'intervalle.
2. Considérons l'algorithme B: Il est identique à l'algorithme A à ceci près que lui prends en compte la notion d'intervalle.

Conclusion: l'algorithme B a un meilleur rapport qualité que l'algorithme A.

La complexité d'un algorithme est la notion la plus compliqué à comprendre ici, c'est pour cela qu'on va la simplifier. En effet, ce tuto est dédié à un algorithme spécifique et non à l'algorithmie en général, que les puristes me pardonnent donc si je “charcute” certaines notions. La complexité d'un algorithme, c'est en gros le nombre de calculs moyens qu'il va devoir réaliser pour arriver au résultat escompté.

Exemple:

1. Considérons l'algorithme A: on considère que sa complexité se situe aux alentours de 100 opérations.
2. Considérons l'algorithme B: Il est identique à l'algorithme A à ceci près que sa complexité est deux fois plus importante.

Conclusion: l'algorithme B a une plus grande complexité que l'algorithme A.

A* est l'un des algorithmes les plus efficaces pour trouver un chemin rapidement, cependant, il se peut que dans des schémas assez complexes, comme un labyrinthe ou il faut faire beaucoup d'allers retours ou s'éloigner souvent de son objectif pour mieux l'atteindre, il peut ne pas retourner le chemin le plus court ou être un peu moins rapide que d'autres.

Avant de commencer il est essentiel d'introduire quelques mots de vocabulaires algorithmique notamment:

1. Le graphe: c'est ainsi que l'on va nommer “le monde” que notre algorithme va devoir parcourir pour trouver un chemin d'un point A vers un point B.
2. Un node: c'est une unité du graphe, une “unité du monde”, l'algorithme va parcourir le “graphe” en passant des “nodes”.
3. La liste ouverte: C'est une liste qui contient les nodes à analyser.
4. La liste fermée: C'est une liste qui contient les nodes déjà analysés.

Explication:

Vous pouvez vous représenter le graphe comme une grille et les nodes sont les cases de ce tableau:

Considérons le graphe suivant:

Ce schéma représentera notre monde, notre “graphe”.

Avant de commencer à décrire en détail l'algorithme A* nous allons introduire quelques petites choses:

Chaque node possède plusieurs propriétés qui vont être utiles à l'algorithme: présentons-les !!

1. La propriété parent (P): il s'agit du node qui a permis “d'arriver” au node courant.
2. La propriété G: il s'agit de la distance parcourue depuis le point de départ pour arriver au node courant.
3. La propriété H: il s'agit de la distance à vol d'oiseau entre le node courant et le node d'arrivée.
4. La propriété poids(F): il s'agit de la somme de G et de H.

Comme unité de mesure pour le calcul des propriétés F, G et H nous allons dire qu'un “déplacement” d'un node ( d'une case ) horizontal ou vertical vaut 100 et qu'un déplacement en diagonale vaut 140.

Voici en détail toutes les étapes de l'algorithme:

1. Ajout du node de départ à la liste ouverte.
2. Entrée dans la boucle suivante:
   1. Récupération du node avec le plus petit F contenu dans la liste ouverte. On le nommera CURRENT.
   2. Basculer CURRENT dans la liste fermée.
   3. Pour chacun des 8 nodes adjacents à CURRENT appliquer la méthode suivante:
      • Si le node est un obstacle ou est dans la liste fermée ignorez-le et passer à l'analyse d'un autre node.
      • Si le node n'est pas dans la liste ouverte, ajoutez-le à ladite liste et faites de CURRENT son parent(P). Calculez et enregistrez ses propriétés F, G et H.
      • Si le node est déjà dans la liste ouverte, recalculez son G, s'il est inférieur à l'ancien, faites de CURRENT son parent(P) et recalculez et enregistrez ses propriétés F et H.
      • Stopper la boucle de recherche si vous ajoutez le node d'arrivée à la liste fermée ou si la liste ouverte est vide, dans ce dernier cas, il n'y a pas de chemin possible entre A et B.
3. Prenez le node d'arrivée et reconstruisez le chemin à rebours, càd en bouclant sur les propriétés parentes jusqu'à ce que le parent soit CURRENT.

Voilà, vous disposez dorénavant du savoir théorique nécessaire pour suivre le prochain tuto qui lui vous apprendra à appliquer cet algorithme en AS3. Nous créerons une classe Pathfinder avec une méthode statique “findPath” qui nous retournera le chemin ( ou non ) en fonction d'un graphe donné.

En attendant essayez de comprendre et d'appliquer par vous-mêmes.

Have fun ! Lire la suite