Forums Développement Multimédia

Aller au contenu

Pathfinder

CODE

2 réponses à ce sujet

#1 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 05 July 2013 - 21:30 PM

Salut,

J'avais besoin pour un exercice en cours d'utiliser un Pathfinder, il existe bien sur un exemple qui fonctionne très bien écrit par Thoutmosis sur le Wiki ( http://forums.mediab..._astar_pratique ), mais je n'arrivai pas à rentrer dedans et j'avoue honteusement avoir eu la flemme de me relire tout le tuto (théorie et pratique)...

Du coup quitte à plonger dans le code je m'en suis monté un à ma sauce.
Pour ceux que ça intéresse voici le machin, si vous souhaitez vous amuser avec.
Si vous pensez qu'il y a plus simple et/ou des choses à corriger n'hésitez pas.

Avant toute chose, il ne fonctionne que sur des maps fermées, sinon il faudrait ajouter quelques lignes.
Voilà la base, dans l'IDE de Flash je me débarrasse du tout venant et des trucs inutiles, j'ai un calque code avec ceci :


// la carte du level
var map:Array = [
                 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
                 1,0,0,0,1,1,1,1,0,0,0,0,1,0,0,0,0,0,0,1,
                 1,0,0,0,0,0,0,0,0,0,1,1,1,0,0,1,1,0,3,1,
                 1,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,
                 1,0,1,0,1,0,0,0,1,1,1,1,1,0,1,0,1,0,0,1,
                 1,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,1,0,0,1,
                 1,0,1,0,1,1,1,1,1,0,0,0,0,0,1,0,1,1,0,1,
                 1,0,1,0,0,0,0,0,0,0,0,1,0,1,1,0,1,1,0,1,
                 1,0,1,0,1,1,1,1,1,1,1,1,0,1,1,0,1,0,0,1,
                 1,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,1,1,
                 1,0,0,0,1,1,1,1,1,1,0,1,0,0,0,0,0,0,0,1,
                 1,0,1,1,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,1,
                 1,1,1,1,1,0,1,1,1,1,0,0,0,0,1,1,1,1,1,1,
                 1,1,1,1,1,0,0,1,1,1,0,0,0,0,0,0,0,0,0,1,
                 1,0,0,0,0,0,0,1,0,1,0,0,1,0,0,1,0,1,0,1,
                 1,0,0,1,0,1,0,1,0,1,0,1,1,0,0,1,0,1,0,1,
                 1,0,1,1,0,1,0,0,0,0,0,1,0,0,0,1,0,1,0,1,
                 1,0,0,1,0,1,1,1,0,0,0,1,0,1,0,1,0,1,0,1,
                 1,2,0,0,0,0,0,0,1,1,1,1,0,0,0,1,0,0,0,1,
                 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
                 ];


// quelques variables
var T:int = 32;
var C:int = 20;
var i:int;
var j:int;
var t:Tuiles;
var liste:Array;
var chemin:Array;
var path:Pathfinder;
var cible:int;
var depart:int;
var stock:Array;

init();

// initialisation du level
function init(){
        path = new Pathfinder(map,C);
        creeMap();
        initPath();
        stage.addEventListener(MouseEvent.CLICK, nouveau);
}

// initialisation du pathfinding
function initPath():void{
        // trouve le départ et l'arrivée (a remplacer dans le cas d'un jeu)
        for (i = 0; i < map.length; i++){
                if(map[i]==2) cible = i;
                if(map[i]==3) depart = i;
        }
        path.chercheChemins(cible,depart);
        liste = path.liste;
        chemin = path.chemin;
        afficheChemin();
}

// affichage de la map
function creeMap():void{
        stock = [];
        for (i = 0; i < map.length; i++){
                t = new Tuiles();
                t.x = i%C*T;
                t.y = int(i/C)*T;
                stock.push(t);
                addChild(t);
        }
}

// affichage du chemin sur la map
function afficheChemin():void{
        for (i = 0; i < stock.length; i++){
                t = stock[i];
                t.gotoAndStop(map[i]+1);
                t.texte.text = "";
                for (j = 0; j < chemin.length; j++){
                        if(i==chemin[j].id && i!=cible && i!=depart) t.gotoAndStop(5);
                }
                for (j = 0; j < liste.length; j++){
                        if(i==liste[j].id) t.texte.text = liste[j].num;
                }
        }
}

// changement de position de la cible
function nouveau(e:MouseEvent):void{
       
        var X:int = mouseX/T;
        var Y:int = mouseY/T;
       
        if(map[X+Y*C]==0) {
                map[cible] = 0;
                map[X+Y*C] = 2;
                initPath();
        }
}
 

Basiquement, j'ai un clip "Tuiles" en bibliothèque pour afficher mes tuiles de la carte du level.
La plupart du code ne sert à rien pour le pahfinding, mais sert pour afficher le résultat, c'est pour ça que j'ai utilisé l'IDE car en fait on en a pas réellement besoin pour le calcul du chemin.

Ce qui est important pour le pathfinder, c'est la map tout d'abord puis :

var liste:Array; // liste des chemins possibles
var chemin:Array; // chemin le plus court
var path:Pathfinder; // création du pathfinder
var cible:int; // case cible à atteindre dans la map
var depart:int; // case de départ pour le chemin
 

"cible" et "depart" sont libres, il suffit de choisir une case pour chaque, du coup dans un jeu la cible peut être le joueur et le départ l'ennemi qui cherche à le traquer.

function init(){
        path = new Pathfinder(map,C);
        creeMap();
        initPath();
        stage.addEventListener(MouseEvent.CLICK, nouveau);
}

Dans la fonction "init", je crée l'objet "path" et je passe au constructeur la map en cours et le nombre de colonnes de la map, puis je crée la map (intérêt purement graphique) et j'initialise le pathfinding.

function initPath():void{
        // trouve le départ et l'arrivée (a remplacer dans le cas d'un jeu)
        for (i = 0; i < map.length; i++){
                if(map[i]==2) cible = i;
                if(map[i]==3) depart = i;
        }
        path.chercheChemins(cible,depart);
        liste = path.liste;
        chemin = path.chemin;
        afficheChemin();
}
 

Voilà la partie qui nous intéresse, vu que je n'ai pas d'objet qui se déplacent dans la map je choisi deux cases un peu comme je veux pour la cible et le départ.

Puis j'appelle la méthode "chercheChemin" de la classe Pathfinder en lui donnant la cible et le départ.
Je récupère ensuite la liste des chemins possibles que le pathfinder a trouvé et le chemin le plus court qu'il a trouvé et enfin j'affiche le résultat.

Donc, il suffit de se créer un objet "path" à partir de la classe Pathfinder, de lui donner la map en cours, puis de faire appel à la méthode "chercheChemin" en lui passant la case de départ et d'arrivée pour trouver le chemin le plus court entre les deux.

J'ai pas réussi à faire plus simple pour le moment.

Du côté de la classe Pathfinder voici ce qu'on a :

package {

  public class Pathfinder {
         
        private var map:Array;
        private var i:int;
        private var C:int;
        private var cible:int;
        private var depart:int;
        public var liste:Array;
        public var chemin:Array;
         
        public function Pathfinder(carte:Array, colonnes:int) {
                map = carte;
                C = colonnes;
        }
               
        public function chercheChemins(c:int, d:int):void {    
                liste = [];
                chemin = [];
                cible = c;
                depart = d;
                liste.push({id:depart,num:0});
                chemin.push({id:cible,num:-1});
                trouveVoisins(0, 1);
                trouveChemin(chemin[0].id, chemin[0].num);
        }

        private function trouveVoisins(debut:int, n:int):void{
                var longueur:int = liste.length;
                for (var i:int=debut; i<longueur; i++){
                        if(voisin(liste[i].id-C,n)) return; // haut
                        if(voisin(liste[i].id+C,n)) return; // bas
                        if(voisin(liste[i].id+1,n)) return; // droite
                        if(voisin(liste[i].id-1,n)) return; // gauche
                }
                trouveVoisins(longueur, n+1);
        }

        private function voisin(index:int, n:int):Boolean{
                if (index == cible) return true;
                if (map[index] != 1) {
                        for (var i:int = liste.length-1; i>=0; i--){
                                if (index == liste[i].id){
                                        if (n >= liste[i].num) return false;
                                        else liste.splice(i, 1);
                                }
                        }
                        liste.push({id:index,num:n})
                }
                return false;
        }

        private function trouveChemin(index:int, n:int):void{
                for each(var b:Object in liste){
                        if(b.id == index-1 && addChemin(b,n)) return;
                        if(b.id == index+1 && addChemin(b,n)) return;
                        if(b.id == index-C && addChemin(b,n)) return;
                        if(b.id == index+C && addChemin(b,n)) return;
                }
        }

        private function addChemin(b:Object,n:int):Boolean{
                if(n == -1 || n-1 == b.num) {
                        chemin.push( b );
                        trouveChemin(b.id, b.num);
                        return true;
                }
                return false;
        }
  }
}

En gros j'utilise deux fonctions récursives, la première cherche tous les chemins possibles en comptant le nombre de cases traversées et s'arrête dès que la case cible est atteinte.

La seconde part de la case cible et remonte le chemin en vérifiant que la case voisine testée à bien un chiffre directement inférieur à celui de la case d'origine. Si un plusieurs chemins sont possible c'est le premier trouvé qui est choisi.

J'ai donc un premier aller qui liste tous les chemins possibles et un retour qui liste le chemin le plus court trouvé, le tout est stocké dans les variables "liste" (tous les chemins possibles) et "chemin" (le chemin le plus court).

Je vous laisse le fichier de test pour ceux qui veulent s'amuser avec.
Et la démo, cliquez sur une case vide pour changer la cible.



- Afficher le SWF -
Fichier joint  simple Astar POO.swf   7.09 Ko   12 téléchargement(s)

Fichier(s) joint(s)



#2 thot

    Ceinture Noire

  • Moderateur
  • PipPipPipPipPipPipPip
  • 331 messages

Posté 20 August 2013 - 09:38 AM

Salut MrSpi, je n'ai pas bien compris ton implémentation d'A*.
Apparemment à un moment tu appelles ta méthode "chercheChemin" qui te renvoie plusieurs chemins possibles ...
A* normalement, ne renvoie qu'un chemin possible par appel.

A la limite, si tu le souhaites, je peux répondre aux questions que tu pourrais te poser concernant l'algo ???


PS: Je suis Thoutmosis, j'ai juste changé de pseudo

#3 Monsieur Spi

  • Community Manager
  • PipPipPipPipPipPipPipPip
  • 7017 messages

Posté 20 August 2013 - 12:49 PM

Hello,

En fait c'est juste un algo de remplissage modifié pour se limiter au chemin le plus court. Au final je ne renvoie aussi qu'un seul chemin, cependant il peut y en avoir plusieurs possibles (c'est à dire aussi court) pour aller d'une tuile à l'autre par exemple :

XXXXXXXXX
X0000000X
XAX0000BX
X0000000X
XXXXXXXXX

Ici que tu passe par le haut ou par le bas le chemin est de la même longueur.
Si tu regarde le SWF donné dans mon premier message tu verra que je part de la tuile rouge pour aller à la verte, (tu peux déplacer la verte où tu veux), je parcours toutes les voisines de chaque tuile et je compte le nombre de tuiles traversées jusqu'à atteindre la tuile verte. Tous les parcours s'arrêtent dès que la tuile verte est touchée, j’obtiens un chiffre, le nombre de tuile le plus court pour aller de A a B, et je n'ai plus qu'à parcourir ce chemin dans l'autre sens (de la verte à la rouge) en vérifiant que les chiffres se suivent de case en case pour avoir mon chemin le plus court. Je pense que ce n'est pas le plus optimisé mais ça fonctionne et ça suffisait pour mes besoins.

Mais après avoir relu ta méthode je la comprend, j'arrivais juste pas à l'utiliser comme je le voulais pour ce que je cherchais à faire, j'ai donc monté la mienne pour voir Image IPB



1 utilisateur(s) li(sen)t ce sujet

0 membre(s), 1 invité(s), 0 utilisateur(s) anonyme(s)