Algorithme a*

Soyez le premier à donner votre avis sur cette source.

Vue 21 356 fois - Téléchargée 2 092 fois

Description

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)

Source / Exemple :


Voir le zip

Conclusion :


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

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

cs_GoldenEye
Messages postés
527
Date d'inscription
vendredi 14 septembre 2001
Statut
Membre
Dernière intervention
6 octobre 2008
2 -
herve.picard@int-evry.fr pour toute question
rrk275
Messages postés
542
Date d'inscription
vendredi 25 juin 2004
Statut
Membre
Dernière intervention
1 octobre 2007
2 -
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...
cs_GoldenEye
Messages postés
527
Date d'inscription
vendredi 14 septembre 2001
Statut
Membre
Dernière intervention
6 octobre 2008
2 -
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é
rrk275
Messages postés
542
Date d'inscription
vendredi 25 juin 2004
Statut
Membre
Dernière intervention
1 octobre 2007
2 -
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
cs_GoldenEye
Messages postés
527
Date d'inscription
vendredi 14 septembre 2001
Statut
Membre
Dernière intervention
6 octobre 2008
2 -
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

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.