Titre : L'algorithme A* ou comment calculer rapidement un chemin optimal
Auteur : Fabrice Rossi
Journal : GNU/Linux Magazine France, numéro 54, pages 32-41, Octobre 2003
Résumé : 

Les jeux vidéo de stratégie temps réel modernes ont des exigences très
élevées en terme de rendu graphique et d'intelligence artificielle (I.A.). Le
joueur attend un jeu en 3D construit à partir de milliers de polygones, pour le
plaisir de l'oeil, mais il veut aussi un adversaire d'un bon niveau, pour
le plaisir de l'esprit. La brique de base de l'I.A., le pathfinding,
c'est-à-dire le calcul des chemins suivis par les unités, doit donc être
rapide et donner de bons résultats. L'algorithme de Dijkstra, présenté dans
Linux Mag 53, garantit des résultats exacts, mais est général trop lent pour
fonctionner dans des conditions stressantes (un grand nombre d'unités, un
terrain de jeu très grand, etc.). Cependant, des modifications minimes mais
très subtiles permettent de conserver l'exactitude des chemins obtenus tout
en accélérant notablement leur calcul. L'algorithme obtenu porte le nom
d'algorithme A*.