Plus court chemin sur un réseau routier (algorithme a star / sdl)

Soyez le premier à donner votre avis sur cette source.

Vue 9 180 fois - Téléchargée 902 fois

Description

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;
  • 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 ); }

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é.

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Messages postés
368
Date d'inscription
jeudi 13 mars 2003
Statut
Membre
Dernière intervention
27 janvier 2010

C'est une modélisation hybride. L'architecture est divisée en plusieurs couches (couches de liaison, planification, régulation, modèle du véhicule), donc t'as à la fois la partie comportementale qui s'intéresse à l'ensemble du système multi-agents et tu as également la partie régulation dynamique des véhicules.
Messages postés
3
Date d'inscription
dimanche 19 avril 2009
Statut
Membre
Dernière intervention
10 novembre 2009

salut !

je ne connaissais pas la STL. J'ai regardé du coup, et c'est vrai que j'aurais dû l'utiliser. Ca permet de gagner un temps fou, j'imagine.

Merci.

Ca consiste en quoi une modélisation en pelotons ? C'est une modélisation véhicule par véhicule d'un comportement d'ensemble sur la route ?
Messages postés
368
Date d'inscription
jeudi 13 mars 2003
Statut
Membre
Dernière intervention
27 janvier 2010

Salut,

Si tu travailles sur une simulation de réseau routier on devrait avoir pas mal de choses à se raconter :). Je travaille sur une simulation également en C++/OpenGL de système autoroutier. La problématique est différente de la tienne, il s'agit plutôt d'optimiser l'espace "autoroutier" via une configuration peloton des véhicules. Je fais ça dans le cadre d'un projet de fin d'étude.

Petite remarque sur le code, tu aurais du utiliser la STL vu que t'es parti sur du C++.

Voila, hate de voir la suite de ton travail :).

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.