Pathfinding a* astar

Soyez le premier à donner votre avis sur cette source.

Snippet vu 14 921 fois - Téléchargée 16 fois

Contenu du snippet

Ce code retrouve le plus court chemin entre deux points à l'aide de la méthode AStar A*.

pour ceux qui ne connaissent pas encore cette méthode -> http://blog.lalex.com/?q=astar

Source / Exemple :


/*******************************La classe case qui représente une position ***********************************/

/**

  • Auteur : KHALFALLAOUI MOURAD
  • COPYRIGHT
  • /
package com; public class Case { private int x; private int y; private int f=0; private int g; private int h; private Case parent; public Case(int x, int y) { super(); this.x = x; this.y = y; } public int getF() { return g+h; } public void setF(int f) { this.f = f; } public int getG() { return g; } public void setG(int g) { this.g = g; } public int getH() { return h; } public void setH(int h) { this.h = h; } public Case getParent() { return parent; } public void setParent(Case parent) { this.parent = parent; } public int getX() { return x; } public void setX(int x) { this.x = x; } public int getY() { return y; } public void setY(int y) { this.y = y; } @Override public int hashCode() { final int PRIME = 31; int result = 1; result = PRIME * result + x; result = PRIME * result + y; return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; final Case other = (Case) obj; if (x != other.x) return false; if (y != other.y) return false; return true; } } /**************************************************La Classe Astar *****************************************************/ /**
  • Auteur : KHALFALLAOUI MOURAD
  • COPYRIGHT
  • /
package com; import java.util.ArrayList; import java.util.HashSet; import java.util.Iterator; import java.util.Set; public class Astar { ArrayList<Case> ferme= new ArrayList<Case>(); ArrayList<Case> ouverte= new ArrayList<Case>(); Set<Case> path=new HashSet<Case>(); boolean go=false; // les lignes 0 et les colonnes 0 sont ignorées dans le calcul du chemain // elles nous permettent seulement d'avoir un tableau de recherche commençant à 1 au lieu de 0; static int[][] pos={{5,5,5,5,5,5,5,5,5,5,5},//0 //ceci est un exemple d'utilsation {5,0,0,0,0,0,1,0,0,0,0},//1 {5,1,0,1,1,1,0,0,0,1,0},//2 {5,1,0,0,0,0,0,0,0,0,0},//3 {5,1,0,1,0,0,1,0,0,1,1},//4 {5,0,0,1,0,0,1,0,0,0,0},//5 {5,0,1,1,0,1,0,1,1,0,0},//6 {5,0,0,0,0,1,0,0,0,0,0},//7 {5,0,1,0,0,1,1,0,0,0,1},//8 {5,0,1,1,0,0,0,0,0,1,0},//9 {5,0,0,0,0,0,1,1,0,0,0}};//10 ///////////// 0 1 2 3 4 5 6 7 8 9 10 Case debut; Case fin; public Astar(){ } public Astar(Case debut, Case fin) { if (pos[debut.getX()][debut.getY()] !=1 && pos[fin.getX()][fin.getY()]!=1){ this.debut = debut; this.fin = fin; ajoutAdjacentAOuverte(debut); } else System.out.println("Vous êtes sur un mur !!!"); } public Astar(Case debut, Case fin, int[][] pos) { if (pos[debut.getX()][debut.getY()] !=1 && pos[fin.getX()][fin.getY()]!=1){ this.pos=pos; this.debut = debut; this.fin = fin; ajoutAdjacentAOuverte(debut);} else System.out.println("Vous êtes sur un mur !!!"); } public void ajoutAdjacentAOuverte(Case debut){ int xc,yc; Case courante=debut; Case memoire=null; while (!isInList(fin,ferme)){ if (!isInList(courante,ferme)){ ferme.add(courante); xc=courante.getX(); yc=courante.getY(); if ((yc>=2) && (pos[xc][yc-1] != 1)) ajoutOuverte(courante, (new Case(xc,yc-1)));////// if ((yc<pos.length-1) && (pos[xc][yc+1] != 1)) ajoutOuverte(courante, (new Case(xc,yc+1)));////// if (xc<pos.length-1){ if ((pos[xc+1][yc] != 1)) ajoutOuverte(courante, (new Case(xc+1,yc)));/////// if ((yc>=2) && (pos[xc+1][yc-1] != 1) && !((pos[xc][yc-1] == 1) || (pos[xc+1][yc] == 1))) ajoutOuverte(courante, (new Case(xc+1,yc-1))); //les 2 dernieres conditions: !((pos[xc][yc-1] == 1) || (pos[xc+1][yc] == 1)) pour eviter de sauter par dessus les coins des murs if ((yc<pos.length-1) && (pos[xc+1][yc+1] != 1)&& !((pos[xc+1][yc] == 1) || (pos[xc][yc+1] == 1))) ajoutOuverte(courante, (new Case(xc+1,yc+1)));//les 2 dernieres conditions: !((pos[xc+1][yc] == 1) || (pos[xc][yc+1] == 1)) pour eviter de sauter par dessus les coins des murs } if (xc>=2){ if ((pos[xc-1][yc] != 1)) ajoutOuverte(courante, (new Case(xc-1,yc))); if ((yc>=2) && (pos[xc-1][yc-1] != 1) && !((pos[xc-1][yc] == 1) || (pos[xc][yc-1] == 1))) ajoutOuverte(courante, (new Case(xc-1,yc-1)));//les 2 dernieres conditions: !((pos[xc-1][yc] == 1) || (pos[xc][yc-1] == 1)) pour eviter de sauter par dessus les coins des murs if ((yc<pos.length-1) && (pos[xc-1][yc+1] != 1) && !((pos[xc-1][yc] == 1) || (pos[xc][yc+1] == 1))) ajoutOuverte(courante, (new Case(xc-1,yc+1)));///les 2 dernieres conditions: !((pos[xc-1][yc] == 1) || (pos[xc][yc+1] == 1)) pour eviter de sauter par dessus les coins des murs } memoire=courante; } ouverte.remove(courante); if (ouverte.isEmpty()) { if (Math.abs(memoire.getX()-fin.getX())>=1 && Math.abs(memoire.getY()-fin.getY())>=1)// pour permettre les sauts des coins des murs remplacer >= par > et && par || {System.out.println("Il n'y a pas de chemin entre ces deux point !!!"); break; } else break; } courante=getMinF(); } fin.setParent(memoire); getParentPath(); dessine(); dessineResult(); } public void afficheList(ArrayList<Case> list){ Iterator<Case> ito=list.iterator(); Case test; while(ito.hasNext()){ test=ito.next(); System.out.println(test.toString()+"-->:"+" X= "+test.getX()+" Y= "+test.getY()+" F= "+test.getF()); } } public boolean isInList(Case courante, ArrayList<Case> list){ Iterator ito=list.iterator(); while(ito.hasNext()){ if (ito.next().equals(courante)) return true; } return false; } public void ajoutOuverte( Case courante, Case adjacente){ int g=courante.getG()+((adjacente.getX()==courante.getX() || adjacente.getY()==courante.getY())?10:15); int h=(Math.abs(adjacente.getX()-fin.getX())+Math.abs(adjacente.getY()-fin.getY())); int f=g+h; if (isInList(adjacente, ouverte)){ if (adjacente.getF() > f){ adjacente.setG(g); adjacente.setF(f); adjacente.setParent(courante); } }else if (!isInList(adjacente, ferme)) { adjacente.setG(g); adjacente.setH(h); adjacente.setF(f); adjacente.setParent(courante); ouverte.add(adjacente); } } public static int[][] getPos() { return pos; } public static void setPos(int[][] pos) { Astar.pos = pos; } public Set<Case> getPath() { while(!go){getPath();} return path; } public int getPathSize() { while(!go){getPath();} return path.size(); } public void setPath(Set<Case> path) { this.path = path; } Case getMinF(){ Case min=null; min=ouverte.get(0); Iterator<Case> fIt=ouverte.iterator(); while(fIt.hasNext()){ min=compareF(min, fIt.next()); } return min; } void getParentPath(){ Case curr=this.fin; while(!curr.equals(debut)){ path.add(curr); curr=curr.getParent(); } //path.add(debut); this.go=true; } Case compareF(Case cF1, Case cF2){ if (cF1.getF()<cF2.getF()) return cF1; return cF2; } //********************************Test************************************************// void dessine(){ for(int pl=1;pl<pos.length;pl++){ for(int c=1;c<pos[pl].length;c++){ System.out.print(pos[pl][c]+" "); } System.out.println(); } } void dessineResult(){ System.out.println("*****************"); Iterator<Case> itFerme=path.iterator(); Case fil=null; while(itFerme.hasNext()){ fil=itFerme.next(); pos[fil.getX()][fil.getY()]=8; } System.out.println("*****************"); for(int pl=1;pl<11;pl++){ for(int c=1;c<11;c++){ System.out.print(pos[pl][c]+" "); } System.out.println(); } } public static void main(String[] args) { Case debut=new Case(6,6); Case fin=new Case(1,1); Astar recherche=new Astar(debut,fin); } }

A voir également

Ajouter un commentaire

Commentaires

Messages postés
1
Date d'inscription
mercredi 9 mai 2012
Statut
Membre
Dernière intervention
17 janvier 2013

I'm new how can i download the code! thanks.
Messages postés
1
Date d'inscription
vendredi 11 juin 2010
Statut
Membre
Dernière intervention
10 novembre 2010

Bonsoir,
Je suis une étudiante en 3ém année informatique appliquée à la gestion et j'ai un mini projet sur la complexité algorithmique de A*,je suis entrain de tester beaucoup de codes que je l'ai trouvé en ligne mais j'ai pas pu exécuter ce code sur Eclipse il m'affiche 2 erreurs an niveau de la classe Astar sur les methodes(dessine et dessineResult) ils ne sont pas encore définis?.Pouver vous m'explique ce problème?
Messages postés
8
Date d'inscription
jeudi 28 mars 2002
Statut
Membre
Dernière intervention
15 décembre 2009

salut et désolé d'avoir repondu en retard !!!
en fait le tableau static me servait juste à tester mon programme, tu peux le rendre private non static et supprimer les valeurs que j'ai donné , et passer un autre en argument à la classe de la maniere suivante :
new Astar(taCaseDebut, taCaseFin, tonTableau[][])

voilà j'espere que j'ai repondu à ta question
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Modérateur
Dernière intervention
30 juillet 2012
38
pourquoi tu stoques la map en statique ? imagine je fais du pre calcul, et je veux lancer du calcul de recherche de plus court chemins sur toutes les cases vers toutes les cases sur 10 maps, et ca a l'install d'un jeu par exemple... bah avec ton code on ne peut pas, parce-que la map est static.

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.