initialise un reseau routier simple avec des echangeurs et des routes entre les echangeurs (maxi 4 routes par echangeur).
affiche le reseau (utilise SDL).
l'utilisateur entre dans la fonction main un échangeur d'arrivée et un échangeur de départ.
une procédure met en oeuvre l'algorithme Astar (A*) pour trouver le chemin le plus court (en longueur de route parcourue) pour relier l'échangeur de départ et l'échangeur d'arrivée.
Enfin, une petite voiture illustre graphiquement sur le réseau le échangeurs traversés successivement pour réaliser ce trajet.
Source / Exemple :
/*
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;
};
void creer_l_echangeur(p_l_echangeur*l)
{
p_l_echangeur nl=new(l_echangeur);
nl->actuel=NULL;
nl->suivant=NULL;
};
void ajouter_noeud(p_l_echangeur*l,p_noeud pn)
{
p_l_echangeur nl=new(l_echangeur);
nl->suivant=*l;
nl->actuel=pn;
};
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)
{
};
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) {
} 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
};
// 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
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 );
}
Conclusion :
je vais essayer de partir sur cette base pour faire une simulation de réseau routier (trafic en fonction de matrices origine/destination)
Je le déposerai quand il sera terminé.
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.