Forums Développement Multimédia

Les formations Mediabox
Les formations Mediabox

Explication de l'algorithme de pathfinding A* - la pratique

Compatible ActionScript 3. Cliquer pour en savoir plus sur les compatibilités.Par Thoutmosis, le 08 janvier 2010

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” ).

L"extension Adobe Flash Plugin est nécessaire pour afficher ce contenu.

Cliquer pour créer ou effacer des murs. Point rouge = départ. Point bleu = arrivée.

Ce tuto se veut la suite logique de celui que vous pouvez lire à cette adresse → Explication de l'algorithme de pathfinding A* - la théorie , sa lecture préalable est donc fortement recommandée si vous voulez comprendre ce qui se joue ici.

Dans cette partie, nous allons créer une classe nommée Pathfinder qui contient une méthode statique findPath, de très petites notions d'objets sont donc recommandées mais non essentielles si vous comprenez ce qu'est une fonction il n'y aura aucun problème.

C'est en forgeant qu'on devient forgeron

Nous allons procéder par petites étapes pour l'implémentation de cet algorithme, ce qui aura le désavantage de rendre l'article un peu plus long mais beaucoup plus compréhensible.

Bon, assez parlé, place au code !!

Première étape: La classe Pathfinder

On va commencer par créer la classe Pathfinder et sa méthode statique findPath.

Code

 
package
{
	import Node;
 
	public class Pathfinder
	{
		public static const NODE_DISTANCE_VALUE:int = 100;
 
		private static var m_openList:Array;
		private static var m_closeList:Array;
 
		public static function findPath( param_graphe:Array, param_start:Node, param_end:Node ):Array
		{
			// on crée les listes fermées et les listes ouvertes
			m_openList = new Array();
			m_closeList = new Array();
 
			// on crée la variable qui va accueillir le chemin final
 
			var finalPath:Array = new Array();
 
 
			//  traitement
 
			// on retourne le chemin final
 
			return finalPath;
		}
 
	}
}

Explications

Nous n'expliquerons pas ici ce qu'est un package ou une méthode statique pour la bonne et simple raison que ceci n'est pas un cours de POO, cependant, pour ceux et celles qui ne seraient pas familiers avec ces notions, je les invite à considérer findPath comme une fonction tout à fait normale.

Premier point: constantes et distances

Nous n'allons pas nous attarder la dessus, sachez simplement que NODE_DISTANCE_VALUE représente la distance parcourue horizontalement ou verticalement d'un node A vers un node B, A et B étant adjacents.

Deuxième point: liste ouverte, liste fermée et résultat final

Nous créons au sein de findPath trois variables qui représentent la liste ouverte, la liste fermée et une variable finale qui contiendra le résultat de notre recherche. Notez seulement que la liste ouverte et la liste fermée sont des propriétées statiques de la classe Pathfinder. Pour de plus amples explications concernant les listes ouverte et fermée, je vous invite à consulter le tuto précédent.

Troisième point: les paramètres

Les paramètres de findPath peuvent être quelques peu déconcertants, surtout les 2ème et 3ème.

  1. Le paramètre param_graphe: c'est un tableau à deux dimensions qui contient le monde dans lequel l'on va chercher notre chemin.
  2. Le paramètre param_start: c'est un objet de type Node, il représente le point de départ de notre recherche.
  3. Le paramètre param_end: c'est un objet de type Node, il représente le point d'arrivée de notre recherche.

Mais à ce stade là, il y a un problème, on ne sait pas encore ce qu'est un objet type Node !! Ce qui nous amène à la prochaine partie…

Deuxième étape: La classe Node

Ici, nous n'allons pas revenir sur ce qu'est un node, en revanche, nous allons définir ce qu'il est programmatiquement parlant.

Voici le code de classe node:

package
{
	public class Node
	{
		private var m_g:int;
		private var m_h:int;
		private var m_f:int;
		private var m_col:int;
		private var m_line:int;
		private var m_walkable:Boolean;
		private var m_parent:Node;
 
		public function Node()
		{
			walkable = true;
			g = h = f = 0;
			parent = this;
		}
 
 
 
		public function set parent( param_node:Node ):void{ m_parent = param_node; }
		public function set walkable( param_walkable:Boolean ):void{ m_walkable = param_walkable; }
		public function set g( param_g:int ):void{ m_g = param_g; }
		public function set f( param_f:int ):void{ m_f = param_f; }
		public function set h( param_h:int ):void{ m_h = param_h; }
		public function set col( param_col:int ):void{ m_col = param_col; }
		public function set line( param_line:int ):void{ m_line = param_line; }
 
		public function get parent():Node{ return m_parent; }
		public function get walkable():Boolean{ return m_walkable; }
		public function get g():int{ return m_g; }
		public function get f():int{ return m_f; }
		public function get h():int{ return m_h; }
		public function get col():int{ return m_col; }
		public function get line():int { return m_line; }
 
	}
}

Explications

Nous allons expliquer chaque propriété de classe Node en détail:

  1. parent: cette propriété représente le parent de ce Node càd un objet de type Node.
  2. walkable: est un booléen qui définit si l'on peut marcher ou passer par ce node, en gros c'est le paramètre qui définit si le node en question est un obstacle ( comme un mur par exemple ).
  3. g, f et h: ce sont des notions expliquées dans la précédent tuto, elles serviront en permanence lors des calculs.
  4. col: représente le numéro de la colonne dans laquelle se situe ce node ( dans le param_graphe, tableau à deux dimensions )
  5. line: représente le numéro de la ligne dans laquelle se situe ce node ( dans le param_graphe, tableau à deux dimensions )

Voilà, maintenant que nous savons ce qu'est un node, nous pouvons passer à l'implémentation.

Troisième étape: Implémentation

Avant de commencer, nous allons écrire 8 méthodes qui vont nous servir durant tout le processus de recherche.

  • Une méthode pour supprimer un node de la liste ouverte: removeFromCloseList
  • Une méthode pour supprimer un node de la liste fermée: removeFromOpenList
  • Une méthode pour ajouter un node à la liste ouverte tout en étant sur qu'il ne se trouve pas dans la liste fermée: addToCloseList
  • Une méthode pour ajouter un node à la liste fermée tout en étant sur qu'il ne se trouve pas dans la liste ouverte: addToOpenList
  • Une méthode pour récupérer le node avec le plus petit F contenu dans la liste ouverte: getCurrentNode
  • Une méthode pour récupérer les voisins du node courant ( CURRENT ): getNeighbours
  • Une méthode pour savoir si un node se trouve dans la liste fermée: isOnCloseList
  • Une méthode pour savoir si un node se trouve dans la liste ouverte: isOnOpenList

Ensuite, on code la fonction findPath en respectant les étapes décrites précédemment. Le code ci-dessous est commenté étape par étape afin que vous puissiez suivre le déroulement de l'implémentation.

Code

Pathfinder.as :

 
 
package
{
  import Node;
 
  public class Pathfinder
  {
    public static const NODE_DISTANCE_VALUE:int = 10;
 
    private static var m_openList:Array;
    private static var m_closeList:Array;
 
    public static function findPath( param_graphe:Array, param_start:Node, param_end:Node ):Array
    {
      // on crée les listes fermées et les listes ouvertes
      m_openList = new Array();
      m_closeList = new Array();
 
      // on crée la variable qui va accueillir le chemin final
 
      var finalPath:Array = new Array();
 
 
      //  traitement
 
      /**
        - Ajout du node de départ à la liste ouverte.
        - Entrée dans la boucle suivante:  
          - Récupération du node avec le plus petit F contenu dans la liste ouverte. On le nommera CURRENT.
          - Basculer CURRENT dans la liste fermée.
          - Pour chacun des 4 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.
 
        - 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.
      */
 
      addToOpenList( param_start );
 
      var currentNode:Node = null;
 
      while( m_openList.length > 0 ) //  stopper la boucle si la liste ouverte est vide
      {
        // a. Récupération du node avec le plus petit F contenu dans la liste ouverte. On le nommera CURRENT.
        currentNode = getCurrentNode(); 
 
        //  stopper la boucle si n ajoute le noeud d'arrivée à la liste fermée
        if( currentNode == param_end ) 
          break;
 
        // b. Basculer CURRENT dans la liste fermée.
        addToCloseList( currentNode ); 
 
        //  récupération des voisins de CURRENT
        var neighbours:Array = getNeighbours( currentNode, param_graphe ); 
        var maxi:int = neighbours.length;
 
        // Pour chacun des 8 nodes adjacents à CURRENT appliquer la méthode suivante:
        for( var i:int = 0; i < maxi; ++i )
        {
          var node:Node = neighbours[i];
 
          //Si le node est un obstacle ou est dans la liste fermée ignorez-le et passer à l'analyse d'un autre node.
          if( isOnCloseList( node ) || node.walkable == false ) 
            continue;
 
          /* on calcule le nouveau g */
          var newG:int;
          newG = node.parent.g + NODE_DISTANCE_VALUE;
 
          /*on calcule le nouveau h */
          var newH:int = ( Math.abs( param_end.line - node.line ) + Math.abs( param_end.col - node.col ) ) * NODE_DISTANCE_VALUE;
 
          /*on calcule le nouveau F*/
          var newF:int = newH + newG;
 
 
 
          if( isOnOpenList( node ) )
          {
            //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.
 
            if( newG < node.g )
            {
              node.parent = currentNode;
              node.g = newG;
              node.h = newH;
              node.f = newF;
            }
 
          }
          else 
          {
            //Si le node n'est pas dans la liste ouverte, ajoutez-le à la dite liste et faites de CURRENT son parent(P). 
            //Calculez et enregistrez ses propriétés F, G et H.
            addToOpenList( node );
            node.parent = currentNode;
            node.g = newG;
            node.h = newH;
            node.f = newF;
          }
        }
 
      }
 
 
      // on est sorti de la liste, on a deux solutions, soit la liste ouverte est vide dans ces cas là il 
      // n'y a pas de solutions et on retoure directement finalPath;
 
      if( m_openList.length == 0 )
        return finalPath;
 
 
      // Soit on maintenant on construit le chemin à rebours;
 
      var lastNode:Node = param_end;
      while( lastNode != param_start )
      {
        trace( lastNode.parent );
        finalPath.push( lastNode );
        lastNode = lastNode.parent;
      }
 
 
      // on retourne le chemin final
 
      return finalPath.reverse();
    }
 
 
    private static function removeFromCloseList( param_node:Node ):void
    {
      var tmpList:Array = new Array();
      var maximum:int =  m_closeList.length;
 
      for( var i:int = 0; i < maximum; ++i )
      {
        if( m_closeList[i] != param_node )
          tmpList.push( m_closeList[i] );
      }
 
      m_closeList = tmpList;
    }
 
 
    private static function removeFromOpenList( param_node:Node ):void
    {
      var tmpList:Array = new Array();
      var maximum:int = m_openList.length;
 
      for( var i:int = 0; i < maximum; ++i )
      {
        if( m_openList[i] != param_node )
          tmpList.push( m_openList[i] );
      }
 
      m_openList = tmpList;
    }
 
 
    private static function addToCloseList( param_node:Node ):void
    {
      removeFromOpenList( param_node );
      m_closeList.push( param_node );
    }
 
 
    private static function addToOpenList( param_node:Node ):void
    {
      removeFromCloseList( param_node );
      m_openList.push( param_node );
    }
 
 
    private static function getCurrentNode():Node
    {
      var tmpList:Array = new Array();
      var maximum:int = m_openList.length;
      var minF:int = 1000000;
      var curNode:Node = null;
 
      for( var i:int = 0; i < maximum; ++i )
      {
        var node:Node = m_openList[i] as Node;
 
        if( node.f < minF )
        {
          minF = node.f;
          curNode = node;
        }
      }
 
      return curNode;
    }
 
 
    private static function getNeighbours( param_node:Node, param_graphe:Array ):Array
    {
      var neighbours:Array = new Array();
      var maxcol:int = param_graphe[0].length;
      var maxline:int = param_graphe.length;
 
 
      // on calcule l'indice de la ligne au dessus de la ligne du node
      var indiceUp:int = param_node.line - 1; 
 
      // on calcule l'indice de la ligne au dessus de la ligne du node
      var indiceBottom:int = param_node.line + 1; 
 
      // on calcule l'indice de la colonne à gauche de la colonne du node
      var indiceLeft:int = param_node.col - 1; 
 
      // on calcule l'indice de la colonne à droite de la colonne du node
      var indiceRight:int = param_node.col + 1;
 
 
      // si la ligne du dessus existe alors le node du dessus existe on ajoute alors le  node du dessus
      if( indiceUp > -1 ) 
        neighbours.push( param_graphe[indiceUp][param_node.col]);
 
      // si la ligne du dessous existe alors le node du dessous existe on ajoute alors le  node du dessous  
      if( indiceBottom < maxline ) 
        neighbours.push( param_graphe[indiceBottom][param_node.col]);
 
      // si la colonne de gauche existe alors le node de gauche existe on ajoute alors le  node de gauche
      if( indiceLeft > -1 )
        neighbours.push( param_graphe[param_node.line][indiceLeft]);
 
      // si la colonne de droite existe alors le node de droite existe on ajoute alors le  node de droite
      if( indiceRight < maxcol ) 
        neighbours.push( param_graphe[param_node.line][indiceRight]);
 
 
      return neighbours;
    }
 
 
    private static function isOnOpenList( param_node:Node ):Boolean
    {
      var maximum:int = m_openList.length;
 
      for( var i:int = 0; i < maximum; ++i )
      {
        if( m_openList[i] == param_node )
          return true;
      }
 
      return false;
    }
 
 
    private static function isOnCloseList( param_node:Node ):Boolean
    {
      var maximum:int = m_closeList.length;
 
      for( var i:int = 0; i < maximum; ++i )
      {
        if( m_closeList[i] == param_node )
          return true;
      }
 
      return false;
    }
 
 
  }
}

Quatrième étape: Création d'un graphe et mise en place du code de test

Dans cette partie, nous allons créer un graphe qui est un bête tableau à deux dimensions contenant des nodes. Nous représenterons les nodes comme ceci :

  • Les nodes avec la propriété walkable = true seront réprésentés ainsi: 0
  • Les nodes avec la propriété walkable = false seront réprésentés ainsi: 1

Au passage, nous importerons les classes Pathfinder et Node, prenez donc le code de la classe Pathfinder et enregistrez-le dans un fichier que vous nommerez Pathfinder.as, faites la même chose pour la classe Node. Nous allons ensuite créer deux nodes start et end et chercher le chemin entre ces deux nodes.

Main.as :

package
{
  import flash.display.Sprite;
  import Pathfinder;
  import Node;
 
  public class Main extends Sprite
  {
    public function Main()
    {
 
      var graphe:Array = [ 
        [ 0, 0, 0, 0, 1],
        [ 1, 1, 0, 0, 1],
        [ 0, 0, 0, 0, 1],
        [ 0, 0, 1, 0, 1],
        [ 0, 0, 1, 0, 1],
        [ 0, 0, 1, 1, 1]
        ];
 
 
      var realGraphe:Array = new Array();
      var ligne:Array = graphe[0] as Array;
 
      var maxcol:int = ligne.length;
      var maxline:int = graphe.length;
 
      for ( var i:int = 0; i < maxline; i++ ) 
      {
        var line:Array = new Array();
 
        for ( var j:int = 0; j < maxcol; j++ )
        {
          var node:Node = new Node();
 
          if ( graphe[i][j] == 1 )
          {
            node.walkable = false;
          }
 
          node.col = j;
          node.line = i;
 
          line.push( node );
        }
 
        realGraphe.push( line );
      }
 
 
      var start:Node = realGraphe[0][0]; //  on crée le node de départ
      var end:Node = realGraphe[2][1]; //  on crée le node d'arrivée
 
	  //  on cherche le chemin allant de //start// à //end//
      var chemin:Array = Pathfinder.findPath( realGraphe, start, end ); 
    }
  }
}
 
 
 

Conclusion

Voilà, vous pouvez dorénavant trouver votre chemin dans un graphe. N'hésitez pas à améliorer le système par exemple ou virant le système de tableau pour les listes ouvertes et fermées ( personnellement je préfère les valeurs booléennes ou entières appliquées au node ). Ensuite si vous voulez vraiment gagner en performances, vous pouvez toujours faire abstraction des méthodes et inliner toutes les méthodes. Pour la suite je vous concocte pas mal de tutos notamment:

  • L'optimisation en AS3: les opérateurs binaires, l'inlining, les post-incrémentations, les choix des bons types, Les pool d'objets.
  • Un tuto sur la génération de labyrinthe: vous verrez comment implémenter un algorithme de génération de labyrinthe pour vos jeux.
  • Un tuto sur mon moteur 3D iso et sa prise en main ( voir ma signature ): vous verrez comment créer des mondes interactifs en trois patés de code.

En attendant je vous souhaite bien du plaisir, Have Fun !