Une explication simple des algorithmes de recherche de chemin et A *

Partie 1. Algorithme de recherche général

Présentation

Trouver un chemin est l'un de ces sujets qui sont généralement les plus difficiles pour les développeurs de jeux. Les gens comprennent particulièrement mal l'algorithme A * , et beaucoup pensent qu'il s'agit d'une sorte de magie incompréhensible.

Le but de cet article est d'expliquer la recherche du chemin en général et de A * en particulier d'une manière très compréhensible et accessible, mettant ainsi un terme à l'idée fausse répandue que ce sujet est complexe. Avec la bonne explication, tout est assez simple.

Veuillez noter que dans l'article, nous considérerons la recherche d'un moyen pour les jeux ; contrairement aux articles plus académiques, nous omettons les algorithmes de recherche tels que Depth-First ou Breadth-First. Au lieu de cela, nous allons essayer de passer de zéro à A * le plus rapidement possible.

Dans la première partie, nous expliquerons les concepts les plus simples pour trouver un chemin. En comprenant ces concepts de base, vous vous rendrez compte que A * est étonnamment évident.

Circuit simple

Bien que vous puissiez appliquer ces concepts à des environnements 3D complexes arbitraires, commençons par un schéma extrêmement simple: une grille carrée de 5 x 5. Pour plus de commodité, j'ai marqué chaque cellule avec une lettre majuscule.


Maille simple.

La toute première chose que nous ferons est d'imaginer cet environnement sous forme de graphique. Je ne vais pas expliquer en détail ce qu'est un graphique; Autrement dit, il s'agit d'un ensemble de cercles reliés par des flèches. Les cercles sont appelés «nœuds» et les flèches sont appelées «bords» .

Chaque nœud représente un «état» dans lequel le personnage peut être. Dans notre cas, l'état du personnage est sa position, nous créons donc un nœud pour chaque cellule de la grille:


Nœuds représentant les cellules de la grille.

Maintenant, ajoutez les côtes. Ils indiquent les états qui peuvent être "atteints" à partir de chaque état donné; dans notre cas, nous pouvons passer de n'importe quelle cellule à la suivante, à l'exception des cellules bloquées:


Les arcs indiquent les mouvements autorisés entre les cellules de la grille.

Si nous pouvons passer de A à B , alors nous disons que B est un «voisin» du nœud A.

Il convient de noter que les côtes ont une direction ; nous avons besoin d'arêtes de A à B et de B à A. Cela peut sembler superflu, mais pas lorsque des «conditions» plus complexes peuvent survenir. Par exemple, un personnage peut tomber du toit au sol, mais ne peut pas sauter du sol au toit. Vous pouvez passer de l'état "vivant" à l'état "mort", mais pas l'inverse. Et ainsi de suite.

Exemple

Supposons que nous voulons passer de A à T. Nous commençons par A. Vous pouvez faire exactement deux actions: aller en B ou aller en F.

Disons que nous sommes passés à B. Maintenant, nous pouvons faire deux choses: revenir à A ou aller à C. Nous nous souvenons que nous étions déjà en A et avons considéré les options là-bas, donc cela n'a aucun sens de le faire à nouveau (sinon nous pouvons passer toute la journée à déplacer A → B → A → B ...). Nous allons donc passer à C.

Étant en C , nous n'avons nulle part où aller. Revenir à B est inutile, c'est-à-dire que c'est une impasse. Choisir la transition vers B quand nous étions en A était une mauvaise idée; vous devriez peut-être essayer F à la place?

Nous répétons simplement ce processus jusqu'à ce que nous nous retrouvions en T. À ce moment, nous recréons simplement le chemin à partir de A , en revenant dans nos pas. Nous sommes en T ; comment en sommes-nous arrivés là? De o ? Autrement dit, la fin du chemin a la forme O → T. Comment sommes-nous arrivés à O ? Et ainsi de suite.

Gardez à l'esprit que nous ne bougeons pas vraiment; tout cela n'était qu'un processus de réflexion. Nous continuons de nous tenir en A , et nous n'en sortirons pas avant d'avoir trouvé tout le chemin. Quand je dis «déménagé en B », je veux dire «imaginez que nous avons déménagé en B ».

Algorithme général

Cette section est la partie la plus importante de tout l'article . Vous devez absolument le comprendre afin de pouvoir réaliser la recherche du chemin; le reste (y compris A * ) ne sont que des détails. Dans cette section, vous comprendrez jusqu'à ce que vous en compreniez le sens .

De plus, cette section est incroyablement simple.

Essayons de formaliser notre exemple, en le transformant en pseudo-code.

Nous devons suivre les nœuds que nous savons atteindre depuis le nœud de départ. Au début, ce n'est que le nœud de départ, mais dans le processus d '«exploration» de la grille, nous apprendrons comment accéder à d'autres nœuds. Appelons cette liste de nœuds reachable :

 reachable = [start_node] 

Nous devons également suivre les nœuds déjà examinés afin de ne pas les reconsidérer. explored les explored :

 explored = [] 

Ensuite, je décrirai le cœur de l'algorithme : à chaque étape de la recherche, nous sélectionnons l'un des nœuds que nous savons atteindre et regardons quels nouveaux nœuds nous pouvons en tirer. Si nous déterminons comment atteindre le nœud final (cible), le problème est résolu! Sinon, nous poursuivons la recherche.

Si simple, qu'est-ce qui déçoit même? Et c'est vrai. Mais c'est tout l'algorithme. Écrivons-le étape par étape avec un pseudo-code.

Nous continuons à chercher jusqu'à ce que nous arrivions au nœud final (dans ce cas, nous trouvons le chemin du nœud initial au nœud final), ou jusqu'à ce que nous manquions de nœuds dans lesquels vous pouvez rechercher (dans ce cas, il n'y a aucun moyen entre les nœuds de début et de fin) .

 while reachable is not empty: 

Nous choisissons l'un des nœuds vers lesquels nous savons arriver et qui n'a pas encore été étudié:

  node = choose_node(reachable) 

Si nous venons d'apprendre à se rendre au nœud final, la tâche est terminée! Nous avons juste besoin de construire le chemin en suivant les liens previous vers le nœud de départ:

  if node == goal_node: path = [] while node != None: path.add(node) node = node.previous return path 

Cela n'a aucun sens d'examiner le nœud plus d'une fois, nous allons donc suivre ceci:

  reachable.remove(node) explored.add(node) 

Nous identifions des nœuds que nous ne pouvons pas atteindre d'ici. Nous commençons par une liste de nœuds adjacents au nœud actuel et supprimons ceux que nous avons déjà examinés:

  new_reachable = get_adjacent_nodes(node) - explored 

Nous prenons chacun d'eux:

  for adjacent in new_reachable: 

Si nous savons déjà comment atteindre le nœud, ignorez-le. Sinon, ajoutez-le à la liste reachable , en suivant comment il y est entré:

  if adjacent not in reachable: adjacent.previous = node # Remember how we got there. reachable.add(adjacent) 

Trouver le nœud final est une façon de quitter la boucle. La seconde est lorsque l' reachable devient vide: nous n'avons plus de nœuds qui peuvent être explorés, et nous n'avons pas atteint le nœud final, c'est-à-dire qu'il n'y a aucun moyen de passer du nœud initial au nœud final:

 return None 

Et ... c'est tout. Il s'agit de l'algorithme entier, et le code de construction du chemin est alloué dans une méthode distincte:

 function find_path (start_node, end_node): reachable = [start_node] explored = [] while reachable is not empty: # Choose some node we know how to reach. node = choose_node(reachable) # If we just got to the goal node, build and return the path. if node == goal_node: return build_path(goal_node) # Don't repeat ourselves. reachable.remove(node) explored.add(node) # Where can we get from here? new_reachable = get_adjacent_nodes(node) - explored for adjacent in new_reachable: if adjacent not in reachable adjacent.previous = node # Remember how we got there. reachable.add(adjacent) # If we get here, no path was found :( return None 

Voici la fonction qui construit le chemin, en suivant les liens previous vers le nœud de départ:

 function build_path (to_node): path = [] while to_node != None: path.add(to_node) to_node = to_node.previous return path 

C’est tout. Il s'agit du pseudocode de chaque algorithme de recherche de chemin, y compris A * .

Relisez cette section jusqu'à ce que vous compreniez comment tout fonctionne et, plus important encore, pourquoi tout fonctionne. Il serait idéal de dessiner un exemple à la main sur papier, mais vous pouvez également regarder une démo interactive:

Démo interactive

Voici une démo et un exemple de l'implémentation de l'algorithme montré ci-dessus (vous pouvez l'exécuter sur la page de l'article original ). choose_node sélectionne simplement un nœud aléatoire. Vous pouvez démarrer l'algorithme étape par étape et consulter la liste des explored reachable et explored , ainsi que la destination previous liens previous .


Notez que la recherche se termine dès qu'un chemin est détecté; il peut arriver que certains nœuds ne soient même pas pris en compte.

Conclusion

L'algorithme présenté ici est un algorithme général pour tout algorithme de recherche de chemin.

Mais qu'est-ce qui distingue chaque algorithme d'un autre, pourquoi A * est A * ?

Voici un conseil: si vous exécutez la recherche dans la démo plusieurs fois, vous verrez que l'algorithme ne trouve pas toujours le même chemin. Il trouve un chemin, et ce chemin n'est pas nécessairement le plus court . Pourquoi?

Partie 2. Stratégies de recherche

Si vous ne comprenez pas complètement l'algorithme décrit dans la section précédente, revenez-y et relisez-le, car il est nécessaire pour comprendre d'autres informations. Lorsque vous le comprendrez, A * vous semblera tout à fait naturel et logique.

Ingrédient secret

À la fin de la partie précédente, j'ai laissé deux questions ouvertes: si chaque algorithme de recherche utilise le même code, pourquoi A * se comporte-t-il comme A * ? Et pourquoi la démo trouve-t-elle parfois des chemins différents?

Les réponses aux deux questions sont liées les unes aux autres. Bien que l'algorithme soit bien défini, j'ai laissé un aspect non résolu, et il s'avère que c'est la clé pour expliquer le comportement des algorithmes de recherche:

 node = choose_node(reachable) 

C'est cette chaîne à l'allure innocente qui distingue tous les algorithmes de recherche les uns des autres. choose_node dépend de la méthode d' choose_node de choose_node .

Alors pourquoi la démo trouve-t-elle des chemins différents? Parce que sa méthode choose_node sélectionne un nœud de manière aléatoire.

La longueur compte

Avant de plonger dans les différences de comportement de la fonction choose_node , nous devons corriger une petite erreur dans l'algorithme décrit ci-dessus.

Lorsque nous avons considéré les nœuds adjacents au courant, nous avons ignoré ceux qui savent déjà comment réaliser:

 if adjacent not in reachable: adjacent.previous = node # Remember how we got there. reachable.add(adjacent) 

C'est une erreur: que se passe-t-il si nous venons de découvrir la meilleure façon de s'y rendre? Dans ce cas, il est nécessaire de modifier le lien de nœud previous pour refléter ce chemin plus court.

Pour ce faire, nous devons connaître la longueur du chemin du nœud de départ à tout nœud accessible. Nous appellerons cela le coût du chemin. Pour l'instant, nous supposons que le passage d'un nœud à l'un des nœuds voisins a un coût constant de 1 .

Avant de commencer la recherche, nous attribuons la valeur de cost de chaque nœud à l' infinity ; grâce à cela, tout chemin sera plus court que cela. Nous allons également définir le cost nœud start_node sur 0 .

Voici à quoi ressemblera le code:

 if adjacent not in reachable: reachable.add(adjacent) # If this is a new path, or a shorter path than what we have, keep it. if node.cost + 1 < adjacent.cost: adjacent.previous = node adjacent.cost = node.cost + 1 

Même coût de recherche

Jetons maintenant un œil à la méthode choose_node . Si nous nous efforçons de trouver le chemin le plus court possible, alors choisir un nœud au hasard n'est pas une bonne idée.

Il est préférable de choisir un nœud que nous pouvons atteindre à partir du nœud initial le long du chemin le plus court; grâce à cela, nous préférons généralement les chemins plus courts aux plus longs. Cela ne signifie pas que les chemins plus longs ne seront pas du tout pris en compte, cela signifie que les chemins plus courts seront considérés en premier. Puisque l'algorithme se termine immédiatement après avoir trouvé un chemin approprié, cela devrait nous permettre de trouver des chemins courts.

Voici un exemple possible de la fonction choose_node :

 function choose_node (reachable): best_node = None for node in reachable: if best_node == None or best_node.cost > node.cost: best_node = node return best_node 

Intuitivement, la recherche de cet algorithme se développe «radialement» à partir du nœud de début jusqu'à ce qu'il atteigne le nœud de fin. Voici une démonstration interactive de ce comportement:

Conclusion

Un simple changement dans la méthode de choix du nœud considéré par les éléments suivants nous a permis d'obtenir un assez bon algorithme: il trouve le chemin le plus court du début au nœud final.

Mais cet algorithme, dans une certaine mesure, reste "stupide". Il continue de chercher partout jusqu'à ce qu'il tombe sur un nœud terminal. Par exemple, quel est le point dans l'exemple illustré ci-dessus pour rechercher dans la direction A , s'il est évident que nous nous éloignons du nœud final?

Est-il possible de rendre choose_node plus intelligent? Pouvons-nous lui faire diriger la recherche vers le nœud final , sans même connaître à l'avance le chemin correct?

Il s'avère que nous pouvons - dans la partie suivante, nous arrivons enfin à choose_node , qui nous permet de transformer l'algorithme de recherche de chemin général en A * .

Partie 3. Retirez le voile du secret de A *

L'algorithme obtenu dans la partie précédente est assez bon: il trouve le chemin le plus court du nœud de départ au nœud final. Cependant, il gaspille son énergie: il considère les façons qu'une personne appelle manifestement erronées - elles s'éloignent généralement du but. Comment éviter cela?

Algorithme magique

Imaginez que nous exécutions un algorithme de recherche sur un ordinateur spécial avec une puce qui peut faire de la magie . Grâce à cette puce incroyable, nous pouvons exprimer choose_node très simple, ce qui garantit de créer le chemin le plus court sans perdre de temps à explorer des chemins partiels qui ne mènent nulle part:

 function choose_node (reachable): return magic(reachable, " ,     ") 

Cela semble tentant, mais les puces magiques ont toujours besoin d'une sorte de code de bas niveau. Voici une bonne approximation:

 function choose_node (reachable): min_cost = infinity best_node = None for node in reachable: cost_start_to_node = node.cost cost_node_to_goal = magic(node, "   ") total_cost = cost_start_to_node + cost_node_to_goal if min_cost > total_cost: min_cost = total_cost best_node = node return best_node 

C'est une excellente façon de sélectionner le nœud suivant: vous sélectionnez un nœud qui nous donne le chemin le plus court du début au nœud final, ce dont nous avons besoin.

Nous avons également minimisé la quantité de magie utilisée: nous savons exactement quel est le coût du déplacement du nœud de départ à chaque nœud (c'est node.cost ), et nous utilisons la magie uniquement pour prédire le coût du déplacement du nœud au nœud final.

Pas magique, mais assez génial A *

Malheureusement, les puces magiques sont nouvelles et nous avons besoin de l'assistance d'un équipement obsolète. La plupart du code nous convient, à l'exception de cette ligne:

 # Throws MuggleProcessorException cost_node_to_goal = magic(node, "   ") 

Autrement dit, nous ne pouvons pas utiliser la magie pour découvrir le coût d'un chemin inexploré. Eh bien, faisons une prédiction. Nous serons optimistes et supposerons qu'il n'y a rien entre les nœuds actuels et finaux, et nous pouvons simplement nous déplacer directement:

 cost_node_to_goal = distance(node, goal_node) 

Notez que le chemin le plus court et la distance minimale sont différents: la distance minimale implique qu'il n'y a absolument aucun obstacle entre les nœuds actuels et finaux.

Cette estimation est assez simple à obtenir. Dans nos exemples de grille, il s'agit de la distance des blocs de ville entre deux nœuds (c'est-à-dire abs(Ax - Bx) + abs(Ay - By) ). Si nous pouvions nous déplacer en diagonale, alors la valeur serait sqrt( (Ax - Bx)^2 + (Ay - By)^2 ) , et ainsi de suite. Plus important encore, nous n'obtenons jamais une estimation de valeur trop élevée.

Voici donc une version non choose_node de choose_node :

 function choose_node (reachable): min_cost = infinity best_node = None for node in reachable: cost_start_to_node = node.cost cost_node_to_goal = estimate_distance(node, goal_node) total_cost = cost_start_to_node + cost_node_to_goal if min_cost > total_cost: min_cost = total_cost best_node = node return best_node 

Une fonction qui estime la distance du courant au nœud final est appelée heuristique , et cet algorithme de recherche, mesdames et messieurs, est appelé ... A * .

Démo interactive

Pendant que vous vous remettez du choc causé par la prise de conscience que le mystérieux A * est en fait si simple , vous pouvez regarder la démo (ou l'exécuter dans l' article original ). Vous remarquerez que, contrairement à l'exemple précédent, la recherche passe très peu de temps à se déplacer dans la mauvaise direction.

Conclusion

Enfin, nous sommes arrivés à l'algorithme A * , qui n'est rien de plus que l'algorithme de recherche général décrit dans la première partie de l'article avec quelques améliorations décrites dans la deuxième partie et en utilisant la fonction choose_node , qui sélectionne le nœud qui, à notre avis, nous rapproche de nœud d'extrémité. C’est tout.

Voici un pseudo-code complet de la méthode principale pour votre référence:

 function find_path (start_node, end_node): reachable = [start_node] explored = [] while reachable is not empty: # Choose some node we know how to reach. node = choose_node(reachable) # If we just got to the goal node, build and return the path. if node == goal_node: return build_path(goal_node) # Don't repeat ourselves. reachable.remove(node) explored.add(node) # Where can we get from here that we haven't explored before? new_reachable = get_adjacent_nodes(node) - explored for adjacent in new_reachable: # First time we see this node? if adjacent not in reachable: reachable.add(adjacent) # If this is a new path, or a shorter path than what we have, keep it. if node.cost + 1 < adjacent.cost: adjacent.previous = node adjacent.cost = node.cost + 1 # If we get here, no path was found :( return None 

Méthode build_path :

 function build_path (to_node): path = [] while to_node != None: path.add(to_node) to_node = to_node.previous return path 

Et voici la méthode choose_node , qui la transforme en A * :

 function choose_node (reachable): min_cost = infinity best_node = None for node in reachable: cost_start_to_node = node.cost cost_node_to_goal = estimate_distance(node, goal_node) total_cost = cost_start_to_node + cost_node_to_goal if min_cost > total_cost: min_cost = total_cost best_node = node return best_node 

C’est tout.

Mais pourquoi avons-nous besoin de la partie 4 ?

Maintenant que vous comprenez comment fonctionne A * , je veux parler de certains domaines étonnants de son application, qui sont loin d'être limités à trouver des chemins dans une grille de cellules.

Partie 4. A * en pratique

Les trois premières parties de l'article commencent par les fondements mêmes des algorithmes de recherche de chemin et se terminent par une description claire de l'algorithme A * . Tout cela est génial en théorie, mais comprendre comment cela est applicable dans la pratique est un sujet complètement différent.

Par exemple, que se passe-t-il si notre monde n'est pas une grille?

Que faire si un personnage ne peut pas pivoter instantanément de 90 degrés?

Comment construire un graphe si le monde est sans fin?

Et si nous ne nous soucions pas de la longueur du chemin, mais que nous dépendons de l'énergie solaire et que nous devons être sous le soleil autant que possible?

Comment trouver le chemin le plus court vers l'un des deux nœuds d'extrémité?

Fonction de coût

Dans les premiers exemples, nous avons recherché le chemin le plus court entre les nœuds de début et de fin. Cependant, au lieu de stocker des longueurs de chemin partielles dans la length variable, nous l'avons appelé cost . Pourquoi?

Nous pouvons faire en sorte que A * recherche non seulement le chemin le plus court , mais aussi le meilleur , et la définition du «meilleur» peut être choisie en fonction de nos objectifs. Lorsque nous avons besoin du chemin le plus court, le coût est la longueur du chemin, mais si nous voulons minimiser, par exemple, la consommation de carburant, nous devons l'utiliser comme coût. Si nous voulons maximiser le «temps passé sous le soleil», alors le coût est le temps passé sans soleil. Et ainsi de suite.

Dans le cas général, cela signifie que les coûts correspondants sont associés à chaque bord du graphique. Dans les exemples ci-dessus, la valeur a été définie implicitement et a toujours été considérée comme égale à 1 , car nous avons compté les étapes en cours de route. Mais nous pouvons changer le coût de la côte selon ce que nous voulons minimiser.

Fonction de critère

Disons que notre objet est une voiture et qu'il doit se rendre à la station-service. Tout ravitaillement nous conviendra. Il prend l'itinéraire le plus court jusqu'à la station-service la plus proche.

L'approche naïve consistera à calculer tour à tour le chemin le plus court vers chaque ravitaillement et à sélectionner le plus court. Cela fonctionnera, mais ce sera un processus assez coûteux.

Et si nous pouvions remplacer un goal_node par une méthode qui, sur un nœud donné, peut dire s'il est fini ou non. Grâce à cela, nous pouvons rechercher plusieurs objectifs en même temps. Nous devons également modifier l'heuristique afin qu'elle renvoie le coût estimé minimum de tous les nœuds d'extrémité possibles.

Selon les spécificités de la situation, nous ne pourrons peut-être pas atteindre l'objectif parfaitement , ou cela coûtera trop cher (si nous envoyons le personnage à travers une demi-carte énorme, la différence d'un pouce est-elle importante?), Donc la méthode is_goal_node peut retourner true lorsque nous Nous sommes "assez proches".

Aucune certitude n'est requise.

Représenter le monde comme une grille discrète peut ne pas être suffisant pour de nombreux jeux. Prenons, par exemple, un jeu de tir à la première personne ou un jeu de course. Le monde est discret, mais il ne peut pas être représenté comme une grille.

Mais il y a un problème plus grave: et si le monde était sans fin? Dans ce cas, même si nous pouvons le présenter sous forme de grille, alors nous ne pourrons tout simplement pas construire un graphe correspondant à la grille, car il doit être infini.

Cependant, tout n'est pas perdu. Bien sûr, pour l'algorithme de recherche de graphiques, nous avons certainement besoin d'un graphique. Mais personne n'a dit que le graphique devait être complet !

Si vous regardez attentivement l'algorithme, vous remarquerez que nous ne faisons rien avec le graphique dans son ensemble; nous examinons le graphe localement, obtenant des nœuds que nous pouvons atteindre à partir du nœud en question. Comme le montre la démo A * , certains nœuds du graphique ne sont pas du tout étudiés.

Alors pourquoi ne construisons-nous pas simplement le graphique dans le processus de recherche?

Nous faisons de la position actuelle du personnage le nœud de départ. Lors de l'appel à get_adjacent_nodes il peut déterminer les façons possibles dont le personnage peut se déplacer à partir d'un nœud donné et créer des nœuds voisins à la volée.

Au-delà de trois dimensions

Même si votre monde est vraiment un maillage 2D, il y a d'autres aspects à considérer. Par exemple, que faire si un personnage ne peut pas pivoter instantanément de 90 ou 180 degrés, comme c'est généralement le cas?

L'état représenté par chaque nœud de recherche ne doit pas être simplement une position ; au contraire, il peut comprendre un ensemble de valeurs arbitrairement complexes. Par exemple, si les virages à 90 degrés prennent autant de temps que la transition d'une cellule à une autre, l'état du personnage peut être défini comme [position, heading] . Chaque nœud peut représenter non seulement la position du personnage, mais aussi la direction de son regard; et les nouveaux bords du graphique (explicites ou indirects) reflètent cela.

Si vous revenez à la grille 5x5 d'origine, la position de recherche initiale peut maintenant être [A, East] . Les nœuds voisins sont maintenant [B, East] et [A, South] - si nous voulons atteindre F , nous devons d'abord ajuster la direction afin que le chemin prenne la forme [A, East] , [A, South] , [F, South] .

Tireur à la première personne? Au moins quatre dimensions: [X, Y, Z, Heading] . Peut-être même [X, Y, Z, Heading, Health, Ammo] .

Notez que plus l'état est complexe, plus la fonction heuristique doit être complexe. Un * lui - même est simple; l'art naît souvent d'une bonne heuristique.

Conclusion

Le but de cet article est de dissiper une fois pour toutes le mythe selon lequel A * est un algorithme mystique qui ne peut être déchiffré. Au contraire, j'ai montré qu'il n'y a rien de mystérieux et qu'en fait on peut tout simplement en déduire en partant de zéro.

Lectures complémentaires

Amit Patel a une excellente «Introduction à l'algorithme A *» (et ses autres articles sur divers sujets sont également excellents!).