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);
}
}
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.