Parcours matrice.

Parcours matrice. - Java - Programmation

Marsh Posté le 02-01-2010 à 00:46:54    

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 !

Reply

Marsh Posté le 02-01-2010 à 00:46:54   

Reply

Marsh Posté le 02-01-2010 à 13:22:42    

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

Reply

Marsh Posté le 02-01-2010 à 13:59:04    

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 :/

Reply

Marsh Posté le 02-01-2010 à 14:17:05    

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.

Reply

Marsh Posté le 02-01-2010 à 18:50:55    

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
Reply

Marsh Posté le 02-01-2010 à 19:16:31    

apaachee a écrit :

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 :/


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

Reply

Marsh Posté le 02-01-2010 à 21:31:17    

Code :
  1. public int eval(char color,int i,int j){
  2.  // System.out.println("----Voici le plateau, on cherche la valeur des points ("+i+","+j+" )------" );
  3.  // this.affichePlateau();
  4.  // System.out.println("----" );
  5.    int result = 0;
  6.    int chemin = 0;
  7.    int optiBas = 100;
  8.    int nbcasestrouvees,no,temI,temJ;
  9.  
  10.    Plateau tempor = new Plateau(nbCases);
  11.    if(color == 'j')
  12.    tempor = this.copieMatrice();
  13.    else{
  14.   tempor = this.rotationMatrice();
  15.   int[] nouveau = cooApresRotation(i,j);
  16.   i = nouveau[0];
  17.   j = nouveau[1];
  18.  }
  19.  
  20.    Stack stackI = new Stack();
  21.    Stack stackJ = new Stack(); 
  22.    Stack somsave = new Stack();
  23.  
  24.    stackI.push(i);
  25.    stackJ.push(j);
  26.    somsave.push(0);
  27.  
  28.    boolean scancomplete = false;
  29.  
  30.    /*CHEMIN BAS*/
  31.     if(j == (nbCases-1)){
  32.   optiBas = 0;
  33.   scancomplete = true;
  34.     }
  35.  
  36.    while(scancomplete == false){
  37.    nbcasestrouvees = 0;
  38.    Integer iCourant = (Integer)stackI.peek();
  39.    Integer jCourant = (Integer)stackJ.peek();
  40.    // System.out.println("-------------" );
  41.    // System.out.println("AfficheStackI" );
  42.    // afficheStack(stackI);
  43.    // System.out.println("--------------" );
  44.    // System.out.println("AffichestackJ" );
  45.    // afficheStack(stackJ);
  46.    // System.out.println("--------------" );
  47.   
  48.    //On cherche les cases à coté de (i,j) étant jaunes ou vierges
  49.    //A droite
  50.    if(iCourant < nbCases-1){ // On évite derniere colonne
  51.    if((tempor.getcase(iCourant+1,jCourant) == color) || (tempor.getcase(iCourant+1,jCourant) == '0')){ // On vérifie que la case = '0' ou 'color'
  52.    if(!dejaPresent(stackI,stackJ,iCourant+1,jCourant)){ // La case n'est pas déja présente dans la pile
  53.       //On a bien une case a droite
  54.       // System.out.println("Case Trouvée a droite" );
  55.       stackI.push(iCourant+1);
  56.       stackJ.push(jCourant);
  57.       nbcasestrouvees++;
  58.    }
  59.    }
  60.    }
  61.    //A gauche
  62.    if(iCourant != 0){
  63.    if((tempor.getcase(iCourant-1,jCourant) == color) || (tempor.getcase(iCourant-1,jCourant) == '0')){
  64.    if(!dejaPresent(stackI,stackJ,iCourant-1,jCourant)){
  65.     // System.out.println("Case Trouvée a gauche" );
  66.       stackI.push(iCourant-1);
  67.       stackJ.push(jCourant);
  68.       nbcasestrouvees++;
  69.    }
  70.    }
  71.    }
  72.    //En haut
  73.    if(jCourant != 0){
  74.    if((tempor.getcase(iCourant,jCourant-1) == color) || (tempor.getcase(iCourant,jCourant-1) == '0')){
  75.    if(!dejaPresent(stackI,stackJ,iCourant,jCourant-1)){
  76.     // System.out.println("Case Trouvée en haut" );
  77.       stackI.push(iCourant);
  78.       stackJ.push(jCourant-1);
  79.       nbcasestrouvees++;
  80.    }
  81.    }
  82.    }
  83.    //En Bas
  84.    if(jCourant < nbCases-1){
  85.    if((tempor.getcase(iCourant,jCourant+1) == color) || (tempor.getcase(iCourant,jCourant+1) == '0')){
  86.    if(!dejaPresent(stackI,stackJ,iCourant,jCourant+1)){
  87.     // System.out.println("Case Trouvée en bas" );
  88.       if(jCourant+1 == nbCases-1){
  89.       nbcasestrouvees = 0;
  90.       chemin = calculnb(stackI,stackJ,somsave);
  91.       // System.out.println("Chemin de "+chemin);
  92.       if(chemin < optiBas)
  93.       optiBas = chemin;
  94.       }
  95.       else{
  97.       stackI.push(iCourant);
  98.       stackJ.push(jCourant+1);
  99.       nbcasestrouvees++;
  100.       }
  101.    }
  102.    }
  103.    }
  104.    // System.out.println("nbcasestrouvees : "+nbcasestrouvees);
  105.    while(nbcasestrouvees > 1){
  106.    somsave.push(nbObj(stackI) - (nbcasestrouvees-1));
  107.    nbcasestrouvees--;
  108.    }
  109.    if(nbcasestrouvees == 0){
  110.    somsave.pop();
  111.    if(somsave.empty())
  112.    scancomplete = true;
  113.    else{
  114.    no = (Integer)somsave.peek();
  115.    while(nbObj(stackI) != (no+1)){
  116.       temI = (Integer)stackI.pop();
  117.       temJ = (Integer)stackJ.pop();
  118.       tempor.setcase(temI,temJ,'-');
  119.    }
  120.    }
  121.    }
  122.    }
  123.  
  124.    /* Chemin HAUT*/
  125.    chemin = 0;
  126.    int optiHaut = 100;
  127.  
  128.    Plateau temp = new Plateau(nbCases);
  129.    if(color == 'j')
  130.    temp = this.copieMatrice();
  131.    else
  132.    temp = this.rotationMatrice();
  133.  
  134.    Stack sstackI = new Stack();
  135.    Stack sstackJ = new Stack(); 
  136.    Stack ssomsave = new Stack();
  137.  
  138.    sstackI.push(i);
  139.    sstackJ.push(j);
  140.    ssomsave.push(0);
  141.  
  142.    scancomplete = false;
  143.  
  144.    if(j == 0){
  145.   scancomplete = true;
  146.   optiHaut = 0;
  147.  }
  148.    while(scancomplete == false){
  149.    nbcasestrouvees = 0;
  150.    Integer siCourant = (Integer)sstackI.peek();
  151.    Integer sjCourant = (Integer)sstackJ.peek();
  152.   
  153.    //On cherche les cases à coté de (i,j) étant jaunes ou vierges
  154.    //En Bas
  155.    if(sjCourant < nbCases-1){
  156.    if((temp.getcase(siCourant,sjCourant+1) == color) || (temp.getcase(siCourant,sjCourant+1) == '0')){
  157.    if(!dejaPresent(sstackI,sstackJ,siCourant,sjCourant+1)){
  159.       sstackI.push(siCourant);
  160.       sstackJ.push(sjCourant+1);
  161.       nbcasestrouvees++;
  162.     
  163.    }
  164.    }
  165.    }
  166.    //A droite
  167.    if(siCourant < nbCases-1){ // On évite derniere colonne
  168.    if((temp.getcase(siCourant+1,sjCourant) == color) || (temp.getcase(siCourant+1,sjCourant) == '0')){ // On vérifie que la case = '0' ou 'color'
  169.    if(!dejaPresent(sstackI,sstackJ,siCourant+1,sjCourant)){ // La case n'est pas déja présente dans la pile
  170.       //On a bien une case a droite
  171.       sstackI.push(siCourant+1);
  172.       sstackJ.push(sjCourant);
  173.       nbcasestrouvees++;
  174.    }
  175.    }
  176.    }
  177.    //A gauche
  178.    if(siCourant != 0){
  179.    if((temp.getcase(siCourant-1,sjCourant) == color) || (temp.getcase(siCourant-1,sjCourant) == '0')){
  180.    if(!dejaPresent(sstackI,sstackJ,siCourant-1,sjCourant)){
  181.       sstackI.push(siCourant-1);
  182.       sstackJ.push(sjCourant);
  183.       nbcasestrouvees++;
  184.    }
  185.    }
  186.    }
  188.    //En haut
  189.    if(sjCourant != 0){
  190.    if((temp.getcase(siCourant,sjCourant-1) == color) || (temp.getcase(siCourant,sjCourant-1) == '0')){
  191.    if(!dejaPresent(sstackI,sstackJ,siCourant,sjCourant-1)){
  192.     if(sjCourant-1 == 0){
  193.       nbcasestrouvees = 0;
  194.       chemin = calculnb(sstackI,sstackJ,ssomsave);
  195.       // System.out.println("Chemin HAUT :"+chemin);
  196.       if(chemin < optiHaut)
  197.       optiHaut = chemin;
  198.       }
  199.       else{
  200.       sstackI.push(siCourant);
  201.       sstackJ.push(sjCourant-1);
  202.       nbcasestrouvees++;
  203.       }
  204.    }
  205.    }
  206.    }
  208.   
  209.    while(nbcasestrouvees > 1){
  210.    ssomsave.push(nbObj(sstackI) - (nbcasestrouvees-1));
  211.    nbcasestrouvees--;
  212.    }
  213.    if(nbcasestrouvees == 0){
  214.    ssomsave.pop();
  215.    if(ssomsave.empty()){
  216.    scancomplete = true;
  217.    // if(optiHaut == 0)
  218.       // optiHaut = -1000;
  219.    }
  220.    else{
  221.    no = (Integer)ssomsave.peek();
  222.    while(nbObj(sstackI) != (no+1)){
  223.       temI = (Integer)sstackI.pop();
  224.       temJ = (Integer)sstackJ.pop();
  225.       temp.setcase(temI,temJ,'-');
  226.    }
  227.    }
  228.    }
  229.    }
  230.  int opti;
  231.  if((optiBas == 0) && (optiHaut == 0))
  232.   opti = -1000;
  233.  else
  234.   opti = (optiBas + optiHaut)*(-1);
  235.  // System.out.println("OptiBas : "+optiBas+" + " );
  236.  // System.out.println("OptiHaut : "+optiHaut+" DONC " );
  237.  
  238.  System.out.println("Opti : "+opti);
  239.  if(opti<-15){
  240.   System.out.println("----Voici le plateau, on cherche la valeur des points ("+i+","+j+" ) Couleur : "+color+"------" );
  241.   temp.affichePlateau();
  242.   System.out.println("----" );
  243.   System.out.println("OptiBas : "+optiBas+" + " );
  244.   System.out.println("OptiHaut : "+optiHaut);
  247.   System.out.println("-----------------------------------------------------------------" );
  248.  }
  249.    return opti;
  250. }


 
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'... :/

Reply

Marsh Posté le 03-01-2010 à 13:14:18    

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.

Reply

Marsh Posté le 04-01-2010 à 00:13:13    

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

Reply

Marsh Posté le 04-01-2010 à 01:09:55    

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 :
  1. -----------------------------------------------------------------------
  2.       --               Resolution du Jeu du Taquin                         --
  3.       -----------------------------------------------------------------------
  4.       procedure Astar (Dans : in out T_Jeu_Du_Taquin) is
  5.       -----------------------------------------------------------------------
  6.       --                      Algorithme A* ou Astar                       --
  7.       -----------------------------------------------------------------------
  8.          Succes : Boolean := Boolean'Value("FALSE" );
  9.          Noeud_Courant : T_Place_Ensemble;
  10.          Nouveau_Successeur : T_Matrice;
  11.       begin
  12.          ajouter(Ensemble => Dans.Ouvert,Avec => Dans.Matrice_melangee);
  13.          Vider(Ensemble => Dans.Ferme);
  14.          while not Est_Vide(Dans.Ouvert) and not Succes loop
  15.             Noeud_courantt := L_Element_Min(Ensemble => Dans.Ouvert).all;
  16.             if -- la j'ai pas le test je comprend plus -- then
  17.               Succes := Boolean'Value("TRUE" );
  18.             else
  19.                Supprimer_noeud(Ensemble => Dans.Ouvert,Avec => Noeud_courant.id);
  20.                ajouter(Ensemble => Dans.Fermer,Nouveau => Noeud_Courant.matrice);
  21.                for I in Mouvement'range loop
  22.                   if (Mouvement(I)
  23.                      (Absisse(Noeud_Courant.Matrice ,0),       -- si mouvement(i) /= 0
  24.                       Ordonnee(Noeud_Courant.Matrice ,0),
  25.                       Noeud_Courant.Matrice) /= 0) then
  26.      
  27.                      -- generer la nouvelle matrice
  28.                      Nouveau_Successeur := Noeud_Courant.Matrice;
  29.                      Permuter(Nouveau_Successeur,
  30.                               Mouvement(I)
  31.                               (Absisse(Nouveau_Successeur ,0),       -- si mouvement(i) /= 0
  32.                                Ordonnee(Nouveau_Successeur ,0),
  33.                                Nouveau_Successeur);
  34.      
  35.      
  36.      
  37.      
  38.                      -- la je pense que l'algo doit varier en fonction de sont utilisation
  39.      
  40.                      if not Esiste(Ensemble => Dans.Ouvert,L_Element => Nouveau_Successeur) and
  41.                        not Esiste(Ensemble => Dans.fermer,L_Element => Nouveau_Successeur) then
  42.                         -- la y a un chmilblic -- on vient de supprimer Noeud_courant de Ouvert est on doit lui ajouter un fils, c'es
  43.     t louche
  44.                         Ajouter(Ensemble => Dans.ferme, Avec =>  Nouveau_Successeur);
  45.                         g(s) := g(n) + coût(n,s);  -- la je sais pas quoi faire de cette ligne
  46.                      elsif (g(s) > g(n) + coût(n,s)) then -- la pareil
  47.                         Ajouter(Ensemble => Dans.Fermer, Avec => Nouveau_Successeur);
  48.                         g(s) = g(n) + coût(n,s);
  49.                         if Existe(Ensemble => Dans.Ferme, L_Element => Nouveau_success)s se trouve dans fermés) then
  50.                            -- la, je comprend plus non plus, on vient de rajouter Nouveau_successeur a ferme et on test s'il y est ?
  51.                            -- le reste, c'est pire donc
  52.                            fermés  = fermés  - S;
  53.                            ouverts = ouverts + S;
  54.                            --
  55.                            -- je doit me planter quelque part !!!!!
  56.                         end if;
  57.                      end if;
  58.                   end if;
  59.                end loop;
  60.      
  61.             end if;
  62.      
  63.          end loop;
  64.      
  65.       -----------------------------------------------------------------------
  66.       --                     Fin algorithme A* ou Astar                    --
  67.       -----------------------------------------------------------------------


 
 
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
Reply

Marsh Posté le 04-01-2010 à 01:09:55   

Reply

Marsh Posté le 04-01-2010 à 01:17:05    

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.

Reply

Marsh Posté le 04-01-2010 à 10:57:37    

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

Reply

Marsh Posté le 05-01-2010 à 14:25:35    

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 :
  1. public int Astar(int idepart, int jdepart, int iarrivee, int jarrivee){
  3.  int resultat;
  5.  Stack LOI = new Stack();//ListeOuverteI
  6.  Stack LOJ = new Stack();//ListeOuverteJ
  7.  Stack LFI = new Stack();//ListeFermeeI
  8.  Stack LFJ = new Stack();//ListeFermeeJ
  10.  Stack tempEucl = new Stack();//Distances Euclidiennes avant tri
  11.  Stack tempI = new Stack();//les i trouves avant tri
  12.  Stack tempJ = new Stack();//les j trouves avant tri
  14.  //On calcule les distances entre "point à proximité du point de départ" et "point d'arrivée"
  15.  double te;
  16.  if(this.caseADroite(idepart,jdepart)){
  17.   te = distanceEuclidienne(idepart+1,jdepart,iarrivee,jarrivee);
  18.   if(this.getcase(idepart+1,jdepart) == '0')//Malus si case vide
  19.    te = te + 5;
  20.   tempEucl.push(te);
  21.   tempI.push(idepart+1);
  22.   tempJ.push(jdepart);
  23.  }
  24.  if(this.caseAGauche(idepart,jdepart)){
  25.   te = distanceEuclidienne(idepart-1,jdepart,iarrivee,jarrivee);
  26.   if(this.getcase(idepart-1,jdepart) == '0')//Malus si case vide
  27.    te = te + 5;
  28.   tempEucl.push(te);
  29.   tempI.push(idepart-1);
  30.   tempJ.push(jdepart);
  31.  }
  32.  if(this.caseEnHaut(idepart,jdepart)){
  33.   te = distanceEuclidienne(idepart,jdepart-1,iarrivee,jarrivee);
  34.   if(this.getcase(idepart,jdepart-1) == '0')//Malus si case vide
  35.    te = te + 5;
  36.   tempEucl.push(te);
  37.   tempI.push(idepart);
  38.   tempJ.push(jdepart-1);
  39.  }
  40.  if(this.caseEnBas(idepart,jdepart)){
  41.   te = distanceEuclidienne(idepart,jdepart+1,iarrivee,jarrivee);
  42.   if(this.getcase(idepart,jdepart+1) == '0')//Malus si case vide
  43.    te = te + 5;
  44.   tempEucl.push(te);
  45.   tempI.push(idepart);
  46.   tempJ.push(jdepart+1);
  47.  }
  49.  //On trie les distances trouvées
  50.  Stack tri = new Stack();
  51.  tri = tri(tempEucl);
  53.  //On ajoute à LOI et LOJ les différentes coordonnées trouvées en fonction de leur distance (plus grosse distance en BAS)
  54.  Stack tempIsave = new Stack();
  55.  Stack tempJsave = new Stack();
  56.  while(!tri.empty()){
  57.   Integer itri = (Integer)tri.pop();
  58.   while(!tempI.empty()){
  59.    if(itri == nbObj(tempI)){
  60.     LOI.push(tempI.peek());
  61.     LOJ.push(tempJ.peek());
  62.    }
  63.    tempIsave.push(tempI.pop());
  64.    tempJsave.push(tempJ.pop());
  65.   }
  66.   while(!tempIsave.empty()){
  67.    tempI.push(tempIsave.pop());
  68.    tempJ.push(tempJsave.pop());
  69.   }
  70.  }
  72.  boolean fin;
  73.  while(fin == false){
  74.   if(LOI.empty()){
  75.    resultat = 1000;
  76.    fin == true;
  77.   }
  78.   else{
  79.    //Case Courante
  80.    int i = LOI.pop();
  81.    int j = LOI.pop();
  83.    //On vide les piles de traitement
  84.    while(!tempEucl.empty())
  85.     tempEucl.pop();
  86.    while(!tri.empty())
  87.     tri.pop();
  88.    while(!tempI.empty()){
  89.     tempI.pop();
  90.     tempJ.pop();
  91.    }
  93.    if((this.caseADroite(i,j)){
  94.     if(!dejaPresent(LFI,LFJ,i+1,j)){
  95.      te = distanceEuclidienne(i+1,j,iarrivee,jarrivee);
  96.      if(this.getcase(i+1,j) == '0')//Malus si case vide
  97.       te = te + 5;
  98.      te += distanceEuclidienne(i,j,iarrivee,jarrivee);
  99.      tempEucl.push(te);
  100.      tempI.push(i+1);
  101.      tempJ.push(j);
  102.     }
  103.    }
  104.    if((this.caseAGauche(i,j)){
  105.     if(!dejaPresent(LFI,LFJ,i-1,j)){
  106.      te = distanceEuclidienne(i-1,j,iarrivee,jarrivee);
  107.      if(this.getcase(i-1,j) == '0')//Malus si case vide
  108.       te = te + 5;
  109.      te += distanceEuclidienne(i,j,iarrivee,jarrivee);
  110.      tempEucl.push(te);
  111.      tempI.push(i-1);
  112.      tempJ.push(j);
  113.     }
  114.    }
  115.    if((this.caseEnHaut(i,j)){
  116.     if(!dejaPresent(LFI,LFJ,i,j-1)){
  117.      te = distanceEuclidienne(i,j-1,iarrivee,jarrivee);
  118.      if(this.getcase(i,j-1) == '0')//Malus si case vide
  119.       te = te + 5;
  120.      te += distanceEuclidienne(i,j,iarrivee,jarrivee);
  121.      tempEucl.push(te);
  122.      tempI.push(i);
  123.      tempJ.push(j-1);
  124.     }
  125.    }
  126.    if((this.caseEnBas(i,j)){
  127.     if(!dejaPresent(LFI,LFJ,i,j)){
  128.      te = distanceEuclidienne(i,j+1,iarrivee,jarrivee);
  129.      if(this.getcase(i,j+1) == '0')//Malus si case vide
  130.       te = te + 5;
  131.      te += distanceEuclidienne(i,j,iarrivee,jarrivee);
  132.      tempEucl.push(te);
  133.      tempI.push(i);
  134.      tempJ.push(j+1);
  135.     }
  136.    }
  138.    // Si la case objectif est atteinte alors aller à solution,
  139.    if(){
  140.     fin = true;
  141.     resultat = solution();
  142.    }
  143.    // sinon :  
  144.    else{
  145.     // empiler les nœuds voisins dans la liste ouverte du moins bon score au meilleur,  
  146.     tri = tri(tempEucl);
  147.     while(!tri.empty()){
  148.      Integer itri = (Integer)tri.pop();
  149.      while(!tempI.empty()){
  150.       if(itri == nbObj(tempI)){
  151.        LOI.push(tempI.peek());
  152.        LOJ.push(tempJ.peek());
  153.       }
  154.       tempIsave.push(tempI.pop());
  155.       tempJsave.push(tempJ.pop());
  156.      }
  157.      while(!tempIsave.empty()){
  158.       tempI.push(tempIsave.pop());
  159.       tempJ.push(tempJsave.pop());
  160.      }
  161.     }
  162.     // empiler le nœud courant dans la liste fermée.
  163.     LFI.push(i);
  164.     LFJ.push(j);
  165.    }
  166.   }
  167.  }
  168.  return resultat;
  169. }

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed