begin process at 2012 02 10 06:58:19
  Trouver un code source :
 
dans
 
[ Dernières recherches ]
Accueil > 

Code

 > 

Maths & Algorithmes

 > ALGORITHME A*

ALGORITHME A*


 Information sur la source

Note :
10 / 10 - par 2 personnes
10,00 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10
Catégorie :Maths & Algorithmes Classé sous :pathfinding, astar, chemin, itinéraire, algorithme Niveau :Initié Date de création :05/08/2005 Date de mise à jour :09/08/2005 10:39:42 Vu / téléchargé :15 827 / 1 383
Auteur : GoldenEye

Ecrire un message privé
Site perso
Commentaire sur cette source (6)
Ajouter un commentaire et/ou une note

 Description

Cliquez pour voir la capture en taille normale
La résolution du problème du plus court chemin pour aller de A à B par l'algorithme Astar
Le problème est restreint à N noeuds ayant au plus 4 voisins (une version généralisée pour les plans de métro est en cours de réalisation)
Le fichier map.txt indique pour chaque noeud s'il est accessible ou non (valeur positive inquant le relief par exemple si oui, nulle sinon). Vous pouvez bien évidemment faire votre propre map.
Dans la fenêtre OpenGL, appuyer sur D ou S pour prendre le contrôle de la source ou de la destination et utiliser les flèches directionnelles pour les faire se mouvoir.
Si les internautes le souhaitent, je mettrais en ligne la version généralisée qui permettra de trouver le plus court chemin entre deux stations de RER et de métro parisien (et indiquer le temps)

Références :
[1] leri.univ-reims.fr/~nocent/lectures/Astar.pdf
[2] Game Programming Gems, les chapitres associés (pathFinding)


 Conclusion

Quelques parties sont commentées en espagnol, j'en suis désolé, j'ai un peu de mal avec le français...

 Fichier Zip

Les Membres Club peuvent télécharger directement un fichier contenu dans le zip sans télécharger le zip en entier !

Télécharger le zip


 Historique

09 août 2005 10:39:42 :
Update [1] : Petite erreur dans le code, je me suis aperçu que c'était l'algorithme de Dijkstra qui était implémenté. Le tir a été rectifié, c'est désormais bel et bien Astar qui tourne. (gain de temps de l'ordre de 30-35%). Une autre petite erreur a été corrigée dans la mise à jour des poids des sommets visités

 Sources du même auteur

Source avec Zip Source avec une capture TILE MAP EDITOR 2.4
Source avec Zip Source avec une capture CHAT MULTITHREAD
Source avec Zip TRANSFORMÉE DE FOURIER : REPRÉSENTATION GRAPHIQUE [VC++ ET A...
Source avec Zip [VC++] COMPRESSION DE HUFFMAN+TUTORIEL
[VC++ ET DJGPP] FLOCON DE VON KOCH AVEC ALLEGRO
Toutes les sources de GoldenEye

 Sources de la même categorie

Source avec Zip UN EXAMPLE D'APPLICATION EN CUDA DE L'ALGORITHME DE SCAN POU... par oguzaras
Source avec Zip Source avec une capture CHIFFREMENT DE VIGENERE par lajouad
Source avec Zip Source avec une capture ANALYSE SYNTAXIQUE par lajouad
Source avec Zip Source avec une capture STRUCTURE D'UNE MATRICE PAR LES LISTE LINÉAIRE (NON CONTUGUS... par benzarabel
Source avec Zip Source avec une capture DESSINER UNE ARBRE BINAIRE( MODE CONSOLE): par benzarabel
Toutes les sources de la catégorie Maths & Algorithmes

 Sources en rapport avec celle ci

Source avec Zip UN EXAMPLE D'APPLICATION EN CUDA DE L'ALGORITHME DE SCAN POU... par oguzaras
Source avec Zip Source avec une capture RÉSOLUTION SUDOKU (9X9) PAR BACKTRACKING RÉCURSIF INTELLIGEN... par Gallien69
Source avec Zip BELLMAN:LA VALEUR DU PLUS COURT CHEMIN ET LE PLUS COURT CHEM... par Perace
Source avec Zip COMPARAISON DE L'ALGORITHME DE DIJKSTRA ET A* SUR LE TRAJET ... par vdujardi
Source avec Zip LISTVIEW PATHFINDING (WIN32) par AlexMAN

Commentaires et avis

Commentaire de GoldenEye le 09/08/2005 11:08:42

herve.picard@int-evry.fr pour toute question

Commentaire de rrk275 le 01/10/2006 11:36:04

Sur des graphes de petites taille ( le metro étant extrement petit) ne suffit t'il pas de mettre un algorithme qui trouve le meilleur  chemin type dijkstra? Enfin c'est toujours utile d'un point de vue algo et explicatif...

Commentaire de GoldenEye le 03/01/2007 15:11:56

Le métro n'est pas si petit que cela, il y a 300 stations de métro et pas mal non plus de RER
Dijkstraa n'est pas optimal quant à la solution proposée. Maintenant pour mon exemple, je reconnais que cela aurait pu être plus adapté

Commentaire de rrk275 le 08/06/2007 14:57:04

j'ai un temps de reponse assez long mais sur 10 000 noeuds et autant de chemins que tu veuilles l'algorithme djikstra mettra moins d'une seconde alors tes 300 stations... c'est pas optimal

Louis

Commentaire de GoldenEye le 08/06/2007 15:36:43

Je regrette, comme tu peux le constater dans mon commentaire l'approche formelle de Djikstraa s'est révélée moins rapide que AStar (utilisant une approche heuristique type BFS)

Après calculs un peu plus savant, il s'avère qu'AStar, s'il ne garantit pas une résolution optimale du pathfinding (au sens du chemin le moins coûteux) sera toujours plus rapide que son homologue
Cordialement

Commentaire de mersin le 11/05/2011 11:53:57

salut, est ce qu'il y a quelqu'un qui peut m'aider pour implémenter l'algorithme A*
en c  SVP.

 Ajouter un commentaire


Discussions en rapport avec ce code source dans le forum

Algorithme de Bellman Ford, chemin le plus cours [ par Nuggy ] Bonjour :je recherche de l'aide pour un programme en c++, le travail consiste a réaliser un algorithme de Bellman Ford .Cet algo permet de calculer le 2 autres petites questions [ par fauve ] Lorsqu'avec Borland C++ v5.02, on compile le code, une fenêtre apparait avec tout en haut de celle-ci un chemin d'accès de l'exécutable crée et-il pos Quelques questions sur rsa [ par jean84 ] Salut a tous ! Je me suis interesse a l'algorithme de cryptage rsa il y a quelque temps mais j'avoue avoir encore du mal avec certains points Algorithme de traitement d'image [ par custronicien ] Bonjour à vous !   <p class="MsoNor Mettre en pause l'exécution d'un algorithme [ par nisaloncaje ] Bonjour,J'utilise dans mon programme, pour l'affichage graphique gluttimerfunc (déclenche un rafraichissement de l'image toutes les 30 millisecondes). probleme linker lapack++ [ par renlel ] Bonjour, J´utilise DEV-C++ sous windows et je cherche à utiliser la librairie lapack++. J´ai installer une version qui comprends libblas32 et libpack Projet d'été sur SUDOKU!! Aidez-nous s'il vous plait... [ par Naruttibayo ] Au préalable, nous tenons à remercier tous ceux qui contribuerons à notre projet...On nous demande d'écrire un programme C qui permet de Générer des G Utilisation des chemins d'accès prédéfinis. [ par _michel ] Certains chemins d'accès sont définis, pour la portabilité des programmes, sous cette forme : %CHEMIN_D_ACCES%On retrouve par exemple, en tapant la co Espaces dans un chemin d'accès [ par ssmint ] Bonjour à tous,mon petit problème du jour, c'est de pouvoir utiliser dans fonctions ayant besoin d'un chemin d'accès en argument...  Genre fopen, Shel Déplacer un fichier / indiquer le chemin de sauvegarde [ par ptitanic ] Bonjour, Je fais une appli avec c++/MFC et je souhaiterais savoir si quelqu'un a une idée pour déplacer un fichier. Je m'explique, l'utilisateur choi


Nos sponsors


Sondage...

Comparez les prix


Apple iPhone 4 Noir (32 Go)
Entre 1290€ et 1333€

Visiter le guide achat

CalendriCode

Février 2012
LMMJVSD
  12345
6789101112
13141516171819
20212223242526
272829    

Consulter la suite du CalendriCode
 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 3,229 sec (3)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales
Outils Convertisseur VB/C# Snippets et scripts Outils en ligne La ToolBox
Communauté Programmation Photographie Technologie Newsgroups Emploi Forum Blogs
Guide d'achat Téléphonie mobile Image et son Informatique Bureautique Jeux vidéo
Logiciels Internet & Réseau Développement Market Android Jeux & Loisirs Graphisme Multimédia Sécurité Pilotes
Loisirs Cartes virtuelles Vidéos droles Jeux en ligne Géoguide AndroLib (Android Market)