Sommaire

Domaines d’application

Ces algorithmes de recherche de chemins sont utilisés dans de nombreux domaines. 

Le premier domaine est celui de la recherche d’itinéraires. Tous les GPS et les applications permettant d’aller d’un endroit à l’autre (en train, en bus, en métro, à pied...) utilisent des algorithmes de pathfinding. Ils prennent en compte la longueur du chemin ou son temps. Vue la complexité des cartes souvent utilisées (par exemple pour Google Maps), il est évident que les algorithmes doivent être optimisés, et privilégient les grands axes dès que possible. Le détail des algorithmes n’est bien évidemment pas communiqué.

Cette recherche de chemins se retrouve dans les jeux vidéo. Le but est alors de déplacer un personnage (contrôlé par le joueur ou représentant un ennemi) d’un endroit à un autre. Les cartes peuvent être très grandes, et le nombre de personnages important. Là encore, il faut optimiser les algorithmes utilisés. On peut cependant noter que c’est l’algorithme A* qui est majoritairement implémenté.

La robotique est un autre domaine friand de recherche d’itinéraires. Il s’agit alors d’amener un robot d’un point à un autre, le plus rapidement possible. Ces algorithmes sont généralement modifiés pour deux raisons. La première, c’est que l’environnement ...