Explication de l’algorithme de pathfinding A*

Décortiquons un instant le mot Pathfinding voulez-vous ? Pathfinding est un mot anglais qui peut se décortiquer en deux mots: path et find.

En anglais, le “path” c’est le chemin, la voie. Le mot find, vient du verbe “to find” qui signifie trouver. On peut donc en déduire qu’un pathfinder est un “trouveur de chemin” et que le pathfinding est un domaine de l’informatique qui étudie les différentes façons de trouver un chemin entre un point A et un point B (si chemin il y a).

Dans ce domaine, pas mal de choses ont déjà été réalisées, beaucoup de chercheurs et de programmeurs se sont déjà penchés sur la question. Dans le domaine du jeux, l’un des algorithmes de pathfinding le plus implémenté est l’algorithme A*.

Je vous propose d’étudier cette notion à travers deux articles techniques. L’un sur la théorie, l’autre davantage orienté sur une mise en pratique.

Explication de l’algorithme de pathfinding A* – la théorie
Explication de l’algorithme de pathfinding A* – la pratique