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.014s
  • Taille :4472 caractères
span class="co1">//Ajouter l'élement de départ
//Trier la liste selon F
//En temps normal, on devrait retrier cette liste en permanence. Pour gagner du temps, on ne le fait qu'une fois sur 4
"F"//Récuperer le premier élement (le plus petit F, le supprimer de openlist et l'ajouter dans closedlist)
//Un petit raccourci pour simplifier l'écriture
//La valeur non heuristique est toujours la même, on la précalcule

                //Faire le test pour les quatre adjacents :
                //-A gauche
//la ligne précédente calcule la valeur heuristique, méthode de Manhattan
//En déduire le cout du chemin.
//Si le chemin est possible, l'enregistrer comme ouvert
//-En haut
//-A droite
//-En bas
//              if(i %20==0)
                //              {
                        //              Trace(OpenList.length+"=>"+CurPoint.x+"?"+CurPoint.y);
                        //              }
"Le chemin n'a pas été trouvé : aucun parent !""La constante PATHFINDING_LIMITE a été dépassée.""Aucun chemin trouvé :-("//     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
//Trace(OpenList_Map[17][7].Parent.x+"?"+OpenList_Map[17][7].Parent.y);
//Trace(CurPoint.x+"?"+CurPoint.y);
//Remettre dans le bon ordre...
//Et c'est terminé !
}
 

Les classes associées

Code source : t_map.as
  • Langage : actionscript3
  • ΔT : 0.001s
  • Taille :201 caractères
 
Code source : t_Ligne.as
  • Langage : actionscript3
  • ΔT : 0.001s
  • Taille :264 caractères
span class="co1">//Cette ligne est elle destructible ?
Code source : t_node.as
  • Langage : actionscript3
  • ΔT : 0.001s
  • Taille :351 caractères
 
Code source : t_OpenList.as
  • Langage : actionscript3
  • ΔT : 0.001s
  • Taille :311 caractères
 

Fonctions

Code source : Misc.as
  • Langage : actionscript3
  • ΔT : 0.027s
  • Taille :5058 caractères
span class="st0">"font-weight: bold;color: #000000;""color: #000000;""color: #000080;""color: #000000;""color: #0000ff;""color: #000000;""color: #0000ff;""color: #000000;""color: #800000;""color: #000000;""font-style: italic;color: #808080;">//Génere un tableau multidimensionnel.</span>
"color: #000000;""font-weight: bold;color: #000000;""color: #000000;""color: #800000;""color: #000000;""font-weight: bold;color: #000000;""color: #000000;""color: #800000;""color: #000000;""color: #000000;""font-weight: bold;color: #000000;""color: #000000;""font-weight: bold;color: #000000;""color: #000000;""color: #0000ff;""color: #000000;""color: #000000;""color: #000000;""font-weight: bold;color: #000000;""color: #000000;""color: #800000;""color: #000000;""color: #000000;""font-weight: bold;color: #000000;""color: #000000;""font-weight: bold;color: #000000;""color: #000000;""color: #0000ff;""color: #000000;""color: #000000;""color: #000000;""font-weight: bold;color: #000000;""color: #000000;""color: #000080;""color: #000000;""color: #000000;""color: #000000;""color: #000000;""font-weight: bold;color: #000000;""color: #000000;""color: #000000;""font-weight: bold;color: #000000;""color: #000000;""color: #000080;""color: #000000;""color: #0000ff;""color: #000000;""color: #0000ff;""color: #000000;""color: #800000;""color: #000000;""font-style: italic;color: #808080;">//Génere un tableau multidimensionnel.</span>
"color: #000000;""font-weight: bold;color: #000000;""color: #000000;""color: #800000;""color: #000000;""font-weight: bold;color: #000000;""color: #000000;""color: #800000;""color: #000000;""color: #000000;""font-weight: bold;color: #000000;""color: #000000;""font-weight: bold;color: #000000;""color: #000000;""color: #0000ff;""color: #000000;""color: #000000;""color: #000000;""font-weight: bold;color: #000000;""color: #000000;""color: #800000;""color: #000000;""color: #000000;""font-weight: bold;color: #000000;""color: #000000;""font-weight: bold;color: #000000;""color: #000000;""color: #0000ff;""color: #000000;""color: #000000;""color: #000000;""font-weight: bold;color: #000000;""color: #000000;""color: #000080;""color: #000000;""font-weight: bold;color: #000000;""color: #000000;""color: #000080;""color: #000000;""color: #000000;""color: #000000;""color: #000000;""font-weight: bold;color: #000000;""color: #000000;""color: #000000;"
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...