Un pathfinder efficace avec A*

Ce code est une illustration du tutorial sur la récursivité

Le résultat

Fichier Flash :

Installez le plugin Flash pour voir l'animation : Cliquez ici pour le télécharger

Comment ça s'utilise ?

Image

Pathfinder en flash (AS3)

L'algorithme

De nombreux algorithmes décrivent A* de façon bien plus pédagogue que je ne saurais le faire...
Je conseille fortement la lecture de aStarTutorial (EN)

Le code

La fonction PathFinding :

Code source : PathFinding.as
  • Langage : actionscript3
  • ΔT : 0.075s
  • Taille :4472 caractères
function PathFind(Depart:Point,Arrivee:Point,Carte:Array):Array
{
        var OpenList:Array = new Array();
        var OpenList_Map:Array = GenerateArrayOfOpenList();
        var CurrentSquare:t_Node;
        var CurPoint:Point;
        var CurF:uint;
        var CurG:uint;
        var CurH:uint;
        var i:int=0;
        var j:int=0;
        //Ajouter l'élement de départ
        OpenList.push(new t_Node(Depart,0,0,0,Depart));
        OpenList_Map[Depart.x][Depart.y].Parent=Depart;
        //Trier la liste selon F
        i=0;
        do
        {
                i++;
                if(i % 4==0)
                {//En temps normal, on devrait retrier cette liste en permanence. Pour gagner du temps, on ne le fait qu'une fois sur 4
                OpenList.sortOn("F", Array.NUMERIC);
                }

                //Récuperer le premier élement (le plus petit F, le supprimer de openlist et l'ajouter dans closedlist)
                CurrentSquare = OpenList.shift();
                CurPoint=CurrentSquare.Empl; //Un petit raccourci pour simplifier l'écriture

                OpenList_Map[CurPoint.x][CurPoint.y].Ferme=true;
                CurG=CurrentSquare.G+10; //La valeur non heuristique est toujours la même, on la précalcule

                //Faire le test pour les quatre adjacents :
                //-A gauche
                if(CurPoint.x>0 && Carte[CurPoint.x][CurPoint.y].Gauche==null)
                {
                        CurH=10*(Math.abs(CurPoint.x-Arrivee.x-1) + Math.abs(CurPoint.y-Arrivee.y));
                        //la ligne précédente calcule la valeur heuristique, méthode de Manhattan
                        CurF=CurG+CurH;//En déduire le cout du chemin.
                        if(OpenList_Map[CurPoint.x-1][CurPoint.y].Visite==false && OpenList_Map[CurPoint.x-1][CurPoint.y].Ferme!=true)
                        {//Si le chemin est possible, l'enregistrer comme ouvert
                        OpenList.push(new t_Node(new Point(CurPoint.x-1,CurPoint.y),CurF,CurG,CurH,CurPoint));
                        OpenList_Map[CurPoint.x-1][CurPoint.y].Visite=true;
                        OpenList_Map[CurPoint.x-1][CurPoint.y].Parent=CurPoint;
                        }

                }
                //-En haut
                if(CurPoint.y>0 && Carte[CurPoint.x][CurPoint.y].Haut==null)
                {
                        CurH=10*(Math.abs(CurPoint.x-Arrivee.x) + Math.abs(CurPoint.y-Arrivee.y-1));
                        CurF=CurG+CurH;
                        if(OpenList_Map[CurPoint.x][CurPoint.y-1].Visite==false && OpenList_Map[CurPoint.x][CurPoint.y-1].Ferme!=true)
                        {
                                OpenList.push(new t_Node(new Point(CurPoint.x,CurPoint.y-1),CurF,CurG,CurH,CurPoint));
                                OpenList_Map[CurPoint.x][CurPoint.y-1].Visite=true;
                                OpenList_Map[CurPoint.x][CurPoint.y-1].Parent=CurPoint;
                        }
                }
                //-A droite
                if(CurPoint.x<LabyWidth && Carte[CurPoint.x+1][CurPoint.y].Gauche==null)
                {
                        CurH=10*(Math.abs(CurPoint.x-Arrivee.x+1) + Math.abs(CurPoint.y-Arrivee.y));
                        CurF=CurG+CurH;
                        if(OpenList_Map[CurPoint.x+1][CurPoint.y].Visite==false && OpenList_Map[CurPoint.x+1][CurPoint.y].Ferme!=true)
                        {
                                OpenList.push(new t_Node(new Point(CurPoint.x+1,CurPoint.y),CurF,CurG,CurH,CurPoint));
                                OpenList_Map[CurPoint.x+1][CurPoint.y].Visite=true;
                                OpenList_Map[CurPoint.x+1][CurPoint.y].Parent=CurPoint;
                        }
                }
                //-En bas
                if(CurPoint.y<LabyHeight && Carte[CurPoint.x][CurPoint.y+1].Haut==null)
                {
                        CurH=10*(Math.abs(CurPoint.x-Arrivee.x) + Math.abs(CurPoint.y-Arrivee.y+1));
                        CurF=CurG+CurH;
                        if(OpenList_Map[CurPoint.x][CurPoint.y+1].Visite==false && OpenList_Map[CurPoint.x][CurPoint.y+1].Ferme!=true)
                        {
                                OpenList.push(new t_Node(new Point(CurPoint.x,CurPoint.y+1),CurF,CurG,CurH,CurPoint));
                                OpenList_Map[CurPoint.x][CurPoint.y+1].Visite=true;
                                OpenList_Map[CurPoint.x][CurPoint.y+1].Parent=CurPoint;
                        }
                }
                //              if(i %20==0)
                //              {
                        //              Trace(OpenList.length+"=>"+CurPoint.x+"?"+CurPoint.y);
                        //              }
        }
        while(!(CurPoint.x==Arrivee.x && CurPoint.y==Arrivee.y) && OpenList.length!=0 && i<PATHFINDING_LIMITE);

        if(OpenList_Map[CurPoint.x][CurPoint.y].Parent==null)
        {
                Trace("Le chemin n'a pas été trouvé : aucun parent !");
                return null;
        }
        if(i>=PATHFINDING_LIMITE)
        {
                Trace("La constante PATHFINDING_LIMITE a été dépassée.");
                return null;
        }
        if(OpenList.length==0)
        {
                Trace("Aucun chemin trouvé :-(");
                return null;
        }

        //      Si on est encore dans la fonction, c'est qu'il n'ya a pas eu d'erreurs : on peut donc renvohyer le chemin.
        //      Faire le chemin inverse pour retrouver le path
        var Chemin:Array=new Array();
        CurPoint=Arrivee;
        i=0;
        //Trace(OpenList_Map[17][7].Parent.x+"?"+OpenList_Map[17][7].Parent.y);
        Chemin.push(Arrivee);
        do
        {
                i++;
                CurPoint=OpenList_Map[CurPoint.x][CurPoint.y].Parent;
                Chemin.push(CurPoint);
                //Trace(CurPoint.x+"?"+CurPoint.y);
        }
        while(!(CurPoint.x==Depart.x && CurPoint.y==Depart.y) && i<PATHFINDING_LIMITE);
        Chemin.push(Depart);
        Chemin.reverse(); //Remettre dans le bon ordre...
        return Chemin;

        //Et c'est terminé !
}
 

Les classes associées

Code source : t_map.as
  • Langage : actionscript3
  • ΔT : 0.004s
  • Taille :201 caractères
package
{
        public class t_Map
        {
                public var Haut:t_Ligne;
                public var Gauche:t_Ligne;
                public function t_Map(Haut:t_Ligne=null,Bas:t_Ligne=null)
                {
                        this.Haut=null;
                        this.Gauche=null;
                }
        }
}
Code source : t_Ligne.as
  • Langage : actionscript3
  • ΔT : 0.006s
  • Taille :264 caractères
package
{
        import flash.display.Sprite;
        public class t_Ligne extends Sprite
        {
                public var Indestructible:Boolean; //Cette ligne est elle destructible ?
                public function t_Ligne(Indestructible:Boolean=false)
                {
                        this.Indestructible = Indestructible;
                }
        }
}
Code source : t_node.as
  • Langage : actionscript3
  • ΔT : 0.006s
  • Taille :351 caractères
package
{
        import flash.geom.Point;
        public class t_Node
        {
                public var Empl:Point;
                public var F:uint;
                public var G:uint;
                public var H:uint;
                public var Parent:Point;

                public function t_Node(Empl:Point,F:uint,G:uint,H:uint,Parent:Point)
                {
                        this.Empl = Empl;
                        this.F = F;
                        this.G = G;
                        this.H = H;
                        this.Parent = Parent;
                }
        }
}
 
Code source : t_OpenList.as
  • Langage : actionscript3
  • ΔT : 0.005s
  • Taille :311 caractères
package
{
        import flash.geom.Point;
        public class t_OpenList
        {
                public var Visite:Boolean;
                public var Parent:Point;
                public var Ferme:Boolean;
                public function t_OpenList(Parent:Point,Visite:Boolean=false,Ferme:Boolean=false)
                {
                        this.Visite=Visite;
                        this.Parent=Parent;
                        this.Ferme=Ferme;
                }
        }
}

Fonctions

Code source : Misc.as
  • Langage : actionscript3
  • ΔT : 0.188s
  • Taille :5058 caractères
<pre>
<span style="font-weight: bold;color: #000000;">function</span><span style="color: #000000;"> </span><span style="color: #000080;">GenerateArray</span><span style="color: #000000;">(Largeur:uint=</span><span style="color: #0000ff;">64</span><span style="color: #000000;">,Hauteur:uint=</span><span style="color: #0000ff;">64</span><span style="color: #000000;">):</span><span style="color: #800000;">Array</span>
<span style="color: #000000;">{</span><span style="font-style: italic;color: #808080;">//Génere un tableau multidimensionnel.</span>
<span style="color: #000000;">  </span><span style="font-weight: bold;color: #000000;">var</span><span style="color: #000000;"> Tableau:</span><span style="color: #800000;">Array</span><span style="color: #000000;"> = </span><span style="font-weight: bold;color: #000000;">new</span><span style="color: #000000;"> </span><span style="color: #800000;">Array</span><span style="color: #000000;">();</span>
<span style="color: #000000;">  </span><span style="font-weight: bold;color: #000000;">for</span><span style="color: #000000;">(</span><span style="font-weight: bold;color: #000000;">var</span><span style="color: #000000;"> i:uint=</span><span style="color: #0000ff;">0</span><span style="color: #000000;">;i&lt;=Largeur;i++)</span>
<span style="color: #000000;">  {</span>
<span style="color: #000000;">          Tableau[i] = </span><span style="font-weight: bold;color: #000000;">new</span><span style="color: #000000;"> </span><span style="color: #800000;">Array</span><span style="color: #000000;">();</span>
<span style="color: #000000;">          </span><span style="font-weight: bold;color: #000000;">for</span><span style="color: #000000;">(</span><span style="font-weight: bold;color: #000000;">var</span><span style="color: #000000;"> j:uint=</span><span style="color: #0000ff;">0</span><span style="color: #000000;">;j&lt;=Hauteur;j++)</span>
<span style="color: #000000;">          {</span>
<span style="color: #000000;">                  Tableau[i][j]= </span><span style="font-weight: bold;color: #000000;">new</span><span style="color: #000000;"> </span><span style="color: #000080;">t_Map</span><span style="color: #000000;">();</span>
<span style="color: #000000;">          }</span>
<span style="color: #000000;">  }</span>
<span style="color: #000000;">  </span><span style="font-weight: bold;color: #000000;">return</span><span style="color: #000000;"> Tableau;</span>
<span style="color: #000000;">}</span>

<span style="font-weight: bold;color: #000000;">function</span><span style="color: #000000;"> </span><span style="color: #000080;">GenerateArrayOfOpenList</span><span style="color: #000000;">(Largeur:uint=</span><span style="color: #0000ff;">64</span><span style="color: #000000;">,Hauteur:uint=</span><span style="color: #0000ff;">64</span><span style="color: #000000;">):</span><span style="color: #800000;">Array</span>
<span style="color: #000000;">{</span><span style="font-style: italic;color: #808080;">//Génere un tableau multidimensionnel.</span>
<span style="color: #000000;">  </span><span style="font-weight: bold;color: #000000;">var</span><span style="color: #000000;"> Tableau:</span><span style="color: #800000;">Array</span><span style="color: #000000;"> = </span><span style="font-weight: bold;color: #000000;">new</span><span style="color: #000000;"> </span><span style="color: #800000;">Array</span><span style="color: #000000;">();</span>
<span style="color: #000000;">  </span><span style="font-weight: bold;color: #000000;">for</span><span style="color: #000000;">(</span><span style="font-weight: bold;color: #000000;">var</span><span style="color: #000000;"> i:uint=</span><span style="color: #0000ff;">0</span><span style="color: #000000;">;i&lt;=Largeur;i++)</span>
<span style="color: #000000;">  {</span>
<span style="color: #000000;">          Tableau[i] = </span><span style="font-weight: bold;color: #000000;">new</span><span style="color: #000000;"> </span><span style="color: #800000;">Array</span><span style="color: #000000;">();</span>
<span style="color: #000000;">          </span><span style="font-weight: bold;color: #000000;">for</span><span style="color: #000000;">(</span><span style="font-weight: bold;color: #000000;">var</span><span style="color: #000000;"> j:uint=</span><span style="color: #0000ff;">0</span><span style="color: #000000;">;j&lt;=Hauteur;j++)</span>
<span style="color: #000000;">          {</span>
<span style="color: #000000;">                  Tableau[i][j]= </span><span style="font-weight: bold;color: #000000;">new</span><span style="color: #000000;"> </span><span style="color: #000080;">t_OpenList</span><span style="color: #000000;">(</span><span style="font-weight: bold;color: #000000;">new</span><span style="color: #000000;"> </span><span style="color: #000080;">Point</span><span style="color: #000000;">());</span>
<span style="color: #000000;">          }</span>
<span style="color: #000000;">  }</span>
<span style="color: #000000;">  </span><span style="font-weight: bold;color: #000000;">return</span><span style="color: #000000;"> Tableau;</span>
<span style="color: #000000;">}</span></pre>
Auteur
Neamar
Date
Juin 2008
But
Trouver un chemin
Voir aussi
Compiler l'AS3
Voir aussi
La récursivité
Menu
Index des ressources

Chargement du sommaire...