algorithm
A * Algorithme Pathfinding

Introduction

Exemple simple de A * Pathfinding: Un labyrinthe sans obstacles

Disons que nous avons la grille 4 par 4 suivante:

Supposons que ce soit un labyrinthe . Il n'y a pas de murs / obstacles, cependant. Nous avons seulement un point de départ (le carré vert) et un point final (le carré rouge). Supposons également que pour passer du vert au rouge, nous ne pouvons pas nous déplacer en diagonale. Donc, en partant du carré vert, voyons les carrés vers lesquels nous pouvons aller et les surlignons en bleu:

Pour choisir la case à déplacer, nous devons prendre en compte 2 heuristiques:

1. La valeur "g" - C'est à quelle distance ce noeud est du carré vert.
2. La valeur "h" - C'est à quelle distance ce noeud est du carré rouge.
3. La valeur "f" - C'est la somme de la valeur "g" et de la valeur "h". C'est le nombre final qui nous indique à quel nœud se déplacer.

Pour calculer ces heuristiques, voici la formule que nous allons utiliser: distance = abs(from.x - to.x) + abs(from.y - to.y)

C'est ce qu'on appelle la formule "Manhattan Distance" .

Calculons la valeur "g" pour le carré bleu immédiatement à gauche du carré vert: abs(3 - 2) + abs(2 - 2) = 1

Génial! Nous avons la valeur: 1. Maintenant, essayons de calculer la valeur "h": abs(2 - 0) + abs(2 - 0) = 4

Parfait. Maintenant, obtenons la valeur "f": 1 + 4 = 5

Ainsi, la valeur finale pour ce noeud est "5".

Faisons la même chose pour tous les autres carrés bleus. Le grand nombre au centre de chaque carré est la valeur "f", tandis que le nombre en haut à gauche est la valeur "g" et le nombre en haut à droite est la valeur "h":

Nous avons calculé les valeurs g, h et f pour tous les nœuds bleus. Maintenant, que choisissons-nous?

Quel que soit celui qui a la valeur f la plus basse.

Cependant, dans ce cas, nous avons 2 nœuds avec la même valeur f, 5. Comment les choisissons-nous?

Simplement, vous pouvez en choisir un au hasard ou définir une priorité. Je préfère généralement avoir une priorité comme celle-ci: "Right> Up> Down> Left"

L'un des nœuds avec la valeur f de 5 nous emmène dans la direction "Down", et l'autre nous prend "Left". Puisque Down est plus prioritaire que Left, nous choisissons le carré qui nous emmène "Down".

Je marque maintenant les noeuds pour lesquels nous avons calculé les heuristiques, mais ne les a pas déplacés en orange, et le noeud que nous avons choisi comme cyan:

Bon, maintenant, calculons la même heuristique pour les nœuds autour du nœud cyan:

Encore une fois, nous choisissons le nœud descendant du nœud cyan, car toutes les options ont la même valeur f:

Calculons l'heuristique pour le seul voisin que le noeud cyan a:

D'accord, puisque nous allons suivre le même schéma que nous avons suivi:

Encore une fois, calculons l'heuristique pour le voisin du noeud:

Allons là-bas:

Enfin, nous pouvons voir que nous avons une place gagnante à côté de nous, alors nous allons là-bas et nous avons terminé.