PLUS COURT CHEMIN SUR UN RÉSEAU ROUTIER (ALGORITHME A STAR / SDL)

/*
 Copyright (C) 2009  erwan le bris
 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 3 of the License, or
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 <stdlib.h>
#include "SDL/SDL.h"
#include <stdio.h>
#include <string>
#include "time.h"
#include <conio.h>
#include <math.h>
#include <time.h>


const int NB_MAX_ROUTE=20;
const int NB_MAX_ECHANGEUR=20;

#include "image.h"

class echangeur;
class route;

typedef echangeur* p_echangeur;
typedef route* p_route;

#include "echangeur.h"
#include "route.h"
#include "reseau.h"

struct l_echangeur;
struct noeud;

typedef l_echangeur* p_l_echangeur;
typedef noeud* p_noeud;


struct noeud
{
 p_echangeur ech;
 float g;
 p_noeud vient_de;
};

struct l_echangeur
{
  p_l_echangeur suivant;
  p_noeud actuel;
};

void creer_noeud(p_noeud*n,p_echangeur nech,float ng,p_noeud nvient_de)
{
 p_noeud nn=new(noeud);
 nn->ech=nech;
 nn->g=ng;
 nn->vient_de=nvient_de;
 *n=nn;
};

void creer_l_echangeur(p_l_echangeur*l)
{
 p_l_echangeur nl=new(l_echangeur);
 nl->actuel=NULL;
 nl->suivant=NULL;
 *l=nl;
};

void ajouter_noeud(p_l_echangeur*l,p_noeud pn)
{
 p_l_echangeur nl=new(l_echangeur);
 nl->suivant=*l;
 nl->actuel=pn;
 *l=nl;
};

void rechercher_meilleur_noeud(p_l_echangeur l,float*val,p_noeud*n,echangeur*objectif)
{
 float tampon;
 if (l->actuel)
 {
    tampon=(l->actuel)->g+distance(*((l->actuel)->ech),*objectif);
    if (tampon<*val)
    {
        *n=l->actuel;
        *val=tampon;
    };
    if (l->suivant) rechercher_meilleur_noeud(l->suivant,val,n,objectif);
 };
};


// met dans n l'adresse du noeud ou il y a l'échangeur e
// ne change rien à n sinon
void rechercher_echangeur(p_l_echangeur l,p_noeud*n,p_echangeur e)
{
 if (l->actuel)
 {
    if ((l->actuel)->ech==e) {
            *n=l->actuel;
        } else {
            if (l->suivant) rechercher_echangeur(l->suivant,n,e);
            };
 };
};

// retire dans la liste le noeud que l'on veut si il existe
void retirer_noeud(p_l_echangeur*l,p_noeud n)
{
 if ((*l)->actuel)
 {
    if (((*l)->actuel)==n) {
            (*l)=(*l)->suivant;
        } else {
            if ((*l)->suivant) retirer_noeud(&((*l)->suivant),n);
            };
 };
};

p_echangeur trajet[NB_MAX_ECHANGEUR];

// recherhe le plus court chemin pour aller de i_dep à i_arr dans reseau
// retourne le noeud d'arrive avec le cheminement dans l'autre sens

void rechercher_trajet_reseau(reseau r,int i_dep,int i_arr,p_noeud*trajet)
{
echangeur*ech_depart=r.get_echangeur(i_dep);
echangeur*ech_objectif=r.get_echangeur(i_arr);

// preparation de la recherche de trajet
// liste de points atteints, mais non explores
p_l_echangeur ouvert=NULL;
// liste de points atteints et explores
p_l_echangeur ferme=NULL;
// noeud du départ
p_noeud depart;
creer_noeud(&depart,ech_depart,0.,NULL);
// noeud courant en cours d'analyse
p_noeud courant;


// variables utilisees pendant les recherches
p_noeud rec;
p_route pr;
p_echangeur pe;
float valeur;
float valeur_0=10000000.;
int recherche;
int i;


// initialisation de la liste ouvert
// on y place le noeud de depart
ajouter_noeud(&ouvert,depart);

/*
 boucle de recherche de trajet
*/
// recherche est mis à 0 : aucune solution de trouvee
recherche=0;
while (recherche==0)
{
    // la valeur de reference pour le point le plus proche est mise à une valeur arbitraire
    // grande fixée plus haut
    valeur=valeur_0;
    // on recherche le noeud dans la liste ouvert qui a le potentiel le plus grand
    // soit la valeur g+distance la plus faible
    if (ouvert) // si il y a une liste, avec un noeud au minimum
       rechercher_meilleur_noeud(ouvert,&valeur,&courant,ech_objectif);
    // courant est le noeud avec le meilleur g+f de la liste ouvert
    // valeur est la valeur (g+distance) la plus basse des points non encore analysés
    if (valeur<valeur_0) // il y a un noeud potentiel, ce noeud est le noeud courant
    {
      // on teste si courant est l'objectif
      if (courant->ech==ech_objectif)
      {
        recherche=1;  // le courant est l'objectif
      } else {
        // le courant n'est pas l'objectif
        // on regarde tous les points qui sont atteignables à partir du point courant
        // on liste toutes les routes qui partent de l'echangeur du point courant
        for (i=0;i<(courant->ech)->get_nb_direction();i++)
        {
           // reperage de la route
           pr=(courant->ech)->get_direction(i);
           // reperage de l'echangeur ou va la route
           pe=pr->get_autre_echangeur(courant->ech);
           // on regarde si il y a deja un noeud qui existe avec cet echangeur dans la liste ouvert
           rec=NULL;
           if (ouvert) rechercher_echangeur(ouvert,&rec,pe);
           if (rec) // il y a un noeud avec cet echangeur dans ouvert
           {

                if ((rec->g)>(courant->g+pr->get_longueur()))
                // le nouveau chemin est plus court que le premier
                {
                    // on modifie la valeur g de ce noeud
                    rec->g=courant->g+pr->get_longueur();
                    // on ajoute que le chmein preferentiel vient de courant
                    rec->vient_de=courant;
                };
           };
           // on regarde si il y a deja un noeud qui existe avec cet echangeur dans la liste ferme
           if (ferme) rechercher_echangeur(ferme,&rec,pe);
           if (rec) // il y a un noeud avec cet echangeur dans ferme
           {
                if ((rec->g)>(courant->g+pr->get_longueur()))
                // le nouveau chemin est plus court que le premier
                {
                    rec->g=courant->g+pr->get_longueur();
                    rec->vient_de=courant;
                    // le noeud rec doit être mis dans la liste ouvert et supprimé de la liste ferme
                    ajouter_noeud(&ouvert,rec);
                    retirer_noeud(&ferme,rec);
                };
           };
           if (rec==NULL) // aucun noeud n'est cree avec cet echangeur
           {
               // on en cree un et on le met dans la liste ouvert
               creer_noeud(&rec,pe,courant->g+pr->get_longueur(),courant);
               ajouter_noeud(&ouvert,rec);
           };
        };
        // ici toutes les directions possibles ont été explorées.
        // on deplace donc le noeud courant de la liste ouvert à la liste ferme
        ajouter_noeud(&ferme,courant);
        retirer_noeud(&ouvert,courant);
      };
    } else {recherche=2;}; // l'objectif ne peut pas être atteint; il n'y a pas de point dans la liste ouvert
};

// fin de la boucle de recherche
// si recherche=2, pas de solution
// si recherche=1, une solution et le noeud courant contient la distance et la succession des noeuds


    *trajet=courant;
};

// transforme la recherche du plus court chemin en succession d'echangeur
// pour arriver a l'objectif

// entree : noeud_arrivee
// sortie : la liste d'echangeurs et le nombre d'echangeurs à visiter

void transforme_recherche_trajet(p_noeud noeud_arrivee,p_echangeur*trajet,int*nb_trajet)
{
  p_noeud noeud_courant;

  // premier passage pour determiner le nb_trajet
  *nb_trajet=1;
  noeud_courant=noeud_arrivee;
  while (noeud_courant->vient_de)
    {
        noeud_courant=noeud_courant->vient_de;
//        trajet[nb_trajet]=noeud_arrivee->ech;
        (*nb_trajet)++;
    };
//    trajet[nb_trajet]=noeud_arrivee->ech;

  int compteur=*nb_trajet;
  int i;
  for (i=compteur;i<NB_MAX_ECHANGEUR;i++) trajet[i]=NULL;
  // deuxiemme passage pour mettre les bons echangeurs dans l'ordre
  noeud_courant=noeud_arrivee;
  compteur--;
  trajet[compteur]=noeud_courant->ech;
  while (compteur>0)
    {
        compteur--;
        noeud_courant=noeud_courant->vient_de;
        trajet[compteur]=noeud_courant->ech;
    };
//    trajet[nb_trajet]=noeud_arrivee->ech;

  };


int main( int argc, char* args[] ) {

    srand(time (NULL));
	//Initialisation de tous les sous-systèmes de SDL
	if( SDL_Init( SDL_INIT_EVERYTHING ) == -1 ) {
		return EXIT_FAILURE;
	}

	//Mise en place de l'écran
	screen = SDL_SetVideoMode( SCREEN_WIDTH, SCREEN_HEIGHT, SCREEN_BPP, SDL_SWSURFACE );

	//S'il y a une erreur dans la création de l'écran
	if( screen == NULL ) {
		return EXIT_FAILURE;
	}
	//Mise en place de la barre caption
	SDL_WM_SetCaption( "reseau routier", NULL );
	//Chargement des images

	background = load_image( "background.bmp" );
 	//On applique le fond sur l'écran
    apply_surface( 0, 0, background, screen );



/*
 DEBUT DES COMMANDES DE JEU
*/


reseau r;
r.ajouter_echangeur(20,50);
r.ajouter_echangeur(120,70);
r.ajouter_echangeur(190,20);
r.ajouter_echangeur(320,150);
r.ajouter_echangeur(210,270);
r.ajouter_echangeur(290,120);
r.ajouter_echangeur(50,220);

r.ajouter_route(1,0);
r.ajouter_route(2,1);
r.ajouter_route(0,2);
r.ajouter_route(2,5);
r.ajouter_route(1,3);
r.ajouter_route(4,3);
r.ajouter_route(5,3);
r.ajouter_route(0,4);
r.ajouter_route(0,6);
r.ajouter_route(4,6);


/*
RECHERCHE DU TRAJET LE PLUS COURT
*/

p_echangeur trajet[NB_MAX_ECHANGEUR];
int nb_trajet;
p_noeud noeud_arrivee;

rechercher_trajet_reseau(r,5,6,&noeud_arrivee);



transforme_recherche_trajet(noeud_arrivee,trajet,&nb_trajet);


int i;

for (i=0;i<nb_trajet;i++)
{
  r.affiche();
  trajet[i]->affiche_voiture();
/*
FIN DES COMMANDES DE JEU
*/

	//Mise à jour de l'écran
	if( SDL_Flip( screen ) == -1 ) {
		return EXIT_FAILURE;
	}

    SDL_Delay( 3000 );
}


	//Libération des surfaces
	SDL_FreeSurface( message );
	SDL_FreeSurface( background );

	//On quitte SDL
	SDL_Quit();

}

/*
  route.h :
  
  CLASSE ROUTE
    
*/

class route
{
  p_echangeur e1,e2;
  float longueur;
  public:
  route(p_echangeur ne1,p_echangeur ne2);
  void affiche(void);
  p_echangeur get_autre_echangeur(p_echangeur e3);
  float get_longueur(void){return (longueur);};
};

p_echangeur route::get_autre_echangeur(p_echangeur e3)
{
  p_echangeur pp=NULL;
  if (e1==e3) pp=e2;
  if (e2==e3) pp=e1;
  return (pp);
};

route::route(p_echangeur ne1,p_echangeur ne2)
{
 e1=ne1;
 e2=ne2;
 longueur=distance(*ne1,*ne2);
};

void route::affiche(void)
{
 SDL_Surface *imm = NULL;
 imm = load_image( "route_noir.bmp" );

  //determination des extremites de la route
 int x1,x2,y1,y2;
 x1=e1->get_x();y1=e1->get_y();
 x2=e2->get_x();y2=e2->get_y();
 // determination du plus grand ecart
 int dx,dy;
 dx=abs(x1-x2);dy=abs(y1-y2);
 // cas ou le plus grand est dx
 int i;
 int x,y;
 for (i=0;i<dx;i++)
  {
      x=x1+i*(x2-x1)/dx;
      y=y1+i*(y2-y1)/dx;
      //On applique le message sur l'écran
      apply_surface( x, y, imm, screen );
  };
 // cas ou le plus grand est dy
 for (i=0;i<dy;i++)
  {
      x=x1+i*(x2-x1)/dy;
      y=y1+i*(y2-y1)/dy;
      //On applique le message sur l'écran
      apply_surface( x, y, imm, screen );
  };

};

/*
  echangeur.h
  CLASSE ECHANGEUR
*/

class echangeur
{
  int x,y;
  p_route direction[4];
  int nb_direction;
  public:
  echangeur(int,int);
  void affiche(void);
  void affiche_voiture(void);
  int get_x(void){return (x);};
  int get_y(void){return (y);};
  int get_nb_direction(void){return( nb_direction);};
  void ajouter_route(p_route nr){direction[nb_direction]=nr;nb_direction++;};
  p_route get_direction(int i){return(direction[i]);};
};

void echangeur::affiche_voiture(void)
{
 SDL_Surface *imm = NULL;
 imm=load_image("voiture.bmp");
 apply_surface( x-5, y-5, imm, screen );
};

void echangeur::affiche(void)
{
 SDL_Surface *imm = NULL;
 imm=load_image("echangeur.bmp");
 apply_surface( x-5, y-5, imm, screen );
};

echangeur::echangeur(int nx,int ny)
{
  x=nx;y=ny;
  nb_direction=0;
};

float distance(echangeur e1,echangeur e2)
{
  float dist,dx,dy;;
  dx=e1.get_x()-e2.get_x();
  dy=e1.get_y()-e2.get_y();
  dist=dx*dx+dy*dy;
  dist=sqrt(dist);
  return(dist);
};

/*
  reseau.h
    CLASSE RESEAU
*/

class reseau
{
    p_echangeur liste_echangeur[NB_MAX_ECHANGEUR];
    p_route liste_route[NB_MAX_ROUTE];
    int nb_echangeur;
    int nb_route;
    public:
    reseau(void){nb_echangeur=0;nb_route=0;};
    void ajouter_echangeur(int,int);
    void ajouter_route(int,int);
    void affiche(void);
    p_echangeur get_echangeur(int i){return (liste_echangeur[i]);};
};

void reseau::affiche(void)
{
 int i;
 for (i=0;i<nb_route;i++) {(liste_route[i])->affiche();};
 for (i=0;i<nb_echangeur;i++) {(liste_echangeur[i])->affiche();};
};

void reseau::ajouter_echangeur(int nx,int ny)
{
 if (nb_echangeur<NB_MAX_ECHANGEUR-1)
 {
    p_echangeur ne=new(echangeur)(nx,ny);
    liste_echangeur[nb_echangeur]=ne;
    nb_echangeur++;
 };
};

void reseau::ajouter_route(int ec1,int ec2)
{
 if ((nb_echangeur>ec1)&&(nb_echangeur>ec2))
 if ((ec1!=ec2)&&(nb_route<NB_MAX_ROUTE-1))
 if ((liste_echangeur[ec1]->get_nb_direction()<4)&&(liste_echangeur[ec2]->get_nb_direction()<4))
 {
    p_route nr=new(route)(liste_echangeur[ec1],liste_echangeur[ec2]);
    liste_route[nb_route]=nr;
    nb_route++;
    liste_echangeur[ec1]->ajouter_route(nr);
    liste_echangeur[ec2]->ajouter_route(nr);
 }
};

/*
  image.h 
  à partir des propositions du tutoriel de http://franckh.developpez.com/articles/c-ansi/bien-debuter-en-c/
  sur l'utilisation du SDL  
*/


//Les attributs de notre écran
   const int SCREEN_WIDTH = 640;
   const int SCREEN_HEIGHT = 480;
   const int SCREEN_BPP = 32;


//Les surfaces que nous allons utiliser
SDL_Surface *message = NULL;
SDL_Surface *background = NULL;
SDL_Surface *screen = NULL;

SDL_Surface *load_image( std::string filename ) {
	//Surface tampon qui nous servira pour charger l'image
	SDL_Surface* loadedImage = NULL;

	//L'image optimisée qu'on va utiliser
	SDL_Surface* optimizedImage = NULL;

	//Chargement de l'image
	loadedImage = SDL_LoadBMP( filename.c_str() );

	//Si le chargement se passe bien
	if( loadedImage != NULL ) {
		//Création de l'image optimisée
		optimizedImage = SDL_DisplayFormat( loadedImage );

		//Libération de l'ancienne image
		SDL_FreeSurface( loadedImage );
	}

	//On retourne l'image optimisée
	return optimizedImage;
}


void apply_surface( int x, int y, SDL_Surface* source, SDL_Surface* destination ) {
	SDL_Rect offset;

	offset.x = x;
	offset.y = y;
	//On blitte la surface
	SDL_BlitSurface( source, NULL, destination, &offset );
}