Share
Dans ce tutoriel, je vais expliquer recherche de champ de vecteur et ses avantages par rapport aux algorithmes de recherche de chemins plus traditionnels, tels que ceux de Dijkstra. Une compréhension de base de l'algorithme de Dijkstra et des champs potentiels vous aidera à comprendre cet article, mais n'est pas obligatoire.
La recherche de parcours pose de nombreuses solutions et chacune a ses avantages et ses inconvénients. De nombreux algorithmes de recherche de chemin fonctionnent en calculant un chemin d'accès à l'objectif pour chaque chemineur, ce qui signifie que la recherche de cheminement prendra deux fois plus de temps à calculer avec deux fois plus de cheminés. Ceci est acceptable dans de nombreuses situations, mais lorsque vous travaillez avec des milliers de pathfinders, une approche plus efficace est possible..
Connu comme recherche de champ de vecteur, Cette approche calcule le chemin entre l'objectif et chaque nœud du graphique. Pour solidifier cette explication du chemin de champ vectoriel, je vais expliquer l'algorithme en utilisant ma mise en oeuvre particulière à titre d'exemple..
Remarque: Le cheminement de champ de vecteur peut être résumé aux noeuds et aux graphiques en général; ce n’est pas parce que j’explique en utilisant mon approche basée sur les tuiles et la grille que cet algorithme est limité aux mondes basés sur les tuiles!
Le cheminement de champ vectoriel est composé de trois étapes.
Cette vidéo vous montre les résultats finaux, puis vous donne un aperçu général des concepts présentés dans le tutoriel complet ci-dessous:
La heatmap enregistre la distance parcourue entre l’objectif et chaque tuile de la carte. La distance du trajet est distincte de la distance euclidienne en ce sens qu'il s'agit du calcul de la distance entre deux points ne traversant que des terrains traversables. Un GPS, par exemple, calcule toujours la distance parcourue, les routes étant le seul terrain traversable..
Ci-dessous, vous pouvez voir la différence entre la distance du trajet et la distance linéaire entre le but (marqué en rouge) et une tuile quelconque (en rose). Les tuiles non traversables sont dessinées en vert. Comme vous pouvez le constater, la distance de parcours (indiquée en jaune) est 9, tandis que la distance linéaire (en bleu clair) est approximativement 4.12.
Les chiffres en haut à gauche de chaque mosaïque indiquent la distance de parcours par rapport à l'objectif calculé par l'algorithme de génération de heatmap. Notez qu'il existe plus d'une distance de trajet possible entre deux points; dans cet article, nous ne nous intéressons qu'au plus court.
L’algorithme de génération de heatmap est un algorithme de front d'onde. Il commence au but avec une valeur de 0, puis s'écoule vers l'extérieur pour remplir toute la région traversable. L'algorithme de front d'onde comporte deux étapes:
Accentsconagua
0.la distance de chemin de la tuile précédente + 1.Remarque: L'algorithme de front d'onde effectue simplement une première recherche en profondeur sur la grille et stocke le nombre d'étapes nécessaires pour atteindre chaque mosaïque le long du chemin. Cet algorithme est parfois aussi appelé le algorithme de coup de pinceau.
Maintenant que la distance de parcours de chaque tuile à l'objectif a été calculée, nous pouvons facilement déterminer le chemin à suivre pour se rapprocher de l'objectif. Il est possible de le faire au moment de l'exécution pour chaque pathfinder à chaque image, mais il est souvent préférable de calculer un champ de vecteurs une fois, puis de faire en sorte que tous les pathfinders se réfèrent au champ de vecteurs au moment de l'exécution.
Le champ de vecteurs stocke simplement un vecteur qui pointe vers le bas le gradient de la fonction de distance (vers l'objectif) sur chaque mosaïque. Voici une visualisation du champ de vecteurs, avec les vecteurs pointant du centre du carreau le long du chemin le plus court vers l’objectif (de nouveau affiché en rouge).
Ce champ de vecteurs est généré une tuile à la fois en regardant la carte thermique. Les composantes x et y du vecteur sont calculées séparément, comme indiqué dans le pseudocode ci-dessous:
Vector.x = left_tile.distance - right_tile.distance Vector.y = up_tile.distance - down_tile.distance
Remarque: La variable de distance de chaque mosaïque stocke la distance du chemin vers l'objectif telle que calculée par l'algorithme de front d'onde ci-dessus.
Si l'une des mosaïques référencée (gauche / droite / haut / bas) ne peut pas être parcourue et n'a donc aucune distance utilisable stockée, la distance associée à la mosaïque actuelle est utilisée à la place de la valeur manquante. Une fois que le vecteur de chemin a été calculé approximativement, il est normalisé pour éviter les incohérences ultérieurement.
Maintenant que le champ de vecteurs a été calculé, il est très facile de calculer le mouvement pour un pathfinder. En supposant que vector_field (x, y) retourne le vecteur que nous avons calculé précédemment au niveau de la tuile (x, y), et que désiré_vitesse est un scalaire, le pseudocode pour calculer la vitesse d'une particule à la tuile (x, y) ressemble à ça:
velocity_vector = vecteur_field (x, y) * désiré_vitesse
Les particules doivent simplement commencer à se déplacer dans la direction indiquée par le vecteur. C'est le moyen le plus simple de le faire, mais des systèmes de mouvement plus complexes peuvent facilement être mis en œuvre à l'aide de champs de flux..
Par exemple, les techniques expliquées dans Comprendre les comportements de pilotage pourraient être appliquées aux mouvements de trajectoire. Dans une telle situation, le vélocité_vecteur nous avons calculé ci-dessus serait utilisé comme la vitesse désirée, et les comportements de direction seraient utilisés pour calculer le mouvement réel à chaque pas de temps.
Lors du calcul du mouvement, il existe parfois un problème, connu sous le nom de Optima local. Cela se produit lorsqu'il y a deux chemins optimaux (les plus courts) à suivre pour atteindre l'objectif à partir d'une tuile donnée..
Ce problème peut être vu dans l'image ci-dessous. La tuile (en rose) située immédiatement à gauche du centre du mur comporte un vecteur de tracé dont les composantes (x et y) sont égales à 0.
Les optima locaux provoquent le blocage des éclaireurs; ils se réfèreront au champ de vecteur qui n'indiquera pas la direction à prendre. Lorsque cela se produit, les indicateurs de trajectoire resteront au même emplacement, sauf si un correctif est implémenté..
Le moyen le plus élégant (j'ai trouvé) de résoudre le problème est de subdiviser une seule fois la carte thermique et le champ vectoriel. Chaque vignette thermique et champ de vecteur a maintenant été divisée en quatre plus petites. Le problème reste le même avec une grille subdivisée; il n'a été que légèrement minimisé.
Le vrai truc qui résout le problème d'optima local consiste à ajouter initialement quatre nœuds d'objectif, au lieu d'un seul. Pour ce faire, il suffit de modifier la première étape de l'algorithme de génération de heatmap. Lorsque nous n’utilisions qu’un seul objectif avec une distance de chemin de 0, nous ajoutons maintenant les quatre tuiles les plus proches du but..
Il existe plusieurs façons de choisir les quatre tuiles, mais la façon dont elles sont choisies est en grande partie hors de propos - tant que les quatre tuiles sont adjacentes (et peuvent être traversées), cette technique devrait fonctionner..
Voici le pseudocode modifié pour la génération de heatmap:
0.la distance de chemin de la tuile précédente + 1.Et maintenant, voici les résultats finaux, montrant clairement que le problème d'optima local a été éliminé:
Bien que cette solution soit élégante, elle est loin d’être idéale. Son utilisation signifie que le calcul de la heatmap et du champ vectoriel prend quatre fois plus de temps en raison du nombre accru de tuiles..
D'autres solutions nécessitent de faire des vérifications, puis de déterminer la direction à prendre au cas par cas, ce qui ralentit considérablement les calculs de mouvement des particules. Dans mon cas, la subdivision des cartes était la meilleure option.
Espérons que ce didacticiel vous ait appris comment implémenter une recherche de cheminement basée sur des objectifs dans un monde basé sur des tuiles. Gardez à l'esprit que ce type de recherche de cheminement est fondamentalement simple: les particules suivent le gradient de la fonction de distance vers l'objectif.
La mise en œuvre est plus complexe, mais peut être décomposée en trois étapes faciles à gérer:
J'espère voir les gens développer les idées présentées ici. Comme toujours, si vous avez des questions, n'hésitez pas à les poser dans les commentaires ci-dessous!
