Algorithme A star A*
Exemple de recherche de chemin le plus court
Algorithme
L'algorithme de recherche A* (qui se prononce A étoile, ou A star à l'anglaise) est un algorithme de recherche de chemin dans un graphe entre un nœud
initial et un nœud final tous deux donnés. De par sa
simplicité il est souvent exhibé comme un exemple typique
d'algorithme de planification, un domaine de l'intelligence artificielle.
L'algorithme A* a été créé pour que la première solution trouvée soit
l'une des meilleures, c'est pourquoi il est célèbre dans des
applications comme les jeux vidéo privilégiant le temps de calcul à
l'exactitude des résultats.
Détails
Vous trouverez plus d'informations sur Wikipedia http://fr.wikipedia.org/wiki/Algorithme_A%2A
Le programme
Le programme présenté ici met en oeuvre l'algorithme de
recherche du plus court chemin dans le cas le plus simple envisageable.
Il est possible de définir le point de départ et
d'arrivée, et de dessiner des murs (obstacles) entre ces 2
points.
La zone explorée par l'algorithme se colorie, montrant l'optimisation réalisée dans la recherche du chemin.
Pour le développement, je me suis inspiré de l'excellente page : http://www.gamedev.net/reference/articles/article2003.asp
Sa lecture est indispensable si l'algorithme vous intéresse !
Fonctionnement programme
Clic droit : ajouter point de départ et point d'arrivée
Clic gauche : ajouter un mur
Clic central 2 fois : ajouter mur en ligne
ECHAP : Quitter
Téléchargements
Version Windows
Astar.exe (executable)
SDL.dll (à placer dans le répertoire /windows/system
Version Linux
astar (executable)
Screenshots
Copyleft 2005