Si vous êtes un développeur de jeux, vous avez peut-être toujours voulu implémenter A* comme pathfinding de personnage (ou d’ennemi). Je sais qu’il y a quelques années, je l’ai fait, mais avec mon niveau de programmation à l’époque, j’avais des problèmes avec les articles actuels qui existent. Je voulais écrire ceci comme une introduction facile avec un exemple de code source clair au pathfinding A* pour que n’importe qui puisse facilement le prendre et l’utiliser dans son jeu.
Un aspect important de A* est f = g + h. Les variables f, g, et h sont dans notre classe Node et sont calculées chaque fois que nous créons un nouveau nœud. Rapidement, je vais passer en revue ce que ces variables signifient.
- F est le coût total du nœud.
- G est la distance entre le nœud actuel et le nœud de départ.
- H est la distance heuristique – estimée du nœud actuel au nœud final.
Regardons un graphique rapide pour aider à illustrer ceci.
Awesome ! Disons que node(0) est notre position de départ et node(19) est notre position d’arrivée. Disons également que notre nœud actuel est au carré rouge node(4).
G
G est la distance entre le nœud actuel et le nœud de départ.
Si nous comptons en arrière, nous pouvons voir que node(4) est à 4 espaces de notre nœud de départ.
Nous pouvons également dire que G est 1 de plus que notre nœud parent (node(3)). Donc dans ce cas pour node(4), currentNode.g = 4.
H
H est la distance heuristique – estimée du nœud actuel au nœud final.
Calculons donc la distance. Si nous jetons un coup d’œil, nous verrons que si nous dépassons 7 espaces et remontons de 3 espaces, nous avons atteint notre nœud final (node(19)).
Appliquons le théorème de Pythagore ! a² + b² = c². Après l’avoir appliqué, nous verrons que currentNode.h = 7² + 3². Ou currentNode.h = 58.
Mais ne devons-nous pas appliquer la racine carrée à 58 ? Non ! Nous pouvons sauter ce calcul sur chaque nœud et obtenir le même résultat. Intelligent !
Avec une heuristique, nous devons nous assurer que nous pouvons réellement la calculer. Il est également très important que l’heuristique soit toujours une sous-estimation du chemin total, car une surestimation conduira A* à chercher des nœuds traversants qui ne sont peut-être pas les « meilleurs » en termes de fvaleur.
F
F est le coût total du nœud.
Ajoutons donc h et g pour obtenir le coût total de notre nœud. currentNode.f = currentNode.g + currentNode.h. Ou currentNode.f = 4+ 58. Ou currentNode.f = 62.
Temps d’utiliser f = g + h
Alright, donc c’était beaucoup de travail. Maintenant, avec tout ce travail, à quoi vais-je utiliser cette valeur f ?
Avec cette nouvelle valeur f, nous pouvons regarder tous nos nœuds et dire : » Hé, est-ce que c’est le meilleur nœud que je peux choisir pour avancer en ce moment ? « . Plutôt que de courir à travers chaque nœud, nous pouvons choisir ceux qui ont la meilleure chance de nous amener à notre objectif.
Voici un graphique pour illustrer. En haut, nous avons l’algorithme de Dijkstra, qui recherche sans cette valeur f, et en bas, nous avons A* qui utilise bien cette valeur f.
Algorithme de Dijkstra
En jetant un coup d’oeil à l’algorithme de Dijkstra, nous voyons qu’il ne fait que chercher. Il n’a aucune idée de quel nœud est le « meilleur », donc il calcule des chemins pour tous.
Algorithme A*
Avec A*,nous voyons qu’une fois que nous passons l’obstacle, l’algorithme donne la priorité au nœud avec le fle plus bas et la « meilleure » chance d’atteindre la fin.