/***************************************************************************
 * 
 *                  NE PAS MODIFIER CETTE SECTION 
 *                  
 **************************************************************************/
import java.awt.*;
import Listes.*;

public class Expresso extends FenetreTortue
{ 
     
/***************************************************************************
 * 
 *                      SECTION MODIFIABLE 
 *                  
 **************************************************************************/
 
 
 
/********************** Parametres de l'interface ************************/

    public static int baseFenetre = 600; // Largeur de la fenêtre
    public static int hauteurFenetre = 500; // Hauteur de la fenêtre
    public static String titreFenetre = "Labyrinthe"; // Titre de la fenêtre
    // Le texte
    public static boolean zoneTexte = true; // Indique si on désire ou non une zone de texte
    // Les boutons
    public static String[] nomsBoutonsLigne1 = {unicode("Cr#eaiger labyrinthe"), unicode("Remise #agra z#eaigro"), "Quitter"}; // Noms des boutons de la ligne 1
    public static String[] nomsBoutonsLigne2 = {unicode("R#eaigsolution en profondeur") , unicode("R#eaigsolution heuristique"), unicode("R#eaigsolution en largeur")}; // Noms des boutons de la ligne 2
    // Les menus
    public static String[] nomsMenus1 = {}; // Exemple: private static String[] nomsMenus1 = {"nomMenu", "nomItem_1", ...};
    public static String[] nomsMenus2 = {}; // Laissez vide si vous ne désirez pas de menu
    public static String[] nomsMenus3 = {};
    public static String[] nomsMenus4 = {};
    public static String[] nomsMenus5 = {};
    public static String[] nomsMenus6 = {};
    public static String[] nomsMenus7 = {};
    public static String[] nomsMenus8 = {};
    
    public static void ajoutDeGlissieres(){
        ajouterGlissiereLigne1("Nombre de cases horizontales", 10,40,30,0);
        ajouterGlissiereLigne1("Nombre de cases verticales", 10,40,30,0);
        ajouterGlissiereLigne1("Pourcentage de murs", 0,100,33,0);
    }

/****************** Initialisation *********************************/
   
    public void initialisation(){
        fixerProportionZoneTexte(0);
    }
    
/****************** Placer vos procedures ici ****************************/

char [][] monLaby;
int dimH, dimV, debutX, debutY, butX, butY;
double deltaX, deltaY, posX, posY, densiteMurs;
boolean labyCree = false, solutionTrouvee = false;

Liste listeChemins; 
int longueurChemin, poidsMax;
int [][] poidsCases;

public void creerLabyrinthe() {
    Color couleur;
    fixeOrigineTortue(largeurZoneGraphique()/2, hauteurZoneGraphique()/2);
    deltaX = (largeurZoneGraphique()-30)/valeurGlissiere(1);
    deltaY = (hauteurZoneGraphique()-30)/valeurGlissiere(2);
    posX = (int) (15 - largeurZoneGraphique()/2);
    posY = (int) (15 - hauteurZoneGraphique()/2);
    dimH = (int) valeurGlissiere(1);
    dimV = (int) valeurGlissiere(2);
    densiteMurs = (int) valeurGlissiere(3);
    videGraphique();
    monLaby = new char[dimH + 1][dimV + 1];
    //grille(cyan);
    for ( int i=1; i<=dimH;i++) {
        for (int j = 1; j<=dimV;j++) {
            if (densiteMurs <= hasard(0,100))
            {couleur = jaune; monLaby[i][j]='L';}
            else
            {couleur = noir; monLaby[i][j]='M';}
            colorerCase(i,j,couleur);
    }}
    int u = hasard(1,dimH); int v = hasard(1,dimV); monLaby[u][v]='D';colorerCase(u,v,bleu);
    do {u = hasard(1,dimH); v = hasard(1,dimV); } while (monLaby[u][v] =='D');
    monLaby[u][v]='A';colorerCase(u,v,rouge); butX = u; butY = v;
    labyCree=true;
    //activerEvenementsSouris();
}

public void reprendreLabyrinthe() {
    if (! labyCree) {return;}
    for(int i = 1; i<=dimH; i++) {
        for (int j=1; j<=dimV;j++) {
            if (monLaby[i][j] == 'V' || monLaby[i][j] == 'L') {monLaby[i][j] = 'L'; colorerCase(i,j,jaune); }
            if (monLaby[i][j] == 'A' ) {colorerCase(i,j,rouge); }}}
        }

public void grille(Color c) {
    couleurCrayon(c);
    for(int i=0;i<=dimH;i++) {segment(posX+i*deltaX, posY, posX+i*deltaX, -posY);};
    for(int i=0;i<=dimV;i++) {segment(posX, posY+i*deltaY, -posX, posY+i*deltaY);};
}

public void segment(double x0, double y0, double x1, double y1) {
    lc(); fixePos(x0,y0);
    bc(); fixePos(x1,y1);
}

public void colorerCase(int i, int j, Color c) {
    rectanglePlein(posX+(i-1)*deltaX+1, posY+(j-1)*deltaY+1, deltaY-2, deltaX-2, c);
}
    
public void rectanglePlein(double x, double y, double hauteur, double base, Color couleur) {
    lc(); fixePos(x,y);
    bc(); cc(cyan);tc(2);
    couleurRemplissage(couleur);
    debutRemplir();  
    av (hauteur); dr(90); av(base); dr(90);av (hauteur); dr(90); av(base); dr(90);
    finRemplir();
}

public int caseX(double x) {
    int cX = (int) ((x-posX)/deltaX + 1);
    if (cX < 1) {cX=1;}
    if (cX > dimH) {cX=dimH;}
    return cX;
}

public int caseY(double y) {
    int cY = (int) ((y-posY)/deltaY + 1);
    if (cY < 1) {cY=1;}
    if (cY > dimV) {cY=dimV;}
    return cY;
}

public void resoudreProfondeur() {
    int departX=0, departY=0;
    if (! labyCree) {return;};
    for(int i = 1; i<=dimH; i++) {
        for (int j=1; j<=dimV;j++) {
            if (monLaby[i][j] == 'D') {departX=i; departY=j; }}}
    monLaby[departX][departY] = 'L'; colorerCase(departX, departY, vert);
    solutionTrouvee = false;
    chercherProfondeur(departX, departY);
    monLaby[departX][departY] = 'D'; colorerCase(departX, departY, bleu);
    if (solutionTrouvee) {message(unicode("R#eaigussi!"));} else {message("Impossible");}; bip();
}

public void chercherProfondeur(int x, int y) {
    char etatCase = monLaby[x][y];
    if (etatCase == 'M' || etatCase == 'V') {return;}
    if (etatCase == 'A') {solutionTrouvee = true; return;}
    colorerCase(x,y,vert); monLaby[x][y] = 'V'; miseAJourGraphique();
    if (x+1 <= dimH && ! solutionTrouvee) {chercherProfondeur(x+1,y);}
    if (y+1 <= dimV && ! solutionTrouvee) {chercherProfondeur(x,y+1);}
    if (x-1 >= 1 && ! solutionTrouvee) {chercherProfondeur(x-1,y);}
    if (y-1 >= 1 && ! solutionTrouvee) {chercherProfondeur(x,y-1);}
    if (! solutionTrouvee) {colorerCase(x,y,grisClair);}
}

public void resoudreHeuristique() {
    int departX=0, departY=0;
    if (! labyCree) {return;};
    for(int i = 1; i<=dimH; i++) {
        for (int j=1; j<=dimV;j++) {
            if (monLaby[i][j] == 'D') {departX=i; departY=j; }}}
    monLaby[departX][departY] = 'L'; colorerCase(departX, departY, vert);
    solutionTrouvee = false;
    chercherHeuristique(departX, departY);
    monLaby[departX][departY] = 'D'; colorerCase(departX, departY, bleu);
    if (solutionTrouvee) {message(unicode("R#eaigussi!"));} else {message("Impossible");}; bip();
}

public void chercherHeuristique(int x, int y) {
    int[] temp;
    char etatCase = monLaby[x][y];
    if (etatCase == 'M' || etatCase == 'V') {return;}
    if (etatCase == 'A') {solutionTrouvee = true; return;}
    colorerCase(x,y,vert); monLaby[x][y] = 'V'; miseAJourGraphique();
    int[][] choix = {{x+1,y,butX-x},{x-1,y,x-butX}, {x,y+1,butY-y}, {x,y-1, y-butY}}; ecrire(choix);
    for(int i=0; i<3; i++) {
        for(int j=i+1; j<4; j++) {
            if (choix[i][2] < choix[j][2]) {temp = choix[i]; choix[i]=choix[j]; choix[j]=temp;}
        }
    } ecrire(choix);
    for (int k=0; k<4; k++) {
        if (! solutionTrouvee && acceptable(choix[k][0], choix[k][1])) {chercherHeuristique(choix[k][0], choix[k][1]);}
    }
    if (! solutionTrouvee) {colorerCase(x,y,grisClair);}
}

public boolean acceptable(int x, int y) {return (1<=x && x<=dimH && 1<=y && y<=dimV);}

public void resoudreLargeur() {
    int departX=0, departY=0;
    if (! labyCree) {return;};
    solutionTrouvee = false;
    longueurChemin = 0;
    poidsMax = dimH*dimV+1;
    poidsCases = new int[dimH+1][dimV+1];
    for (int i=1; i<dimH+1; i++) {
        for (int j=1; j<dimV+1;j++) {
            poidsCases[i][j] = poidsMax;
            if (monLaby[i][j] == 'D') {departX = i; departY = j;}
        }
    }
    monLaby[departX][departY] = 'L'; colorerCase(departX, departY, vert);
    listeChemins = liste(liste(liste(departX, departY)));
    chercherLargeur();
    monLaby[departX][departY] = 'D'; colorerCase(departX, departY, bleu);
    if (solutionTrouvee) 
            {colorerCase(butX,butY,rouge);
              message(unicode("R#eaigussi!"));} 
        else {message("Impossible");}; bip();
}

public void chercherLargeur() {
    Liste chemin = premier(listeChemins);
    int x = valEnt(premier(dernier(chemin)));
    int y = valEnt(dernier(dernier(chemin)));
    char etatCase = monLaby[x][y];
    if (etatCase == 'A') {solutionTrouvee = true; return;}
    ajouterCas (x+1,y, chemin);
    ajouterCas (x-1,y, chemin);
    ajouterCas (x,y+1, chemin);
    ajouterCas (x,y-1, chemin);
    listeChemins = saufPremier(listeChemins);
    if (videP(listeChemins)) {return;}
    effacer (chemin);
    tracer (premier(listeChemins));
    chercherLargeur();
}

public void ajouterCas(int x, int y, Liste chemin) {
    if (x<1 || x>dimH || y< 1 || y>dimV || monLaby[x][y]=='M') {return;}
    if (elementP(liste(x,y),chemin)) {return;}
    if (compte(chemin) >= poidsCases[x][y]) {return;}
    poidsCases[x][y] = compte(chemin);
    listeChemins = metsDernier(metsDernier(liste(x,y),chemin),listeChemins);
}

public void effacer(Liste chemin) {
    int x,y; //ecrisRC(chemin.toString());
    while (! videP(chemin)) {
        x = valEnt(premier(dernier(chemin)));
        y = valEnt(dernier(dernier(chemin)));
        colorerCase(x,y,jaune);
        chemin = saufDernier(chemin);
    }
}

public void tracer(Liste chemin) {
    int x,y; //ecrisRC(chemin.toString());
    if (longueurChemin != compte(chemin)) {longueurChemin = compte(chemin); videTexte(); ecris("Chemins de longueur "+ longueurChemin);}
    while (! videP(chemin)) {
        x = valEnt(premier(premier(chemin)));
        y = valEnt(dernier(premier(chemin)));
        colorerCase(x,y,vert);
        chemin = saufPremier(chemin);}
    //attendre(50);
    miseAJourGraphique();
}

public Liste liste(int x, int y) { return metsPremier(x,metsPremier(y,listeVide()));}

public Liste liste(Liste x, Liste y) { return metsPremier(x,metsPremier(y,listeVide()));}

public Liste liste(Liste x) { return metsPremier(x,listeVide());}


public void ecrire(int[][] truc) {
 for (int i=0; i< truc.length; i++) 
    {for (int j=0; j< truc[0].length; j++) {ecris(truc[i][j]+"   ");} 
    ecrisRC("");}
}

/**************  Les actions des boutons  ************************************/

public void actionBouton1(){
    creerLabyrinthe();
} 

public void actionBouton2(){
    reprendreLabyrinthe();
} 

public void actionBouton3(){
    quitter();
} 

public void actionBouton4(){
    resoudreProfondeur();
}

public void actionBouton5(){
    resoudreHeuristique();
}   

public void actionBouton6(){
   resoudreLargeur();
}

/**************  Les actions des menus  ****************************/

public void actionMenu1Item1(){
   
}

public void actionMenu1Item2(){

}

public void actionMenu1Item3(){
    
}

   
/*************** Les actions des glissieres *********************************/  

  public void actionGlissiere1(double d){
        
    }
    
  
/**************** Les actions de la souris *******************************/
    
    public void clicSouris(double x, double y){
        if (! labyCree) {return;} //---> nŽcessaire si on ne crŽe pas laby au dŽpart
        int u = caseX(x); int v = caseY(y);
        if (monLaby[u][v] == 'L') {monLaby[u][v]='M';colorerCase(u,v,noir); return;}
        if (monLaby[u][v] == 'M') {monLaby[u][v]='L';colorerCase(u,v,jaune); return;}
    }
    
    public void debutGlisser(double x, double y){
        debutX = caseX(x); debutY = caseY(y);
    }
    
    public void finGlisser(double x, double y){
        if (! labyCree) {return;} //---> nŽcessaire si on ne crŽe pas laby au dŽpart
        int u = caseX(x); int v = caseY(y);
        if (monLaby[debutX][debutY] == 'D' && monLaby[u][v] != 'A') {monLaby[debutX][debutY]='L';colorerCase(debutX,debutY,jaune);monLaby[u][v]='D';colorerCase(u,v,bleu);}
        if (monLaby[debutX][debutY] == 'A' && monLaby[u][v] != 'D') 
            {monLaby[debutX][debutY]='L';colorerCase(debutX,debutY,jaune);monLaby[u][v]='A';colorerCase(u,v,rouge); butX = u; butY = v;}
    }
    
    public void glisserEnCours(double x, double y){
        
    }
    
/***************************************************************************
 * 
 *                  NE PAS MODIFIER CETTE SECTION 
 *                  
 **************************************************************************/    
    
    public static String[][] Menus = {nomsMenus1, nomsMenus2, nomsMenus3, nomsMenus4, nomsMenus5, nomsMenus6, nomsMenus7, nomsMenus8};    
    
    public Expresso(int l, int h, String titre, String[] nomsBoutons1, String[] nomsBoutons2, String[][] Menus, boolean avecTexte){
        super(l, h, titre, nomsBoutons1, nomsBoutons2, Menus, avecTexte);
    }
    
    public Expresso() {
        this(baseFenetre, hauteurFenetre, titreFenetre, nomsBoutonsLigne1, nomsBoutonsLigne2, Menus, zoneTexte);
    }
    
    public static void executer(boolean applet){
        initGlissieres();
        ajoutDeGlissieres();
        Expresso maFenetre = new Expresso();
        faireApplet(applet);
        maFenetre.toFront();
        maFenetre.initialisation();
    }
    
    public static void main(String[] args){
        executer(false);
    }

     
}