Java

Parcours matrice.

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : Parcours matrice.

apaachee

Bonjour à tous ceux qui prendront la peine de lire mes peines... ^^

Je possède une matrice de char constituée de 0 , 'r' , ou 'j'. ('r' = pions rouges et 'j' = pions jaunes, '0' = cases vierges).

Je dévellope une IA pour un jeu et j'ai besoin de connaitre le chemin le plus court entre un point (i,j) et le bas ou le haut de ma matrice.

En sachant que si je calcule pour les jaunes, les points 'r' sont infranchissables, les points 'j' sont de poids nul et les points '0' sont de cout 1.

Les déplacements autorisés sont nord,sud,est,ouest.

Je ne pose pas de question sur ce forum sans connaissance de cause, cela fait bientôt 5h que je me renseigne sur les algo de Djiksttra et A*, sans trouver quelque chose de concluant pour mon cas particulier, je n'y comprend pas grand chose.

Merci !

Publicité

Profil supprimé

Portant A star va bien pour faire ce que tu souhaites.

apaachee

Merci de ta réponse =) En fait je sais que Astar est parfait pour mon cas, mais je n'ai aucune idée de comment l'implémenter simplement pour ma matrice toute bête

Profil supprimé

Ben t'écris tes heuristique et tu les file à A star.

C'est quoi qui te pose problème, java, a star, ou les heuristique.
j'y connais rien en java et j'écrirais pas les heuristique pour toi.
Par contre je peux me replonger dans A star et te filer un coup de pouce.

apaachee

Le mot heuristique m'est étranger Ce qui me pose souci c'est que je connais pas l'algorithme A*, les très nombreux sites que j'ai lu dessus sont un peu complexes pour moi et je ne sais pas comment transformer ma matrice en graphe

Message cité 1 fois

Profil supprimé

apaachee a écrit :

Moi non plus !
Alors là, il faut que t'attende une autre âme charitable parce que je sais faire, mais pas expliquer.

apaachee

Code :

public int eval(char color,int i,int j){
// System.out.println("----Voici le plateau, on cherche la valeur des points ("+i+","+j+" )------" );
// this.affichePlateau();
// System.out.println("----" );
int result = 0;
int chemin = 0;
int optiBas = 100;
int nbcasestrouvees,no,temI,temJ;
Plateau tempor = new Plateau(nbCases);
if(color == 'j')
tempor = this.copieMatrice();
else{
tempor = this.rotationMatrice();
int[] nouveau = cooApresRotation(i,j);
i = nouveau[0];
j = nouveau[1];
}
Stack stackI = new Stack();
Stack stackJ = new Stack();
Stack somsave = new Stack();
stackI.push(i);
stackJ.push(j);
somsave.push(0);
boolean scancomplete = false;
/*CHEMIN BAS*/
if(j == (nbCases-1)){
optiBas = 0;
scancomplete = true;
}
while(scancomplete == false){
nbcasestrouvees = 0;
Integer iCourant = (Integer)stackI.peek();
Integer jCourant = (Integer)stackJ.peek();
// System.out.println("-------------" );
// System.out.println("AfficheStackI" );
// afficheStack(stackI);
// System.out.println("--------------" );
// System.out.println("AffichestackJ" );
// afficheStack(stackJ);
// System.out.println("--------------" );
//On cherche les cases à coté de (i,j) étant jaunes ou vierges
//A droite
if(iCourant < nbCases-1){ // On évite derniere colonne
if((tempor.getcase(iCourant+1,jCourant) == color) || (tempor.getcase(iCourant+1,jCourant) == '0')){ // On vérifie que la case = '0' ou 'color'
if(!dejaPresent(stackI,stackJ,iCourant+1,jCourant)){ // La case n'est pas déja présente dans la pile
//On a bien une case a droite
// System.out.println("Case Trouvée a droite" );
stackI.push(iCourant+1);
stackJ.push(jCourant);
nbcasestrouvees++;
}
}
}
//A gauche
if(iCourant != 0){
if((tempor.getcase(iCourant-1,jCourant) == color) || (tempor.getcase(iCourant-1,jCourant) == '0')){
if(!dejaPresent(stackI,stackJ,iCourant-1,jCourant)){
// System.out.println("Case Trouvée a gauche" );
stackI.push(iCourant-1);
stackJ.push(jCourant);
nbcasestrouvees++;
}
}
}
//En haut
if(jCourant != 0){
if((tempor.getcase(iCourant,jCourant-1) == color) || (tempor.getcase(iCourant,jCourant-1) == '0')){
if(!dejaPresent(stackI,stackJ,iCourant,jCourant-1)){
// System.out.println("Case Trouvée en haut" );
stackI.push(iCourant);
stackJ.push(jCourant-1);
nbcasestrouvees++;
}
}
}
//En Bas
if(jCourant < nbCases-1){
if((tempor.getcase(iCourant,jCourant+1) == color) || (tempor.getcase(iCourant,jCourant+1) == '0')){
if(!dejaPresent(stackI,stackJ,iCourant,jCourant+1)){
// System.out.println("Case Trouvée en bas" );
if(jCourant+1 == nbCases-1){
nbcasestrouvees = 0;
chemin = calculnb(stackI,stackJ,somsave);
// System.out.println("Chemin de "+chemin);
if(chemin < optiBas)
optiBas = chemin;
}
else{
stackI.push(iCourant);
stackJ.push(jCourant+1);
nbcasestrouvees++;
}
}
}
}
// System.out.println("nbcasestrouvees : "+nbcasestrouvees);
while(nbcasestrouvees > 1){
somsave.push(nbObj(stackI) - (nbcasestrouvees-1));
nbcasestrouvees--;
}
if(nbcasestrouvees == 0){
somsave.pop();
if(somsave.empty())
scancomplete = true;
else{
no = (Integer)somsave.peek();
while(nbObj(stackI) != (no+1)){
temI = (Integer)stackI.pop();
temJ = (Integer)stackJ.pop();
tempor.setcase(temI,temJ,'-');
}
}
}
}
/* Chemin HAUT*/
chemin = 0;
int optiHaut = 100;
Plateau temp = new Plateau(nbCases);
if(color == 'j')
temp = this.copieMatrice();
else
temp = this.rotationMatrice();
Stack sstackI = new Stack();
Stack sstackJ = new Stack();
Stack ssomsave = new Stack();
sstackI.push(i);
sstackJ.push(j);
ssomsave.push(0);
scancomplete = false;
if(j == 0){
scancomplete = true;
optiHaut = 0;
}
while(scancomplete == false){
nbcasestrouvees = 0;
Integer siCourant = (Integer)sstackI.peek();
Integer sjCourant = (Integer)sstackJ.peek();
//On cherche les cases à coté de (i,j) étant jaunes ou vierges
//En Bas
if(sjCourant < nbCases-1){
if((temp.getcase(siCourant,sjCourant+1) == color) || (temp.getcase(siCourant,sjCourant+1) == '0')){
if(!dejaPresent(sstackI,sstackJ,siCourant,sjCourant+1)){
sstackI.push(siCourant);
sstackJ.push(sjCourant+1);
nbcasestrouvees++;
}
}
}
//A droite
if(siCourant < nbCases-1){ // On évite derniere colonne
if((temp.getcase(siCourant+1,sjCourant) == color) || (temp.getcase(siCourant+1,sjCourant) == '0')){ // On vérifie que la case = '0' ou 'color'
if(!dejaPresent(sstackI,sstackJ,siCourant+1,sjCourant)){ // La case n'est pas déja présente dans la pile
//On a bien une case a droite
sstackI.push(siCourant+1);
sstackJ.push(sjCourant);
nbcasestrouvees++;
}
}
}
//A gauche
if(siCourant != 0){
if((temp.getcase(siCourant-1,sjCourant) == color) || (temp.getcase(siCourant-1,sjCourant) == '0')){
if(!dejaPresent(sstackI,sstackJ,siCourant-1,sjCourant)){
sstackI.push(siCourant-1);
sstackJ.push(sjCourant);
nbcasestrouvees++;
}
}
}
//En haut
if(sjCourant != 0){
if((temp.getcase(siCourant,sjCourant-1) == color) || (temp.getcase(siCourant,sjCourant-1) == '0')){
if(!dejaPresent(sstackI,sstackJ,siCourant,sjCourant-1)){
if(sjCourant-1 == 0){
nbcasestrouvees = 0;
chemin = calculnb(sstackI,sstackJ,ssomsave);
// System.out.println("Chemin HAUT :"+chemin);
if(chemin < optiHaut)
optiHaut = chemin;
}
else{
sstackI.push(siCourant);
sstackJ.push(sjCourant-1);
nbcasestrouvees++;
}
}
}
}
while(nbcasestrouvees > 1){
ssomsave.push(nbObj(sstackI) - (nbcasestrouvees-1));
nbcasestrouvees--;
}
if(nbcasestrouvees == 0){
ssomsave.pop();
if(ssomsave.empty()){
scancomplete = true;
// if(optiHaut == 0)
// optiHaut = -1000;
}
else{
no = (Integer)ssomsave.peek();
while(nbObj(sstackI) != (no+1)){
temI = (Integer)sstackI.pop();
temJ = (Integer)sstackJ.pop();
temp.setcase(temI,temJ,'-');
}
}
}
}
int opti;
if((optiBas == 0) && (optiHaut == 0))
opti = -1000;
else
opti = (optiBas + optiHaut)*(-1);
// System.out.println("OptiBas : "+optiBas+" + " );
// System.out.println("OptiHaut : "+optiHaut+" DONC " );
System.out.println("Opti : "+opti);
if(opti<-15){
System.out.println("----Voici le plateau, on cherche la valeur des points ("+i+","+j+" ) Couleur : "+color+"------" );
temp.affichePlateau();
System.out.println("----" );
System.out.println("OptiBas : "+optiBas+" + " );
System.out.println("OptiHaut : "+optiHaut);
System.out.println("-----------------------------------------------------------------" );
}
return opti;
}

J'ai fait un algo (assez lourd j'en conviens) pour le problème que dois traiter. En bref je cherche le chemin le plus court du point (i,j) au bas de la matrice, puis au haut. Etant au coeur du problème depuis maintenant une 20e d'heure, mes explications peuvent paraître légères, si besoin de détailler quelquechose j'y suis tout disposé !

J'ai l'impression qu'il ne marche pas sur les cases 'enfermées'...

Profil supprimé

Salut,

T'as tout mis en vrac, j'ai pas l'habitude de java, j'arrive pas à lire.
Ce que je sais c'est que a star fais une 30aine de lignes avec Java.
Avec Ada aussi par ailleurs.

apaachee

Hmm la je bloque vraiment avec mon algo interminable. On commence par ou pour A* et ma matrice ? =)

Profil supprimé

Ca c'est A *

Algorithme A-étoile

Début
ouverts = { état initial }
fermés = vide
succès = faux
Tant que (ouverts non vide) et (non succès) faire
choisir n dans les ouverts tel que f(n) est minimum
Si est_final(n) Alors succès=vrai
Sinon ouverts = ouverts privé de n
fermés = fermés + n
Pour chaque successeurs s de n faire
Si (s n'est ni dans ouverts ni dans fermés)
Alors
ouverts = ouverts + s
père(s) = n
g(s) = g(n) + coût(n,s)
Sinon
Si (g(s) > g(n) + coût(n,s)) Alors
père(s) = n
g(s) = g(n) + coût(n,s)
Si (s se trouve dans fermés) Alors
fermés = fermés - s
ouverts = ouverts + s
Fin si
Fin si
Fin si
Fin pour
Fin si
Fin TQ
Fin

Ca c'est une vue de l'implémentation avec le langage Ada, je l'ai tradui du code java.

Code :

-----------------------------------------------------------------------
      --               Resolution du Jeu du Taquin                         --
      -----------------------------------------------------------------------
      procedure Astar (Dans : in out T_Jeu_Du_Taquin) is
      -----------------------------------------------------------------------
      --                      Algorithme A* ou Astar                       --
      -----------------------------------------------------------------------
         Succes : Boolean := Boolean'Value("FALSE" );
         Noeud_Courant : T_Place_Ensemble;
         Nouveau_Successeur : T_Matrice;
      begin
         ajouter(Ensemble => Dans.Ouvert,Avec => Dans.Matrice_melangee);
         Vider(Ensemble => Dans.Ferme);
         while not Est_Vide(Dans.Ouvert) and not Succes loop
            Noeud_courantt := L_Element_Min(Ensemble => Dans.Ouvert).all;
            if -- la j'ai pas le test je comprend plus -- then
              Succes := Boolean'Value("TRUE" );
            else
               Supprimer_noeud(Ensemble => Dans.Ouvert,Avec => Noeud_courant.id);
               ajouter(Ensemble => Dans.Fermer,Nouveau => Noeud_Courant.matrice);
               for I in Mouvement'range loop
                  if (Mouvement(I)
                     (Absisse(Noeud_Courant.Matrice ,0),       -- si mouvement(i) /= 0
                      Ordonnee(Noeud_Courant.Matrice ,0),
                      Noeud_Courant.Matrice) /= 0) then
     
                     -- generer la nouvelle matrice
                     Nouveau_Successeur := Noeud_Courant.Matrice;
                     Permuter(Nouveau_Successeur,
                              Mouvement(I)
                              (Absisse(Nouveau_Successeur ,0),       -- si mouvement(i) /= 0
                               Ordonnee(Nouveau_Successeur ,0),
                               Nouveau_Successeur);
     
     
     
     
                     -- la je pense que l'algo doit varier en fonction de sont utilisation
     
                     if not Esiste(Ensemble => Dans.Ouvert,L_Element => Nouveau_Successeur) and
                       not Esiste(Ensemble => Dans.fermer,L_Element => Nouveau_Successeur) then
                        -- la y a un chmilblic -- on vient de supprimer Noeud_courant de Ouvert est on doit lui ajouter un fils, c'es
    t louche
                        Ajouter(Ensemble => Dans.ferme, Avec =>  Nouveau_Successeur);
                        g(s) := g(n) + coût(n,s);  -- la je sais pas quoi faire de cette ligne
                     elsif (g(s) > g(n) + coût(n,s)) then -- la pareil
                        Ajouter(Ensemble => Dans.Fermer, Avec => Nouveau_Successeur);
                        g(s) = g(n) + coût(n,s);
                        if Existe(Ensemble => Dans.Ferme, L_Element => Nouveau_success)s se trouve dans fermés) then
                           -- la, je comprend plus non plus, on vient de rajouter Nouveau_successeur a ferme et on test s'il y est ?
                           -- le reste, c'est pire donc
                           fermés  = fermés  - S;
                           ouverts = ouverts + S;
                           --
                           -- je doit me planter quelque part !!!!!
                        end if;
                     end if;
                  end if;
               end loop;
     
            end if;
     
         end loop;
     
      -----------------------------------------------------------------------
      --                     Fin algorithme A* ou Astar                    --
      -----------------------------------------------------------------------

De mémoire, il est quasi correcte, si non, je me ferait taper sur les doigts.

Message édité par Profil supprimé le 04-01-2010 à 01:10:16

Publicité

Profil supprimé

A non, le code Ada est un mélange avec du pseudo code...

il faut savoir de quoi il s'agit, c'est un jeu du taquin.

Les ligne commentées sont les instruction Ada manquante dans l'implémentation, je vais tenter de récupérer mieux.

apaachee

Merci beaucoup pour ce début, je planche dessus cet après-midi !

apaachee

Voila mon Astar. Ce qui me chagrine dans cet algo c'est qu'il ne prend pas en compte la valeur des cases. si 6 cases sont gratuites en allant voir un peu plus haut il ne le verra pas, comment faire ?

Code :

public int Astar(int idepart, int jdepart, int iarrivee, int jarrivee){
int resultat;
Stack LOI = new Stack();//ListeOuverteI
Stack LOJ = new Stack();//ListeOuverteJ
Stack LFI = new Stack();//ListeFermeeI
Stack LFJ = new Stack();//ListeFermeeJ
Stack tempEucl = new Stack();//Distances Euclidiennes avant tri
Stack tempI = new Stack();//les i trouves avant tri
Stack tempJ = new Stack();//les j trouves avant tri
//On calcule les distances entre "point à proximité du point de départ" et "point d'arrivée"
double te;
if(this.caseADroite(idepart,jdepart)){
te = distanceEuclidienne(idepart+1,jdepart,iarrivee,jarrivee);
if(this.getcase(idepart+1,jdepart) == '0')//Malus si case vide
te = te + 5;
tempEucl.push(te);
tempI.push(idepart+1);
tempJ.push(jdepart);
}
if(this.caseAGauche(idepart,jdepart)){
te = distanceEuclidienne(idepart-1,jdepart,iarrivee,jarrivee);
if(this.getcase(idepart-1,jdepart) == '0')//Malus si case vide
te = te + 5;
tempEucl.push(te);
tempI.push(idepart-1);
tempJ.push(jdepart);
}
if(this.caseEnHaut(idepart,jdepart)){
te = distanceEuclidienne(idepart,jdepart-1,iarrivee,jarrivee);
if(this.getcase(idepart,jdepart-1) == '0')//Malus si case vide
te = te + 5;
tempEucl.push(te);
tempI.push(idepart);
tempJ.push(jdepart-1);
}
if(this.caseEnBas(idepart,jdepart)){
te = distanceEuclidienne(idepart,jdepart+1,iarrivee,jarrivee);
if(this.getcase(idepart,jdepart+1) == '0')//Malus si case vide
te = te + 5;
tempEucl.push(te);
tempI.push(idepart);
tempJ.push(jdepart+1);
}
//On trie les distances trouvées
Stack tri = new Stack();
tri = tri(tempEucl);
//On ajoute à LOI et LOJ les différentes coordonnées trouvées en fonction de leur distance (plus grosse distance en BAS)
Stack tempIsave = new Stack();
Stack tempJsave = new Stack();
while(!tri.empty()){
Integer itri = (Integer)tri.pop();
while(!tempI.empty()){
if(itri == nbObj(tempI)){
LOI.push(tempI.peek());
LOJ.push(tempJ.peek());
}
tempIsave.push(tempI.pop());
tempJsave.push(tempJ.pop());
}
while(!tempIsave.empty()){
tempI.push(tempIsave.pop());
tempJ.push(tempJsave.pop());
}
}
boolean fin;
while(fin == false){
if(LOI.empty()){
resultat = 1000;
fin == true;
}
else{
//Case Courante
int i = LOI.pop();
int j = LOI.pop();
//On vide les piles de traitement
while(!tempEucl.empty())
tempEucl.pop();
while(!tri.empty())
tri.pop();
while(!tempI.empty()){
tempI.pop();
tempJ.pop();
}
if((this.caseADroite(i,j)){
if(!dejaPresent(LFI,LFJ,i+1,j)){
te = distanceEuclidienne(i+1,j,iarrivee,jarrivee);
if(this.getcase(i+1,j) == '0')//Malus si case vide
te = te + 5;
te += distanceEuclidienne(i,j,iarrivee,jarrivee);
tempEucl.push(te);
tempI.push(i+1);
tempJ.push(j);
}
}
if((this.caseAGauche(i,j)){
if(!dejaPresent(LFI,LFJ,i-1,j)){
te = distanceEuclidienne(i-1,j,iarrivee,jarrivee);
if(this.getcase(i-1,j) == '0')//Malus si case vide
te = te + 5;
te += distanceEuclidienne(i,j,iarrivee,jarrivee);
tempEucl.push(te);
tempI.push(i-1);
tempJ.push(j);
}
}
if((this.caseEnHaut(i,j)){
if(!dejaPresent(LFI,LFJ,i,j-1)){
te = distanceEuclidienne(i,j-1,iarrivee,jarrivee);
if(this.getcase(i,j-1) == '0')//Malus si case vide
te = te + 5;
te += distanceEuclidienne(i,j,iarrivee,jarrivee);
tempEucl.push(te);
tempI.push(i);
tempJ.push(j-1);
}
}
if((this.caseEnBas(i,j)){
if(!dejaPresent(LFI,LFJ,i,j)){
te = distanceEuclidienne(i,j+1,iarrivee,jarrivee);
if(this.getcase(i,j+1) == '0')//Malus si case vide
te = te + 5;
te += distanceEuclidienne(i,j,iarrivee,jarrivee);
tempEucl.push(te);
tempI.push(i);
tempJ.push(j+1);
}
}
// Si la case objectif est atteinte alors aller à solution,
if(){
fin = true;
resultat = solution();
}
// sinon :
else{
// empiler les nœuds voisins dans la liste ouverte du moins bon score au meilleur,
tri = tri(tempEucl);
while(!tri.empty()){
Integer itri = (Integer)tri.pop();
while(!tempI.empty()){
if(itri == nbObj(tempI)){
LOI.push(tempI.peek());
LOJ.push(tempJ.peek());
}
tempIsave.push(tempI.pop());
tempJsave.push(tempJ.pop());
}
while(!tempIsave.empty()){
tempI.push(tempIsave.pop());
tempJ.push(tempJsave.pop());
}
}
// empiler le nœud courant dans la liste fermée.
LFI.push(i);
LFJ.push(j);
}
}
}
return resultat;
}

FORUM HardWare.fr

Programmation

Java

Parcours matrice.

Sujets relatifs
Exporter en csv une matrice stockée en base	Type de donnée abtrait : Matrice
[C] [resolu] lecture matrice alloué dynamiquement	[Résolu] Tri d'une matrice
[C] pb pour passer une matrice en parametre d'un fonction	Allocation de matrice 3D pondérée
recherche matrice php	Adressage de matrice, performances
produit des matrice en vba	Parcours Arborescence
Plus de sujets relatifs à : Parcours matrice.

Page générée en 0.162 secondes