Trouver un moyen parmi les obstacles ronds

Navigation forestière

Un * Path Finder Algorithm est un outil puissant pour générer rapidement des chemins optimaux. Habituellement, A * est affiché lors de la navigation dans les cartes à partir des grilles, mais il peut être utilisé non seulement pour les grilles! Il peut fonctionner avec n'importe quel graphique. Vous pouvez utiliser A * pour trouver votre chemin dans le monde des obstacles ronds.


Dans l' article original, toutes les images sont interactives.

Comment un algorithme résout-il ces deux problèmes? Commençons par une brève description du fonctionnement d'A *.

Algorithme A *

L'algorithme A * trouve le chemin optimal du début au point final, en évitant les obstacles en cours de route. Il s'en rend compte, élargissant progressivement de nombreux chemins partiels . Chaque chemin partiel est une série d'étapes allant du point de départ à un point intermédiaire sur la route du but. Dans le processus de travail A *, les chemins partiels se rapprochent du point final. L'algorithme cesse de fonctionner lorsqu'il trouve le chemin complet, ce qui est meilleur que les options restantes, et cela peut être prouvé.

À chaque étape de l'algorithme, A * évalue l'ensemble des chemins partiels et génère de nouveaux chemins, développant le chemin le plus prometteur hors de l'ensemble. Pour ce faire, A * stocke les chemins partiels dans une file d'attente prioritaire, triés par longueur approximative - la vraie longueur de chemin mesurée plus la distance restante approximative jusqu'à la cible. Cette approximation doit être sous-estimée ; c'est-à-dire que l'approximation peut être inférieure à la vraie distance, mais pas supérieure à celle-ci. Dans la plupart des tâches de recherche de chemin, une bonne estimation sous-estimée est la distance géométrique en ligne droite entre la fin du chemin partiel et le point final. Le vrai meilleur chemin vers le but depuis la fin du chemin partiel peut être plus long que cette distance en ligne droite, mais ne peut pas être plus court.

Lorsque A * démarre, la file d'attente prioritaire ne contient qu'un seul chemin partiel: le point de départ. L'algorithme supprime à plusieurs reprises le chemin le plus prometteur de la file d'attente prioritaire, c'est-à-dire le chemin avec la plus petite longueur approximative. Si ce chemin se termine au point de terminaison, alors l'algorithme a terminé la tâche - la file d'attente prioritaire garantit qu'aucun autre chemin ne peut être meilleur. Sinon, à partir de la fin du chemin partiel qu'il a supprimé de la file d'attente, A * génère plusieurs nouveaux chemins, faisant des pas unitaires dans toutes les directions possibles. Il remet ces nouveaux chemins dans la file d'attente prioritaire et recommence le processus.

Compter

A * fonctionne avec un graphe : un ensemble de nœuds reliés par des arêtes . Dans un monde basé sur une grille, chaque nœud désigne une cellule de maillage distincte, et chaque bord est une connexion aux cellules voisines au nord, au sud, à l'est ou à l'ouest.

Avant de pouvoir exécuter A * pour la forêt à partir d'obstacles ronds, nous devons le convertir en graphique. Tous les chemins à travers la forêt sont constitués de segments alternés de lignes et d'arcs. Ce sont les bords du graphique du chemin. Les extrémités de ces bords deviennent des nœuds.

Un chemin à travers un graphique est une série de nœuds reliés par des bords:


Les segments et les arcs sont tous deux des bords du graphique. Nous appellerons les segments les bords de transition , car le chemin les utilise pour se déplacer entre les obstacles. Nous appelons arcs les bords enveloppants , car leur tâche en cours de route est de contourner les côtés des obstacles.

Ensuite, nous explorerons un moyen simple de transformer une forêt avec des obstacles en graphique: nous générerons toutes les arêtes de transition et enveloppes possibles des arêtes.

Transition Edge Generation

Les bords de la transition entre une paire de cercles sont des segments de ligne qui touchent à peine les deux cercles; ces segments sont appelés tangentes à deux points , et pour chaque paire de cercles, il y a quatre tangentes de ce type. Les tangentes à deux points qui se croisent entre les cercles sont appelées tangentes internes à deux points , et celles qui passent à l'extérieur sont appelées externes .

Tangentes intérieures à deux points

Dans le passé, la recherche de tangentes internes était importante pour calculer la longueur de la courroie reliant deux poulies de tailles différentes, de sorte que la tâche de créer des tangentes internes à deux points s'appelle le problème des courroies . Pour trouver les tangentes internes à deux points, vous devez calculer l'angle $$$\ theta$ dans le dessin ci-dessous.


Il s'est avéré que, pour les cercles avec des centres $$$A$ et $$$B$ et rayons $$$r_A$ et $$$r_B$ dont les centres sont à distance $$$d$ :

$$

$$\ theta = \ arccos {{r_A + r_B} \ over {d}}$$

Définition $$$\ theta$ on peut facilement trouver les points $$$C$ , $$$D$ , $$$E$ et $$$F$ .

Tangentes externes à deux points

Lors de la construction de tangentes externes (c'est la tâche des poulies ), une technique similaire est utilisée.


Pour les tangentes externes, nous pouvons trouver $$$\ theta$ comme suit:

$$

$$\ theta = \ arccos {{\ lvert r_A - r_B \ rvert} \ over d}$$

Peu importe lequel des cercles est plus grand, A ou B, mais comme vous pouvez le voir sur l'image, $$$\ theta$ posé sur le côté A le plus proche de B, mais sur le côté B le plus éloigné de A.

Ligne de vue

Pris ensemble, les tangentes internes et externes à deux points entre les deux cercles forment les bords de la transition entre les cercles. Mais que se passe-t-il si un ou plusieurs bords de transition ferment le troisième cercle?


Si le bord de transition est chevauché par un autre cercle, alors nous devons éliminer ce bord. Pour reconnaître un tel cas, nous utilisons un calcul simple de la distance entre un point et une ligne . Si la distance entre le bord de transition et le centre de l'obstacle est inférieure au rayon de l'obstacle, alors l'obstacle chevauche le bord de transition, nous devons donc le jeter.

Pour calculer la distance d'un point $$$C$ à un segment de ligne droite $$$\ overline {AB}$ nous utiliserons la méthode suivante :

Tout d'abord, nous calculons $$$u$ - une partie de la distance le long du segment $$$\ overline {AB}$ où la perpendiculaire coupe le point $$$C$ :

$$

$$u = {(C - A) \ cdot (B-A) \ over (B-A) \ cdot (B-A)}$$

Ensuite, nous calculons la position $$$E$ sur $$$\ overline {AB}$ :

$$

$$E = A + \ mathrm {clamp} (u, 0, 1) * (B - A)$$

La distance $$$d$ de $$$C$ couper $$$\ overline {AB}$ La distance de $$$C$ avant $$$E$ :

$$

$$d = \ | E - C \ |$$

Depuis $$$d <r$ , le cercle chevauche la ligne de visée de $$$A$ dans $$$B$ et le bord doit être jeté. Si $$$d \ ge r$ puis la ligne de vue de $$$A$ dans $$$B$ existe et la côte doit être laissée.

Génération d'enveloppe de bord

Les nœuds du graphique relient le bord de transition au bord de l'enveloppe. Dans les sections précédentes, nous avons généré des arêtes de transition. Pour générer les enveloppes des bords, nous partons du point final du bord de transition, faisons le tour du cercle et terminons au point final d'un autre bord de transition.


Pour trouver l'ensemble des enveloppes des bords d'un cercle, on trouve d'abord tous les bords de la transition qui sont tangents au cercle. Créez ensuite les enveloppes des bords entre tous les points d'extrémité des bords de transition sur le cercle.

Tout mettre ensemble

Après avoir généré des arêtes de transition, des enveloppes d'arêtes et de nœuds, puis éliminé toutes les arêtes de transition qui se chevauchent, nous pouvons créer un graphique et commencer à rechercher le chemin à l'aide de l'algorithme A *.

Améliorations

La procédure de génération de graphe que nous avons examinée fonctionne assez bien pour expliquer l'algorithme, mais peut être améliorée à bien des égards. De telles améliorations permettront à l'algorithme de dépenser moins de ressources CPU et mémoire, ainsi que de gérer plus de situations. Regardons quelques-unes des situations.

Obstacles qui se concernent

Vous avez peut-être remarqué que dans les exemples ci-dessus, les obstacles ronds ne se chevauchaient pas et ne se touchaient même pas. En supposant que les cercles peuvent se toucher, cela complique la tâche de trouver le chemin

Tangentes à deux points

Rappelons que les tangentes à deux points peuvent être trouvées en utilisant cette formule pour les tangentes internes:

$$

$$\ theta = \ arccos {{r_A + r_B} \ over {d}}$$

et formules pour tangentes externes:

$$

$$\ theta = \ arccos {{\ lvert r_A - r_B \ rvert} \ over d}$$

Lorsque deux cercles se touchent ou se croisent, il n'y a pas de tangente interne entre eux. Dans ce cas $$${r_A + r_B} \ sur d$ plus d'un. Étant donné que la valeur de l'arccosine est en dehors du domaine de la définition $$$[- 1, 1]$ non défini, il est important de vérifier l'intersection des cercles avant de trouver l'arc cosinus.

De même, si un cercle est complètement situé dans un autre, il n'y aura pas de tangentes externes entre eux. Dans ce cas $$${r_A - r_B} \ sur d$ hors de portée $$$[- 1, 1]$ c'est-à-dire qu'il n'a pas d'arc cosinus.

Ligne de visibilité des bords de transition

Si nous autorisons la possibilité de toucher ou de franchir des obstacles, de nouveaux cas apparaissent dans les calculs de la ligne de visée des bords de transition.

Rappeler le calcul $$$u$ - partie de la distance le long du bord de la transition à laquelle la perpendiculaire au point touche le bord. Si toucher les cercles n'est pas autorisé, la valeur $$$u$ hors de portée $$$[0,1]$ c'est-à-dire que le cercle ne peut pas toucher le bord, car pour cela il devrait toucher l'un des points d'extrémité du bord. Cela n'est pas possible car les extrémités d'une arête sont déjà tangentes à d'autres cercles.

Cependant, si nous permettons la possibilité de cercles qui se chevauchent, les valeurs $$$u$ hors de portée $$$[0,1]$ peut chevaucher la ligne de visée le long du bord. Cela correspond aux cas où le cercle est situé au-delà de l'extrémité du bord de transition, mais chevauche ou touche le point final. Pour suivre de tels cas mathématiquement, nous limiterons $$$u$ intervalle $$$[0,1]$ :

$$

$$E = A + pince (u, 0, 1) * (B - A)$$

Ligne de vue de l'enveloppe

Lorsque des obstacles peuvent se toucher ou se croiser, les enveloppes des bords peuvent être bloquées par des obstacles de la même manière que les bords de transition. Considérez le bord de l'enveloppe de la figure ci-dessous. Si l'enveloppe de la côte touche un autre obstacle, la côte est bloquée et doit être jetée.


Pour déterminer si l'enveloppe du bord est bloquée par un autre obstacle, nous utilisons la méthode suivante pour déterminer les points d'intersection de deux cercles. Si les cercles ont des centres aux points $$$A$ et $$$B$ et rayons $$$r_A$ et $$$r_B$ où $$$d$ - distance entre $$$A$ et $$$B$ , pour commencer, nous devons vérifier plusieurs cas. Si les cercles ne se touchent pas (c.-à-d. $$$d> r_A + r_B$ ),
sont l'un dans l'autre ( $$$d <| r_A - r_B |$ ) ou match ( $$$d = 0$ et $$$r_A = r_B$ ), les cercles ne peuvent donc pas affecter les enveloppes des uns et des autres.

Si aucune de ces conditions n'est remplie, les cercles se coupent en deux points; si les cercles se touchent, alors ces deux points coïncident. Considérez l' axe radical reliant les points d'intersection; il est perpendiculaire à la ligne reliant $$$A$ et $$$B$ à un moment donné $$$C$ . On peut calculer la distance $$$a$ de $$$A$ avant $$$C$ comme suit:

$$

$$a = {r_A ^ 2 - r_B ^ 2 + d ^ 2 \ sur 2d}$$

Trouver $$$a$ on peut trouver l'angle $$$\ theta$ :

$$

$$\ theta = \ arccos {a \ over r_A}$$

Si $$$\ theta$ est nul, alors les cercles se touchent $$$C$ . Sinon, il y a deux points d'intersection correspondant à positif et négatif $$$\ theta$ .


Ensuite, nous déterminons si l'un des points d'intersection se situe entre les points de début et de fin de l'enveloppe de l'arête. Si c'est le cas, l'obstacle bloque le bord de l'enveloppe et nous devons jeter ce bord. Notez que nous n'avons pas besoin de considérer le cas où l'enveloppe du bord est entièrement à l'intérieur de l'obstacle, car l'écrêtage le long de la ligne de visée pour les bords de transition a déjà rejeté ce bord.

Après avoir modifié le calcul des tangentes à deux points et la ligne de visée des bords de transition et des enveloppes des bords, tout fonctionne correctement.

Rayon d'acteur variable et extension de Minkowski

Lors du calcul de la navigation d'un objet rond dans le monde des obstacles circulaires, on peut prendre en compte des observations qui simplifient la solution du problème. Tout d'abord, on peut simplifier le travail en notant que le mouvement d'un cercle de rayon r à travers la forêt est similaire au mouvement d'un point à travers la même forêt avec un seul changement: le rayon de chaque obstacle augmente de r . Il s'agit d'un cas extrêmement simple d'application de la somme de Minkowski . Si le rayon de l'acteur est supérieur à zéro, alors avant de commencer, nous augmentons simplement la taille des obstacles.

Génération de bords différés

En général, un graphique pour une forêt de $$$n$ obstacles contient $$$O (n ^ 2)$ bords de transition, mais comme chacun d'eux doit être vérifié pour la ligne de vue avec $$$n$ obstacles, la durée totale de génération du graphe est $$$O (n ^ 3)$ . De plus, des paires de bords de transition peuvent conduire à la création de bords d'enveloppe, et chacun d'eux doit être vérifié avec chaque obstacle pour la ligne de visée. Cependant, en raison de la grande efficacité de l'algorithme A *, il ne regarde généralement qu'une partie de ce grand graphique pour créer le chemin optimal.

Nous pouvons gagner du temps en générant de petites parties du graphique à la volée pendant l'exécution de l'algorithme A *, plutôt que de faire tout le travail à l'avance. Si A * trouve rapidement le chemin, nous ne générerons qu'une petite partie du graphique. Pour ce faire, nous déplaçons la génération de bord vers la fonction neighbors() .

Il y a plusieurs cas. Au début de l'algorithme, nous avons besoin de voisins du point de départ. Ce sont les bords de la transition du point de départ aux bords gauche et droit de chaque obstacle.

Le cas suivant est celui où A * vient d'arriver au point $$$p$ au bord d'un obstacle $$$C$ le long du bord de transition: les neighbors() doivent renvoyer les enveloppes des bords menant de $$$p$ . Pour ce faire, nous déterminons quelles arêtes de transition sortent de l'obstacle en calculant les tangentes à deux points entre $$$C$ et tous les autres obstacles, en éliminant tous ceux qui ne sont pas en vue. On retrouve ensuite toutes les enveloppes des bords se connectant $$$p$ avec ces bords de transition, laissant tomber ceux qui sont bloqués par d'autres obstacles. Nous renvoyons toutes ces enveloppes des bords, en sauvegardant les bords de transition pour le retour dans un appel ultérieur aux neighbors() .

Le dernier cas est celui où A * a contourné le bord de l'enveloppe le long de l'obstacle $$$C$ et il doit partir $$$C$ le long du bord de la transition. Étant donné que l'étape précédente a calculé et enregistré toutes les arêtes de transition, vous pouvez simplement rechercher et renvoyer l'ensemble d'arêtes correct.

Nous coupons les enveloppes pointues des côtes

Les bords d'enveloppe relient les bords de transition touchant un cercle, mais il s'avère que bon nombre de ces bords d'enveloppe ne conviennent pas pour une utilisation optimale. Nous pouvons accélérer l'algorithme en les éliminant.

Le chemin optimal à travers la forêt d'obstacles consiste toujours à alterner des bords de transition et des enveloppes de bords. Supposons que nous entrons dans un nœud $$$A$ et décidez comment vous en sortir:


Connectez-vous via $$$A$ signifie que nous allons dans le sens horaire ( $$$\ circlearrowright$ ) Nous devons sortir par le nœud, ce qui nous permet de continuer à se déplacer dans le sens horaire ( $$$\ circlearrowright$ ), c'est-à-dire que nous ne pouvons sortir que par le nœud $$$B$ ou $$$D$ . Si vous sortez par $$$C$ puis une inflexion ( $$$\ curlywedge$ ) des moyens qui ne seront jamais optimaux. Nous devons filtrer ces bords pointus.

Tout d'abord, notez que A * traite de toute façon chaque bord non orienté. $$$P \ longleftrightarrow Q$ comme deux bords orientés $$$P \ longrightarrow Q$ et $$$Q \ longrightarrow P$ . Nous pouvons en profiter en marquant les bords et les nœuds avec une orientation.

1. Noeuds $$$P$ devenir des nœuds avec une orientation - dans le sens horaire ( $$$P \ circlearrowright$ ) ou dans le sens antihoraire ( $$$P \ circlearrowleft$ ) flèches.
2. Bords de transition non orientés $$$P \ longleftrightarrow Q$ devenir des bords orientés $$$P, p \ longrightarrow Q, \ hat {q}$ et $$$Q, q \ longrightarrow P, \ hat {p}$ où $$$p$ et $$$q$ Sont des orientations, et $$$\ chapeau {x}$ signifie la direction opposée $$$x$ .
3. Enveloppes côtelées non orientées $$$P \ longleftrightarrow Q$ devenir des bords orientés $$$P \ circlearrowright \ longrightarrow Q \ circlearrowright$ et $$$P \ circlearrowleft \ longrightarrow Q \ circlearrowleft$ . C'est là que se produit le filtrage: nous n'activons pas $$$P \ circlearrowright \ longrightarrow Q \ circlearrowleft$ et $$$P \ circlearrowleft \ longrightarrow Q \ circlearrowright$ , car un changement de direction crée des plis ( $$$\ curlywedge$ )

Dans notre circuit, le nœud $$$A$ se transformera en deux nœuds, $$$A \ circlearrowright$ et $$$A \ circlearrowleft$ il a un front de transition entrant $$$\ longrightarrow A \ circlearrowright$ et bord de transition sortant $$$A \ circlearrowleft \ longrightarrow$ . Si nous prenons la route $$$A \ circlearrowright$ devrait alors sortir par le nœud $$$\ circlearrowright$ qui sera soit un bord de transition $$$B \ circlearrowright \ longrightarrow$ (à travers le bord de l'enveloppe $$$A \ circlearrowright \ longrightarrow B \ circlearrowright$ ), ou bord de transition $$$D \ circlearrowright \ longrightarrow$ (à travers le bord de l'enveloppe $$$A \ circlearrowright \ longrightarrow D \ circlearrowright$ ) Nous ne pouvons pas sortir $$$C \ circlearrowleft \ longrightarrow$ , car le sens de rotation va changer de cette façon, et nous avons filtré l'enveloppe du bord $$$A \ circlearrowright \ longrightarrow C \ circlearrowleft$ .

En filtrant ces enveloppes pointues de bords du graphique, nous avons augmenté l'efficacité de l'algorithme.

Couper les bords qui se croisent

Des chemins partiels peuvent être coupés, dont les derniers bords de la transition coupent l'avant-dernier bord de la transition.

Obstacles polygonaux

Voir Game Programming Gems 2 , Chapter 3.10, Optimizing Points-of-Visibility Pathfinding, écrit par Thomas Young. Ce chapitre traite de l'écrêtage des nœuds, mais pas pour les cercles, mais pour les polygones.

Les références

• La tâche des ceintures
• Tâche de poulie
• Distance entre le point et la ligne
• Intersection de deux cercles