/*
 *
 * Copyright (C) 2008 Fontaine Clément
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 2 of the License, or
 * (at your option) any later version.
 *
 * this program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <http://www.gnu.org/licenses/>.
 *
 */

#include "ia.h"

void chemin(hauteur altitude, hauteur *hauteur, coordonnees depart, coordonnees arrivee)
{
        coordonnees positionActuelle = depart;
        coordonnees positionPere = depart;
        liste listeOuverte = {NULL, NULL, 0};
        liste listeFermee = {NULL, NULL, 0};
        contenu *contenu = NULL;
        int signe, a = 0, pos;
        
        printf("\n--------- Calculs graphe avec l'algorithme A* (A-Star), affichage des données dans 2 secondes. ---------\n\n");
        sleep(2);
        
        /* on met la case de départ dans la liste ouverte */
        contenu = listeAjouterFin(&listeOuverte, sizeof(contenu));
        contenu->actuelle = depart;
        contenu->parent = depart;
        contenu->G = 20;
        contenu->H = calculH(depart, arrivee);
        contenu->F = contenu->G + contenu->H;
        
        printf("case de depart dans la liste ouverte : actuelle = [%d,%d], parent = [%d,%d], F = %d, G = %d, H = %d.\n", contenu->actuelle.x, contenu->actuelle.y, contenu->parent.x, contenu->parent.y, contenu->F, contenu->G, contenu->H);
        
        /* on s'arrête si l'ont ajoute la case d'arrivée dans la liste fermée */
        while(1)
        {
                printf("\n--- %d %s ---\n", a, (a > 1) ? "iterations" : "iteration");
                /* le poids le plus petit dans la liste ouverte sera la case actuelle */
                /* je la met dans le liste fermée */
                contenu = listeAjouterFin(&listeFermee, sizeof(contenu));
                *contenu = poidPlusFaible(listeOuverte);
                positionActuelle = contenu->actuelle;
                positionPere = positionActuelle;
                
                printf("Plus petit poids de la liste ouverte : %d.\n", contenu->F);
                printf("Position actuelle = [%d,%d].\n", positionActuelle.x, positionActuelle.y);
                /* j'analyse les 8 cases adjacentes à la case actuelle */
                for(signe = -1; signe <= 1; signe += 2)
                {
                        calculCase(altitude, hauteur, &listeOuverte, &listeFermee,
                        positionActuelle.x + signe, positionActuelle.y + signe, positionPere, arrivee);
                        calculCase(altitude, hauteur, &listeOuverte, &listeFermee,
                        positionActuelle.x, positionActuelle.y + signe, positionPere, arrivee);
                        calculCase(altitude, hauteur, &listeOuverte, &listeFermee,
                        positionActuelle.x + signe, positionActuelle.y - signe, positionPere, arrivee);
                        calculCase(altitude, hauteur, &listeOuverte, &listeFermee,
                        positionActuelle.x + signe, positionActuelle.y, positionPere, arrivee);
                }
                if((positionActuelle.x == arrivee.x) && (positionActuelle.y == arrivee.y))
                {
                        break;
                }
                a++;
                /* on l'enlève de la liste ouverte */
                pos = trouverListeCoordonnees(positionActuelle, listeOuverte);
                listeSupprimer(&listeOuverte, pos);
        }
        
        printf("\n--- Retour dans 2 secondes ---\n");
        sleep(2);
        
        retour(hauteur, listeOuverte, listeFermee, depart, arrivee);
        
        listeSupprimerTout(&listeOuverte);
        listeSupprimerTout(&listeFermee);
}

void retour(hauteur *hauteur, liste listeOuverte, liste listeFermee, coordonnees depart, coordonnees arrivee)
{
        coordonnees actuelle = arrivee, parent;
        int pos, *valeur;
        contenu *contenu;
        
        while((actuelle.x != depart.x) || (actuelle.y != depart.y))
        {
                valeur = tableauValeur(*hauteur, actuelle);
                *valeur = 1;
                
                pos = trouverListeCoordonnees(actuelle, listeFermee);
                contenu = listeValeur(listeFermee, pos);
                parent = contenu->parent;
                printf("F = %d, actuelle = [%d,%d], parent = [%d,%d].\n", contenu->F, actuelle.x, actuelle.y, parent.x, parent.y);
                actuelle = parent;
        }
        actuelle.x = 0;
        actuelle.y = 0;
        valeur = tableauValeur(*hauteur, actuelle);
        *valeur = 1;
}

contenu poidPlusFaible(liste liste)
{
        contenu *p_courant = NULL;
        contenu courant;
        int taille = liste.taille;
        int i, max = 999999999;
        int retour, j = 0;
        
        /* on analyse toute la liste */
        for(i = 0; i < taille; i++)
        {
                p_courant = listeValeur(liste, i);
                retour = p_courant->F;
                
                /* si on a trouvé un poid plus faible */
                if(retour < max)
                {
                        courant = *p_courant;
                        max = retour;
                }
        }
        return courant;
}

int calculH(coordonnees actuelle, coordonnees arrivee)
{
        int resultat = 2;
        
        /* calcul la longueur */
        if(actuelle.x < arrivee.x)
                resultat += arrivee.x - actuelle.x;
        else
                resultat += actuelle.x - arrivee.x;
        
        /* calcul la hauteur */
        if(actuelle.y < arrivee.y)
                resultat += arrivee.y - actuelle.y;
        else
                resultat += actuelle.y - arrivee.y;
        
        return resultat; /* retourne la distance à vol d'oiseau */
}

int calculG(hauteur altitude, coordonnees actuelle, coordonnees parent, int facteur)
{
        int G;
        int *altitudeActuelle, *altitudeParent;
        int delta;
        
        /* si l'ont est en diagonal par rapport à la case parent */
        if((actuelle.x != parent.x) && (actuelle.y != parent.y))
        {
                G = 11;
        }
        else
        {
                G = 10;
        }
        altitudeActuelle = tableauValeur(altitude, actuelle);
        altitudeParent = tableauValeur(altitude, parent);
        
        delta = *altitudeParent - *altitudeActuelle;
        
        /* si le chiffre est negatif, on le rend positif */
        if(delta < 0)
        {
                delta = delta - delta - delta;
        }
        delta *= facteur;
        G += delta;
        
        return G;
}

void calculCase(hauteur altitude, hauteur *hauteur, liste *listeOuverte, liste *listeFermee, int x, int y, coordonnees parent, coordonnees arrivee)
{
        int G, siListeOuverte, siListeFermee;
        coordonnees actuelle = {x, y};
        contenu *contenu, *p_contenu;
        int *test;
        
        printf("Case adjacente = [%d,%d] : ", x, y);
        /* si elle est dans la grille */
        if((x >= 0) && (x < altitude.taille.x) && (y >= 0) && (y < altitude.taille.y))
        {
                /* ce n'est pas un obstacle */
                test = tableauValeur(*hauteur, actuelle);
                if((*test) != -1)
                {
                        siListeOuverte = trouverListeCoordonnees(actuelle, *listeOuverte);
                        siListeFermee = trouverListeCoordonnees(actuelle, *listeFermee);
                        
                        /* si elle n'est pas dans la liste fermée */
                        if(siListeFermee == -1)
                        {
                                /* la case n'est pas dans la liste ouverte */
                                if(siListeOuverte == -1)
                                {
                                        contenu = listeAjouterFin(listeOuverte, sizeof(contenu));
                                        contenu->actuelle = actuelle;
                                        contenu->parent = parent;
                                        contenu->H = calculH(actuelle, arrivee);
                                        contenu->G = calculG(altitude, actuelle, parent, 1);
                                        contenu->F = contenu->G + contenu->H;
                                        printf("actuelle = [%d,%d], parent = [%d,%d], F = %d, G = %d, H = %d.\n", contenu->actuelle.x, contenu->actuelle.y, contenu->parent.x, contenu->parent.y, contenu->F, contenu->G, contenu->H);
                                }
                                else
                                {
                                        p_contenu = listeValeur(*listeOuverte, siListeOuverte);
                                        /* on vérifie si un nouveau G sera plus faible */
                                        G = calculG(altitude, actuelle, parent, 1);
                                        
                                        if(G < p_contenu->G)
                                        {
                                                p_contenu->parent = parent;
                                                p_contenu->G = G;
                                                p_contenu->F = p_contenu->H + p_contenu->G;
                                        }
                                        printf("recalcul de F et G.\n");
                                }
                        }
                        else
                        {
                                printf("dans la liste fermée.\n");
                        }
                }
                else
                {
                        printf("un obstacle.\n");
                }
        }
        else
        {
                printf("pas dans le graphe.\n");
        }
}

void afficherGraphe(hauteur altitude, hauteur hauteur)
{
        int *contenu;
        coordonnees taille;
        
        glBegin(GL_QUADS);
        
        for(taille.y = 0; taille.y < altitude.taille.y; taille.y++)
        {
                for(taille.x = 0; taille.x < altitude.taille.x; taille.x++)
                {
                        contenu = tableauValeur(hauteur, taille);
                        
                        switch(*contenu)
                        {
                                case 0:
                                        glColor3ub(0, 0, 255);
                                        break;
                                
                                case -1:
                                        glColor3ub(255, 0, 0);
                                        break;
                                
                                case 1:
                                        glColor3ub(0, 255, 0);
                                        break;
                        }
                        contenu = tableauValeur(altitude, taille);
                        
                        /* base */
                        glVertex3d(taille.x, taille.y, *contenu);
                        glVertex3d(taille.x + TAILLE_CARRE, taille.y, *contenu);
                        glVertex3d(taille.x + TAILLE_CARRE, taille.y + TAILLE_CARRE, *contenu);
                        glVertex3d(taille.x, taille.y + TAILLE_CARRE, *contenu);
                        
                        /* cotés */
                        glColor3ub(255, 0, 255);
                        glVertex3d(taille.x, taille.y + TAILLE_CARRE, *contenu);
                        glVertex3d(taille.x, taille.y + TAILLE_CARRE, 0);
                        glVertex3d(taille.x, taille.y, 0);
                        glVertex3d(taille.x, taille.y, *contenu);
                        
                        glColor3ub(155, 0, 155);
                        glVertex3d(taille.x, taille.y, *contenu);
                        glVertex3d(taille.x, taille.y, 0);
                        glVertex3d(taille.x + TAILLE_CARRE, taille.y, 0);
                        glVertex3d(taille.x + TAILLE_CARRE, taille.y, *contenu);
                        
                        glColor3ub(255, 0, 255);
                        glVertex3d(taille.x + TAILLE_CARRE, taille.y, *contenu);
                        glVertex3d(taille.x + TAILLE_CARRE, taille.y, 0);
                        glVertex3d(taille.x + TAILLE_CARRE, taille.y + TAILLE_CARRE, 0);
                        glVertex3d(taille.x + TAILLE_CARRE, taille.y + TAILLE_CARRE, *contenu);
                        
                        glColor3ub(155, 0, 155);
                        glVertex3d(taille.x + TAILLE_CARRE, taille.y + TAILLE_CARRE, *contenu);
                        glVertex3d(taille.x + TAILLE_CARRE, taille.y + TAILLE_CARRE, 0);
                        glVertex3d(taille.x, taille.y + TAILLE_CARRE, 0);
                        glVertex3d(taille.x, taille.y + TAILLE_CARRE, *contenu);
                }
        }
        glEnd();
}

void initialiserGraphe(hauteur *altitude, hauteur *hauteur)
{
        SDL_Surface *surfaceTerrain = NULL;
        SDL_Surface *surfaceAltitude = NULL;
        int *contenu;
        coordonnees taille, tailleBMP;
        char nomTerrain[] = "terrain.bmp";
        char nomAltitude[] = "altitude.bmp";
        Uint8 r, v, b, a;
        Uint32 point;
        
        printf("\n--------- Initialisations, affichage des données dans 2 secondes. ---------\n\n");
        sleep(2);
        
        printf("Chargement des textures...\n");
        surfaceTerrain = SDL_LoadBMP(nomTerrain);
        surfaceAltitude = SDL_LoadBMP(nomAltitude);
        
        if((surfaceTerrain == NULL) || (surfaceAltitude == NULL))
        {
                fprintf(stderr, "Erreur de chargement d'image : %s ou %s.\n", nomTerrain, nomAltitude);
                exit(EXIT_FAILURE);
        }
        printf("Verifications de la taille des images...\n");
        if((surfaceTerrain->w != surfaceAltitude->w) || (surfaceTerrain->h != surfaceAltitude->h))
        {
                fprintf(stderr, "Erreur de taille d'image : %s et %s n'ont pas la même taille.\n", nomTerrain, nomAltitude);
                exit(EXIT_FAILURE);
        }
        altitude->debut = NULL;
        altitude->fin = NULL;
        altitude->taille.x = 0;
        altitude->taille.y = 0;
        hauteur->debut = NULL;
        hauteur->fin = NULL;
        hauteur->taille.x = 0;
        hauteur->taille.y = 0;
        tailleBMP.x = surfaceTerrain->w;
        tailleBMP.y = surfaceTerrain->h;
        
        printf("Création des tableaux bidimentionnels dynamiques...\n");
        tableauCreer(hauteur, tailleBMP, sizeof(int));
        tableauCreer(altitude, tailleBMP, sizeof(int));
        
        printf("Initialisations des tableaux...\n");
        for(taille.y = 0; taille.y < tailleBMP.y; taille.y++)
        {
                for(taille.x = 0; taille.x < tailleBMP.x; taille.x++)
                {
                        contenu = tableauValeur(*hauteur, taille);
                        point = pixel(surfaceTerrain, taille.x, taille.y);
                        SDL_GetRGBA(point, surfaceTerrain->format, &r, &v, &b, &a);
                        *contenu = (v == 255) ? 0 : -1;
                }
        }
        for(taille.y = 0; taille.y < tailleBMP.y; taille.y++)
        {
                for(taille.x = 0; taille.x < tailleBMP.x; taille.x++)
                {
                        contenu = tableauValeur(*altitude, taille);
                        point = pixel(surfaceAltitude, taille.x, taille.y);
                        SDL_GetRGBA(point, surfaceAltitude->format, &r, &v, &b, &a);
                        *contenu = v;
                }
        }
        printf("Fin. Suite dans 2 secondes.\n");
        sleep(2);
}

int trouverListeCoordonnees(coordonnees actuelle, liste liste)
{
        contenu *p_contenu = NULL;
        coordonnees courant;
        int taille = liste.taille;
        int i;
        
        for(i = 0; i < taille; i++)
        {
                p_contenu = listeValeur(liste, i);
                courant = p_contenu->actuelle;
                
                if((courant.x == actuelle.x) && (courant.y == actuelle.y))
                {
                        return i;
                }
        }
        return -1;
}