|
Trouver une ressource
Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum. Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !
PATHFINDING A* ASTAR
Information sur la source
Description
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
- /*******************************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);
-
- }
-
-
-
- }
/*******************************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);
}
}
Historique
- 23 mai 2007 22:20:17 :
- ajout de lien vers un tutorial sur la méthode astar !!!
Sources de la même categorie
Sources en rapport avec celle ci
Commentaires et avis
Discussions en rapport avec ce code source dans le forum
Une IA en Java, pourquoi pas vous ? [ par Globul ]
Salut ! J'aimerai juste signaler à tous les amateurs de programmation en Java l'ouverture d'un site mais aussi et surtout d'un concours visant à la pr
Configuration: java.library.path [ par zebulaon ]
Bonjour,Si qqn pourrait m'indiquer comment on configure la variable d'envirronement afin que le java.library.path soit correct??Quel nom?, comment...M
Recherche d'algorithme de table de hachage [ par jpegg ]
Bonsoir,Je recherche un code source me permettant de coder un programme en Java similaire a gperf. Si quelqu un a une solution, ca m arrangerait bien.
Path avec winXP [ par AlphaSurfeur ]
Bonjour à tous,Je programme avec Forte for java. Jusque la, pas de probleme, sauf que si je veux compiler sous le dos avec javac, le path pour mon jdk
Gros pb avec les JAR [ par Wood_lord ]
Voilà g une applet fonctionnant en java3d ainsi ayant besoin de beaucoup de fichiers (des .obj pour les modèles 3D, des .gif pour les textures et enfi
algorithme de l'ombre portée [ par EulaSky ]
salut tout le monde!je suis en train de programmer un peu de filtres en java mais je réussi pas à trouver l'algorithme de l'ombre portée. cad insérer
Algorithme de la rotation d'une image [ par EulaSky ]
voila je cherche l'algorithme de la rotation d'images... je veux pas utiliser celui fourni dans les librairies de java... vous avez pas un petit lien?
comparer deux algorithme ( Mathematique) [ par olidong ]
salut les amis ,j´essaye d´écrire deux algorithme:1. Décomposition en valeurs singulières (SVD)2. Tikhonov regularisation pour resoudre les "ill posed
Chat avec l'ordi (IA) [ par dufour137 ]
Voilà, après avoir vu dans un magazine "pour la Science" un article sur l'intelligence artificielle, je me suis dis qu'il serait seper de développer m
Path d'une classe en string [ par Thundrax ]
Vous allez me prendre pour un fou mais j'ai besoin du path d'ou se trouve ma classe (sans la définir en dur).Alors ma combine actuel c'est :==========
|
Téléchargements
Logiciels à télécharger sur le même thème :
|