A Star (A*) Algorithme C# - Pathfinding
A* est un algorithme de type pathfinding. C'est à dire que c'est un algorithme qui est capable de trouver un chemin entre deux points, en prenant en compte certaines contraintes. Il existe plusieurs algorithmes de type pathfinding, mais AStar est un des meilleurs en termes de simplicité, performance et ressource.
Presque tous les jeux récents utilisent ce genre d'algorithme (avec bien entendu des améliorations faites maison). Pensez, par exemple, à un jeu où l'ordinateur qui est votre adversaire doit déplacer des unités: il doit les amener d'un point de la map à un autre, en respectant certaines contraintes telles que des unités ennemies, des montagnes où les unités avancent moins vites, peut-être des ruisseaux, etc.
A* est capable de prendre en compte ces différentes contraintes et de calculer le chemin le plus court pour aller de A à B. Le net grouille d'informations qui explique le fonctionnement (assez simple) de cet algorithme, je ne vais donc pas le réexpliquer ici. Vous trouverez néamoins un fichier html qui décrit de manière très simple le fonctionnement (j'ai implémenté l'algorithme grâce à ce document que j'ai trouvé sur le web).
La solution contient trois projets: un projet library qui contient A Star (A*) à proprement parlé, un autre qui contient les classes pour représenter graphiquement le résultat de l'algorithme (cf. capture) et un projet Windows qui utilise les deux autres projets pour qu'on puisse tester.
J'ai rajouté également des maps au projet pour qu'on puisse voir le résultat instantanément. Dans le cas de la map "laby" par exemple, vous verrez des cases bleues et rouges. Ces cases représentent des contraintes, c'est à dire qu'elles ont une certaine pondérations (x2 pour la case bleue, x5 pour la case rouge). Autrement dit, l'algorithme va calculer le chemin le plus adapté en partant du principe que s'il passe sur une case rouge ça lui prendra 5x plus de temps que de passer sur une case normale (pour reprendre la comparaison ci-dessus, ça pourrait être l'équivalent d'un passage dans du sable où les unités sont ralenties).
Il est naturellement possible d'améliorer ce projet, par exemple en gérant les déplacements diagonaux, en prenant en compte des contraintes plus complexes, en améliorant la rapidé de l'algorithme AStar, etc.
Le projet qui implémente l'algo A Star est donc pratiquement prêt à l'emplois tel quel, suffit de le rajouter à votre solution...
N'hésitez pas à soumettre vos remarques, je tâcherai de les prendre en compte dans une future version.