Explication graphique des algorithmes de PathFinding

Illustration graphique de la recherche du chemin le plus court avec l'algorithme A*

Le PathFinding est présent dans bon nombre de domaines, en particulier chez les jeux vidéos qui nécessitent de doter les bots d’une intelligence artificielle afin qu’ils puissent se déplacer, par exemple, sur une carte le plus efficacement possible.

Les deux principaux algorithmes de recherche de chemin sont l’algorithme de Dijkstra et l’algorithme A*. Il ne faut pas chercher à savoir lequel est meilleur, mais lequel est le plus efficace dans une situation précise.

Pour avoir une idée de leurs fonctionnements, un projet posté sur GitHub propose de créer notre propre plan en nous permettant de déplacer le point de départ et d’arrivé, et d’ajouter ou supprimer des obstacles. Vous pourrez ensuite choisir quel algorithme (ou sous-algorithme) utiliser, sélectionner diverses options comme l’utilisation des diagonales, et enfin appuyer sur « Start » pour voir l’algorithme en action.

Un petit timer en bas à droite précisera également le temps et le nombre d’actions qui ont été nécessaires afin de mener à bien la recherche du chemin. Avec tout ça, vous devriez pouvoir trouver l’algorithme optimal pour votre utilisation.

[source]

Laisser un commentaire

Your email address will not be published / Required fields are marked *

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.