Trouver son chemin - Pathfinding

Pour d'autres utilisations, voir Pathfinder (homonymie) .
Algorithmes de recherche de graphiques et d' arbres
Annonces
Rubriques connexes
Chemins équivalents entre A et B dans un environnement 2D

Pathfinding ou pathfining est le tracé, par une application informatique, du chemin le plus court entre deux points. C'est une variante plus pratique pour résoudre des labyrinthes . Ce domaine de recherche est fortement basé sur l'algorithme de Dijkstra pour trouver le chemin le plus court sur un graphe pondéré .

La recherche de chemin est étroitement liée au problème du chemin le plus court , au sein de la théorie des graphes , qui examine comment identifier le chemin qui répond le mieux à certains critères (le plus court, le moins cher, le plus rapide, etc.) entre deux points d'un grand réseau.

Algorithmes

À la base, une méthode de recherche de chemin recherche un graphe en commençant par un sommet et en explorant les nœuds adjacents jusqu'à ce que le nœud de destination soit atteint, généralement dans le but de trouver l'itinéraire le moins cher. Bien que les méthodes de recherche de graphique telles qu'une recherche en largeur d'abord trouveraient un itinéraire si elles avaient suffisamment de temps, d'autres méthodes, qui « explorent » le graphique, auraient tendance à atteindre la destination plus tôt. Une analogie serait une personne marchant à travers une pièce ; plutôt que d'examiner à l'avance tous les itinéraires possibles, la personne marcherait généralement dans la direction de la destination et ne s'écarterait du chemin que pour éviter un obstacle, et ferait des écarts aussi mineurs que possible.

Deux problèmes principaux de la recherche de chemin sont (1) de trouver un chemin entre deux nœuds dans un graphe ; et (2) le problème du chemin le plus court —pour trouver le chemin optimal le plus court . Les algorithmes de base tels que la recherche en largeur d'abord et en profondeur d'abord abordent le premier problème en épuisant toutes les possibilités ; à partir du nœud donné, ils parcourent tous les chemins potentiels jusqu'à ce qu'ils atteignent le nœud de destination. Ces algorithmes s'exécutent en , ou temps linéaire, où V est le nombre de sommets et E est le nombre d' arêtes entre les sommets.

Le problème le plus compliqué est de trouver le chemin optimal. L'approche exhaustive dans ce cas est connue sous le nom d' algorithme de Bellman-Ford , qui donne une complexité temporelle de , ou temps quadratique. Cependant, il n'est pas nécessaire d'examiner tous les chemins possibles pour trouver celui qui est optimal. Des algorithmes tels que A* et l'algorithme de Dijkstra éliminent stratégiquement les chemins, soit par heuristique, soit par programmation dynamique . En éliminant les chemins impossibles, ces algorithmes peuvent atteindre des complexités temporelles aussi faibles que .

Les algorithmes ci-dessus sont parmi les meilleurs algorithmes généraux qui fonctionnent sur un graphe sans prétraitement. Cependant, dans les systèmes de routage de voyage pratiques, des complexités temporelles encore meilleures peuvent être atteintes par des algorithmes qui peuvent prétraiter le graphe pour obtenir de meilleures performances. Un tel algorithme est les hiérarchies de contraction .

Algorithme de Dijkstra

Un exemple courant d'algorithme de recherche de chemin basé sur des graphes est l'algorithme de Dijkstra . Cet algorithme commence par un nœud de départ et un « ensemble ouvert » de nœuds candidats. A chaque étape, le nœud de l'ensemble ouvert avec la distance la plus faible depuis le début est examiné. Le nœud est marqué "fermé", et tous les nœuds adjacents sont ajoutés à l'ensemble ouvert s'ils n'ont pas déjà été examinés. Ce processus se répète jusqu'à ce qu'un chemin vers la destination ait été trouvé. Étant donné que les nœuds les plus éloignés sont examinés en premier, la première fois que la destination est trouvée, le chemin qui y mène sera le chemin le plus court.

L'algorithme de Dijkstra échoue s'il y a un poids de bord négatif . Dans la situation hypothétique où les nœuds A, B et C forment un graphe non orienté connecté avec des arêtes AB = 3, AC = 4 et BC = −2, le chemin optimal de A à C coûte 1 et le chemin optimal de A à B coûte 2. L'algorithme de Dijkstra à partir de A examinera d'abord B, car c'est le plus proche. Il lui attribuera un coût de 3, et le marquera comme fermé, ce qui signifie que son coût ne sera jamais réévalué. Par conséquent, Dijkstra ne peut pas évaluer les poids de bord négatifs. Cependant, étant donné qu'à de nombreuses fins pratiques, il n'y aura jamais de poids de bord négatif, l'algorithme de Dijkstra est largement adapté à la recherche de chemin.

Algorithme A*

A* est une variante de l'algorithme de Dijkstra couramment utilisé dans les jeux. A* attribue un poids à chaque nœud ouvert égal au poids du bord de ce nœud plus la distance approximative entre ce nœud et l'arrivée. Cette distance approximative est trouvée par l' heuristique , et représente une distance minimale possible entre ce nœud et la fin. Cela lui permet d'éliminer les chemins plus longs une fois qu'un chemin initial est trouvé. S'il existe un chemin de longueur x entre le début et la fin et que la distance minimale entre un nœud et la fin est supérieure à x, ce nœud n'a pas besoin d'être examiné.

A* utilise cette heuristique pour améliorer le comportement par rapport à l'algorithme de Dijkstra. Lorsque l'heuristique est évaluée à zéro, A* est équivalent à l'algorithme de Dijkstra. Au fur et à mesure que l'estimation heuristique augmente et se rapproche de la distance réelle, A* continue de trouver des chemins optimaux, mais s'exécute plus rapidement (en examinant moins de nœuds). Lorsque la valeur de l'heuristique est exactement la vraie distance, A* examine le moins de nœuds. (Cependant, il est généralement peu pratique d'écrire une fonction heuristique qui calcule toujours la vraie distance, car le même résultat de comparaison peut souvent être atteint en utilisant des calculs plus simples - par exemple, en utilisant la distance de Manhattan sur la distance euclidienne dans un espace à deux dimensions .) valeur de l'heuristique augmente, A* examine moins de nœuds mais ne garantit plus un chemin optimal. Dans de nombreuses applications (telles que les jeux vidéo), cela est acceptable et même souhaitable, afin que l'algorithme continue de fonctionner rapidement.

Exemple d'algorithme

Il s'agit d'un algorithme de recherche de chemin assez simple et facile à comprendre pour les cartes basées sur des tuiles. Pour commencer, vous disposez d'une carte, d'une coordonnée de départ et d'une coordonnée de destination. La carte ressemblera à ceci, Xétant des murs, Sétant le début, Oétant la fin et _étant des espaces ouverts, les nombres le long des bords supérieur et droit sont les numéros de colonne et de ligne : 

  1 2 3 4 5 6 7 8
X X X X X X X X X X
X _ _ _ X X _ X _ X 1
X _ X _ _ X _ _ _ X 2
X S X X _ _ _ X _ X 3
X _ X _ _ X _ _ _ X 4
X _ _ _ X X _ X _ X 5
X _ X _ _ X _ X _ X 6
X _ X X _ _ _ X _ X 7
X _ _ O _ X _ _ _ X 8
X X X X X X X X X X

Tout d'abord, créez une liste de coordonnées, que nous utiliserons comme file d'attente. La file d'attente sera initialisée avec une coordonnée, la coordonnée de fin. Chaque coordonnée aura également une variable de compteur attachée (le but de cela deviendra bientôt évident). Ainsi, la file d'attente commence par ((3,8,0)).

Ensuite, parcourez chaque élément de la file d'attente, y compris les nouveaux éléments ajoutés à la fin au cours de l'algorithme, et pour chaque élément, procédez comme suit :

  1. Créez une liste des quatre cellules adjacentes, avec une variable compteur de la variable compteur de l'élément actuel + 1 (dans notre exemple, les quatre cellules sont ((2,8,1),(3,7,1),(4, 8,1),(3,9,1)))
  2. Vérifiez toutes les cellules de chaque liste pour les deux conditions suivantes :
    1. Si la cellule est un mur, supprimez-la de la liste
    2. S'il y a un élément dans la liste principale avec la même coordonnée, supprimez-le de la liste des cellules
  3. Ajouter toutes les cellules restantes de la liste à la fin de la liste principale
  4. Aller à l'élément suivant de la liste

Ainsi, après le tour 1, la liste des éléments est la suivante : ((3,8,0),(2,8,1),(4,8,1))

  • Après 2 tours : ((3,8,0),(2,8,1),(4,8,1),(1,8,2),(4,7,2))
  • Après 3 tours : (...(1,7,3),(4,6,3),(5,7,3))
  • Après 4 tours : (...(1,6,4),(3,6,4),(6,7,4))
  • Après 5 tours : (...(1,5,5),(3,5,5),(6,6,5),(6,8,5))
  • Après 6 tours : (...(1,4,6),(2,5,6),(3,4,6),(6,5,6),(7,8,6))
  • Après 7 tours : (...(1,3,7)) - problème résolu, terminez cette étape de l'algorithme - notez que si vous avez plusieurs unités pourchassant la même cible (comme dans de nombreux jeux - la fin pour commencer approche de l'algorithme est destiné à rendre cela plus facile), vous pouvez continuer jusqu'à ce que toute la carte soit occupée, que toutes les unités soient atteintes ou qu'une limite de compteur définie soit atteinte

Maintenant, mappez les compteurs sur la carte, obtenant ceci : 

  1 2 3 4 5 6 7 8
X X X X X X X X X X
X _ _ _ X X _ X _ X 1
X _ X _ _ X _ _ _ X 2
X S X X _ _ _ X _ X 3
X 6 X 6 _ X _ _ _ X 4
X 5 6 5 X X 6 X _ X 5
X 4 X 4 3 X 5 X _ X 6
X 3 X X 2 3 4 X _ X 7
X 2 1 0 1 X 5 6 _ X 8
X X X X X X X X X X

Maintenant, commencez à S (7) et allez à la cellule voisine avec le numéro le plus bas (les cellules non cochées ne peuvent pas être déplacées). Le chemin tracé est (1,3,7) -> (1,4,6) -> (1,5,5) -> (1,6,4) -> (1,7,3) -> ( 1,8,2) -> (2,8,1) -> (3,8,0). Dans le cas où deux nombres sont également bas (par exemple, si S était à (2,5)), choisissez une direction aléatoire - les longueurs sont les mêmes. L'algorithme est maintenant terminé.

Dans les jeux vidéo

Chris Crawford en 1982 a décrit comment il a « passé beaucoup de temps » à essayer de résoudre un problème de recherche de chemin dans Tanktics , dans lequel des réservoirs d'ordinateurs se sont retrouvés piégés sur terre dans des lacs en forme de U. "Après beaucoup d'efforts inutiles, j'ai découvert une meilleure solution : supprimer les lacs en forme de U de la carte", a-t-il déclaré.

Recherche de chemin hiérarchique

Les quadtrees peuvent être utilisés pour la recherche de chemin hiérarchique

L'idée a d'abord été décrite par l' industrie du jeu vidéo , qui avait besoin de planifier de grandes cartes avec un temps CPU réduit . Le concept d'utilisation de l'abstraction et de l' heuristique est plus ancien et a été mentionné pour la première fois sous le nom d'ABSTRIPS (Abstraction-Based STRIPS ) qui était utilisé pour rechercher efficacement les espaces d'état des jeux logiques. Une technique similaire est celle des maillages de navigation (navmesh), qui sont utilisés pour la planification géométrique dans les jeux et la planification du transport multimodal qui est utilisée dans les problèmes des vendeurs ambulants avec plus d'un véhicule de transport.

Une carte est séparée en clusters . Sur la couche de haut niveau, le chemin entre les clusters est prévu. Une fois le plan trouvé, un deuxième chemin est planifié au sein d'un cluster au niveau inférieur. Cela signifie que la planification se fait en deux étapes qui sont une recherche locale guidée dans l'espace d'origine. L'avantage est que le nombre de nœuds est plus petit et que l'algorithme fonctionne très bien. L'inconvénient est qu'un planificateur de chemin hiérarchique est difficile à mettre en œuvre.

Exemple

Une carte a une taille de 3000x2000 pixels . La planification d'un chemin sur une base de pixels prendrait beaucoup de temps. Même un algorithme efficace devra calculer de nombreux graphes possibles. La raison en est qu'une telle carte contiendrait 6 millions de pixels au total et les possibilités d'explorer l'espace géométrique sont extrêmement grandes. La première étape pour un planificateur de chemin hiérarchique consiste à diviser la carte en sous-cartes plus petites. Chaque cluster a une taille de 300x200 pixels. Le nombre total de clusters est de 10x10=100. Dans le graphique nouvellement créé, le nombre de nœuds est faible, il est possible de naviguer entre les 100 clusters, mais pas dans la carte détaillée. Si un chemin valide a été trouvé dans le graphique de haut niveau, l'étape suivante consiste à planifier le chemin au sein de chaque cluster. La sous-carte a 300x200 pixels qui peuvent être facilement gérées par un planificateur de chemin A* normal .

Algorithmes utilisés dans la recherche de chemin

Recherche de chemin multi-agent

La recherche de chemin multi-agents consiste à trouver les chemins de plusieurs agents de leurs emplacements actuels à leurs emplacements cibles sans entrer en collision les uns avec les autres, tout en optimisant en même temps une fonction de coût, telle que la somme des longueurs de chemin de tous les agents. C'est une généralisation du pathfinding. De nombreux algorithmes de recherche de chemin multi-agents sont généralisés à partir de A*, ou basés sur la réduction à d'autres problèmes bien étudiés tels que la programmation linéaire en nombres entiers. Cependant, de tels algorithmes sont généralement incomplets ; en d'autres termes, il n'a pas été prouvé qu'il produisait une solution en temps polynomial. Une autre catégorie d'algorithmes sacrifie l'optimalité pour les performances en utilisant soit des modèles de navigation connus (tels que le flux de trafic), soit la topologie de l'espace du problème.

Voir également

Les références

Liens externes