A*

L’algorithme A* (A Star) est un algorithme itératif pour la recherche de chemin auquel on donne une liste d’obstacles , un point de départ et un point d’arrivée. Je l’ai implémenté pour le jeu lostonthepath (vidéo de l’environnement de teste sur http://www.lostonthepath.com/divers.html). Il ne trouve pas forcément le meilleur chemin, mais en trouve toujours un et généralement un bon.

Il est intéressant de constater que l’on peut l’améliorer facilement.

(Pour l’algorithme de base, me suis aidé du tutoriel http://blog.lalex.com/post/2003/09/15/Traduction-%3A-article-sur-le-pathfinding-A

Mon code ici

.

Version de base :

(calcul de distance par delta X + delta Y)

a.png

.

Avec calcul précis :

Calcul de distance par racine de [{ (delta X*delta X) + (delta Y*delta Y)}*10'000]  (*10′000 pour obtenire 100 unité par noeud : ce choix est expliqué par la suite). Calculer des distances avec des racines est souvent déconseillé car cela  nécessite des temps de calcul plus élevé. Une solution est de faire une fonction lancée plusieurs fois (par fonction, j’entends tout le programme), en exécutant un certain nombre d’itérations à chaque fois, et qui retourne à chaque fois son état (pas fini, terminé, pas de solutions).

b.png

.

Avec un flou sur les obstacles :

Voici la plus grosse modification que j’y ai apportée.

Pour plus de réalisme : lors ce que quelqu’un se déplace, il ne se frotte pas contre les murs (en principe). La méthode consiste à inclure le terrain pour calculer la difficulté d’un déplacement. En claire, une zone proche d’un obstacle entrainera un coût G important. Il faut donc éditer une carte contenant la  praticabilité du terrain. Cela consiste à faire une sorte de flou, ce qui entrainera des valeur de difficulté élevée proches des obstacles. Cette opération se fait avant de lacer l’algorithme A*.

02.png

.

Avec un flou + accrochage :

Comportement d’un ennemi qui reste caché le plus longtemps possible contre les objets.

Ici, la valeur du terrain est rendue plus faible proche des obstacles pour inciter le trajet à longer les bords des objets (avec des valeurs quand même plus élevées très proches pour maintenir l’effet de l’image précédente). Il en résulte une sorte d’effet d’aimantation.

A noter que cette fois ci, le trajet fait un long détour vers la gauche. C’est que ce chemin est devenu plus avantageux par rapport à celui passant par la petite forêt d’obstacles.

03.png

.

Un autre trajet, avec les pixels explorés

Ici, les noeuds qui sont dans la liste fermée ou dans la liste ouverte sont remplacés par des points. Cela permet de voire les zones qui ont étés explorées et aussi les chemins qui ont failli être pris.

06.png

.

Le Code :

Ici est décrit la méthode pour faire un flou sur les obstacles.

La technique consiste à obtenir le coût G en multipliant 10 (14 pour les diagonales) par la difficulté de la case (10 par défaut et rendu plus grand par le flou pour les cases proches d’un obstacle).On ne travail pas avec des nombres à virgules flottantes pour plus de rapidité.

Remarque:

Du coup, pour respecter les unités, le coût H (distance à vole d’oiseau entre le nœud en exploration et le nœud d’arrivée) serra de 100 par cases, ce qui a aussi pour conséquence d’augmenter la précisions lors ce que l’on n’utilise pas les nombres en virgules flottante. Et c’est justement pour faire la racine de grands nombres plus rapidement que j’ai développé une méthode par essais successifs.

Cette deuxième méthode (voire au bas de code-flou.c) demandera systématiquement entre 8 et 17 itération pour fournir un résultat alors que la première utilisée teste toutes les valeurs depuis 0 jusqu’à tomber sur la bonne. Donc pour la racine d’un nombre supérieur à 256, la deuxième méthode serra plus avantageuse. Imaginez la racine de 10E8 ou la première nécessitera 10′001 itérations, contre 12 pour la deuxième.

La valeur 1000 correspond à un obstacle.

LISS : rayon pour le lissage (constante)

mem_obstacle : contient une image de obstacle

planque : 0 pour pas d’aimantation 1 à 9 pour effet d’aimantation

code-flou.png

code-flou.c

Voici ma formule (navré, je n’ai pas eu le temps de mettre au propre)

mem_obstacle sert à faire les calculs toujours avec les valeurs d’origine.

.

Marche à suivre :

  • Lors ce qu’on tombe sur un obstacle, on balaie tout les pixels au alentours, et si la distance est plus petite ou égale au rayon (pour ne traiter que  les pixels dans un cercle), on procède au traitement suivant :
  • On inverse la distance (pour obtenir une valeur plus grande proche de l’obstacle).
  • On écrit la valeur calculée que si la valeur est plus grande que la valeur du pixel actuelle (pour éviter qu’une valeur plus faible issue d’un obstacle proche écrase une intensité plus forte précédemment calculée). Pour les valeurs < que la valeur normal du terrain on les écrits si c’est la première fois que le pixel est traîté (cas de l’aimantation) en regardant si mem_obstacle[x][y]  = obstacle[x][y].
  • On évite d’écrire sur un obstacle.

.

La formule mathémagique :

Le cas ou A=0, A+1=1, ce qui correspond à la situation ou l’intensité part de la valeur de base du terrain pour augmenter près des obstacles.

Dans le cas ou A>0, (pour que le trajet tende à suivre les obstacles mais sans les toucher) la valeur commence en dessous de la valeur du terrain (sorte d’offset négatif). Attention, A+1 ne doit jamais dépasser la valeur minimum de base du terrain (le minimum est 10 chez moi). Car dans ce cas, le coût G ne s’augmentera pas le long d’un trajet, ce qui conduit à des aberrations.

lissage.jpg

.

Différence de chemin pour départ et arrivée inversé :

c.pngd.png

.

Optimisation:

L’optimisation qui améliore le mieux la rapidité d’exécution que j’ai faite et de combiner un système de liste et de coordonnée:  imaginez l’étape 2.c exécutée 8 fois plus souvent que l’étape 2.a (pour la numérotation des étapes, se référer au tutorial). Avec une liste dont l’indice est la coordonnée (exemple : liste[x][y]) il n’y a plus besoin de rechercher un élément dans une liste! il suffit d’entrer les coordonnées dans l’indice du tableau liste pour savoir si c’est un obstacle, ou un élément de liste fermée (chez moi, il n’y a pas 3 liste (ouverte, fermée, obstacle) mais une : 0 = inexploré, 1 = ouverte, 2 = fermée, 3 = obstacle). Donc, pour savoir si une case en exploration n’est pas dans la liste fermé et n’est pas un obstacle, il suffit de faire : if (liste[x][y] <2).

Par contre, pour l’étape 2.a , j’utilise quand même une liste pour ne pas rechercher dans tous les pixels. C’est en fait une liste de coordonnée existant avec une variable contenant l’indice maximum (max) qui indique jusqu’à ou il faut chercher dans le tableau. Max est incrémenté à chaque fois qu’un nouvelle élément de liste ouverte est ajouté. Du coup, la recherche se fait aussi dans les éléments de la liste fermée, ce qui prend du temps inutilement mais cela évite d’avoir à trier une liste, ce qui est long également.

Une petit astuce pour la recherche  de la case de la liste ouverte possédant le coût le plus faible (toujours l’étape 2.a) et de l’utiliser pour détecter le cas ou il n’y a pas de chemin possible. En effet, lors ce qu’on sort de la recherche, si il n’y a plus d’éléments dans la liste ouverte, la variable que l’on utilise pour comparer les valeurs serra toujours égale à la valeur avec laquelle on l’aura initialisé (grosse valeur).

Le 28 Juillet 2008