Pathfinding: Algorithmes en A*

L’algorithme de recherche A* (A star) est un algo­rithme de recherche de chemin dans un graphe entre un nœud ini­tial et un nœud final tous deux don­nés. De par sa sim­plic­ité il est sou­vent présen­té comme exem­ple typ­ique d’algorithme util­isé en intel­li­gence arti­fi­cielle. L’algorithme A* a été créé pour que la pre­mière solu­tion trou­vée soit l’une des meilleures, c’est pourquoi il est célèbre dans des appli­ca­tions comme les jeux vidéo priv­ilé­giant la vitesse de cal­cul sur l’exactitude des résul­tats. Cet algo­rithme a été pro­posé pour la pre­mière fois par Peter E. Hart, Nils Nils­son et Bertram Raphael en 1968. Il s’agit d’une exten­sion de l’algorithme de Dijk­stra de 1959.

Astar_progress_animation

Algorithme

A chaque itéra­tion, A* va ten­ter de pren­dre le chemin le plus court pour aller d’une posi­tion Src à une posi­tion Dst.

Pour déter­min­er si un nœud est sucep­ti­ble de faire par­tie du chemin solu­tion, il faut pou­voir quan­ti­fi­er sa qual­ité. Le plus sou­vent, on utilise la dis­tance en “vol d’oiseau” entre la posi­tion du noeud et Dst, mais d’autres fonc­tions peu­vent être util­isées.

On tra­vaille à par­tir d’une posi­tion de départ, d’une arrivée, d’un ter­rain, et de deux listes de nœuds (ouverte et fer­mée), vides à l’origine.

  1. A par­tir du départ, on regarde quels sont les nœuds voisins (cor­re­spon­dant aux lib­ertés de mou­ve­ment — Par exem­ple, on peut aller à droite, à gauche, sauter ou ram­per, reculer ou avancer – 6 pos­si­bil­ités = 6 noeuds). On place le nœud de départ dans la liste fer­mée.
  2. Pour chaque nœud voisin :
    • Si c’est un obsta­cle, on passe (on ne traite pas ce nœud, il ne sera ajouté nulle part)
    • S’il est déjà dans la liste fer­mée, on passe (on a déjà étudié ce tra­jet)
    • S’il est déjà dans la liste ouverte, On véri­fie sa qual­ité. Si la qual­ité actuelle est meilleure, c’est que le chemin est plus court en pas­sant par le tra­jet actuel, donc on met à jour sa qual­ité dans la liste ouverte, et on met à jour son lien par­ent (avec noeud courant qui cor­re­spond à un meilleur chemin)
    • Sinon, on ajoute ce nœud à la liste ouverte avec comme par­ent le nœud courant
  3. On par­cours la liste ouverte à la recherche du nœud ayant la meilleure qual­ité. Si la liste ouverte est vide, il n’y a pas de solu­tion, fin de l’algorithme.
  4. On prend le meilleur, et on le retire de la liste ouverte pour le met­tre dans la liste fer­mée
  5. Nœud courant = nœud qu’on vient d’insérer
  6. Si nœud courant = Dst alors c’est bon, on a trou­vé un bon chemin, sinon on réitère en 2.

La liste ouverte con­tient toutes les pistes de tra­jet qui sont encore pos­si­bles. La liste fer­mée con­tient toutes les solu­tions étudiées, bonnes et mau­vais­es.

Le “bon chemin” trou­vé se retrou­ve en remon­tant le long des par­ents de nœuds.

Implémentation sous Python

Vous pou­vez télécharg­er le code source de la classe, ain­si que le code source de l’exemple à par­tir de l’archive suiv­ante.

AstarLa classe Astar est générique, elle est implé­men­tée au tra­vers de SQ_MapHandler :

astar = AStar.AStar(AStar.SQ_MapHandler(self.mapdata,self.mapw,self.maph))

Elle peut facile­ment être adap­tée et réu­til­isée pour d’autres sujet..

Le déplace­ment n’est assuré qu’au tra­vers de Haut,Bas,Droite,Gauche du mem­bre getAd­ja­centN­odes() de SQ_MapHandler. La fonc­tion ren­voi une liste des nœuds pos­si­bles.

La qual­ité est cal­culée par SQ_MapHandler._handleNode():

dx = max(x,destx) - min(x,destx)
dy = max(y,desty) - min(y,desty)
emCost = dx+dy
n.mCost += fromnode.mCost
n.score = n.mCost+emCost

Il y a ici deux notions de qual­ité: le walk­a­ble et la dis­tance. Un cal­cul per­met de gér­er les 2 valeurs.

C’est la classe Astar._getBestOpenNode() qui effectue la recherche du meilleur can­di­dat (nœud ayant la meilleure qual­ité): ce sont les scores qui sont com­parés et le plus petit représente le meilleur.
La fonc­tion prin­ci­pale qui étudie un nœud voisin en phase 2 de l’algo est la suiv­ante:

def _handleNode(self,node,end):
   i = self.o.index(node.lid)
   self.on.pop(i)
   self.o.pop(i)
   self.c.append(node.lid)
   nodes = self.mh.getAdjacentNodes(node,end)
   for n in nodes:
      if n.location == end:
         # reached the destination
         return n
      elif n.lid in self.c:
         # already in close, skip this
         continue
      elif n.lid in self.o:
         # already in open, check if better score
         i = self.o.index(n.lid)
         on = self.on[i];
         if n.mCost & on.mCost:
            self.on.pop(i);
            self.o.pop(i);
            self.on.append(n);
            self.o.append(n.lid);
         else:
            # new node, append to open list
            self.on.append(n);
            self.o.append(n.lid);
      return None

Liste ouverte (self.o) et fer­mée (self.c) ne sont com­posées que des posi­tions (node.lid) des dif­férents nœuds.Seule la liste ouverte pos­sède (self.on) pos­sède une liste de nodes. Chaque node est représen­té par une posi­tion (x,y), un lid unique (posi­tion. Ex: y*taillex+x), un coût, un score et un par­ent. Nodes réc­cupère ensuite la liste des nœuds adja­cents pos­si­bles et pour chaque nœud adja­cent un traite­ment est effec­tué. Si on est arrivé à des­ti­na­tion alors on retourne le nœud. Sinon, s’il est déjà en liste fer­mée, on passe. S’il est en liste ouverte, on le retrou­ve et si le cout actuel (cost) est meilleur que celui en liste ouverte, alors on le retire de la liste et on le rem­place par celui actuel. Sinon, on l’ajoute à la liste ouverte.
La recherche du plus court chemin se fait donc par la fonc­tion Astar.findPath():

def findPath(self,fromlocation, tolocation):
   self.o = []
   self.on = []
   self.c = []
   end = tolocation
   fnode = self.mh.getNode(fromlocation)
   self.on.append(fnode)
   self.o.append(fnode.lid)
   nextNode = fnode
   while nextNode is not None:
      finish = self._handleNode(nextNode,end)
      if finish:
         return self._tracePath(finish)
      nextNode=self._getBestOpenNode()
   return None

Elle ini­tialise les 3 listes précé­dente, puis définit la pro­priété end avec la des­ti­na­tion. Fnode est ini­tial­isé avec le nœud de départ, qu’on ajoute en liste ouverte. Le nœud courant devient alors le nœud de départ et on lance une boucle dans laque­lle, tant que le prochain nœud n’est pas vide, on le traite avec la fonc­tion _handleNode et on choisit le prochain meilleur dans la liste ouverte avec _getBestOpenNode().

C’est bien là le cœur du traite­ment.
Une fois le chemin trou­vée, on peut l’afficher grâce à Astar._tracePath()

def _tracePath(self,n):
   nodes = [];
   totalCost = n.mCost;
   p = n.parent;
   nodes.insert(0,n);
   while 1:
      if p.parent is None:
      break
      nodes.insert(0,p)
      p=p.parent
   return Path(nodes,totalCost)

Voici une vidéo de P. Armand  expli­quant l’algorithme pas à pas:

 

Laisser un commentaire

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.