Chapitre 8
Recherche de plus court chemin
sur une carte
La recherche de plus court chemin sur une carte est une étape importante pour de
nombreuses applications comme les jeux vidéo ou la planification de mouvements de
robots. Nous nous intéressons ici à la recherche de plus court chemin sur une grille. Elle
est souvent utilisée pour les jeux de stratégie temps réel par exemple, pour trouver le
chemin d'un agent jusqu'à son but sur la carte.
8.1 L'algorithme de Dijkstra
L'algorithme de Dijkstra permet de trouver le chemin de coût minimal dans un graphe
dont les arêtes sont associées à des coût positifs ou nuls. Nous nous intéressons ici au
cas particulier de l'algorithme de Dijkstra pour la recherche de plus court chemin sur une
carte. Afin d'illustrer la façon dont l'algorithme de Dijkstra trouve le plus court chemin
entre deux points, nous allons utiliser une carte très simple. Elle est donnée dans la figure
8.1. Le but est de trouver le plus court chemin entre le point D et le point A. Les cases
noires sont des obstacles infranchissables.
Le principe de l'algorithme de Dijkstra est de développer la position qui a le plus petit
chemin déjà parcouru. Pour cela, on associe à chaque position la longueur du chemin déjà
parcouru que nous appellerons g. Pour la position de départ g = O. Puisqu'un déplacement
coûte un, les fils de la position de départ ont tous un g = 1 . L' algorithme de Dijkstra
commence donc par développer la position de départ qui est marquée comme visitée, et à
insérer dans une structure de donnée tous les fils de cette position comme décrit dans la
figure 8.2.
Une fois ces nouvelles positions développées, le principe de l'algorithme est de dé-