AccueilCodesTutorielsForumsEmploiLivresGuide achatConnexion

  • C / C++ / C++.NET CodeS-SourceS
  • RSS CodeS-SourceS
  • CodyxBot, le Bot GTalk & MSN qu'il vous faut !
  • Générez des revenus avec vos codes, scripts et tutoriaux
  • Aide à la navigation du site
begin process at 2009 07 06 10:38:13
Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum. Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !

ALGORITHME A*


Information sur la source

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é: 10 681 / 1 089
Auteur : GoldenEye Site perso
Ecrire un message privé
Note :
10 / 10 - par 2 personnes
10,00 / 10

  • 1

  • 2

  • 3

  • 4

  • 5

  • 6

  • 7

  • 8

  • 9

  • 10
Commentaire sur cette source (5)
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

Pour les "Membres Club", vous pouvez 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

Commentaires et avis

signaler à un administrateur
Commentaire de GoldenEye le 09/08/2005 11:08:42

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

signaler à un administrateur
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...

signaler à un administrateur
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é

signaler à un administrateur
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

signaler à un administrateur
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

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

CalendriCode

Juillet 2009
LMMJVSD
  12345
6789101112
13141516171819
20212223242526
2728293031  

Consulter la suite du CalendriCode

Téléchargements

Logiciels à télécharger sur le même thème :

Comparez les prix Nouvelle version


Console Sony Playstation 3 80GB
Entre 398€ et 425€


Visiter le guide achat

Photothèque Nouveau !

Photo sitges beachPhoto friends
Photo homme nuPhoto close up of smiling womans mouth and teeth

Visiter la photothèque


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
Temps d'éxécution de la page : 0,218 sec

Google Coop CodeS-SourceS Google Coop CodeS-SourceS


Certaines images présentes sur le site (notament certains avatars) sont issues des collections IconShock, donc si vous souhaitez utiliser ces icons vous devez les acheter, ne les copiez pas et ne utilisez pas dans vos sites et applications sans les avoir commandé.