Einen Weg zwischen runden Hindernissen finden

Waldnavigation

Ein * Path Finder-Algorithmus ist ein leistungsstarkes Tool zum schnellen Generieren optimaler Pfade. Normalerweise wird A * beim Navigieren von Karten aus Gittern angezeigt, es kann jedoch nicht nur für Gitter verwendet werden! Es kann mit beliebigen Diagrammen arbeiten. Mit A * können Sie sich in der Welt der runden Hindernisse zurechtfinden.


Im Originalartikel sind alle Bilder interaktiv.

Wie löst ein Algorithmus diese beiden Probleme? Beginnen wir mit einer kurzen Beschreibung der Funktionsweise von A *.

Algorithmus A *

Algorithmus A * findet den optimalen Weg vom Start bis zum Endpunkt und vermeidet dabei Hindernisse. Er erkennt dies und erweitert allmählich viele Teilpfade . Jeder Teilpfad besteht aus einer Reihe von Schritten vom Startpunkt zu einem Zwischenpunkt auf dem Weg zum Ziel. Während der Arbeit mit A * nähern sich Teilpfade dem Endpunkt. Der Algorithmus funktioniert nicht mehr, wenn er den vollständigen Pfad gefunden hat, der besser ist als die übrigen Optionen, und dies kann bewiesen werden.

Bei jedem Schritt des Algorithmus wertet A * die Menge der Teilpfade aus und generiert neue Pfade, wodurch der vielversprechendste Pfad aus der Menge erweitert wird. Zu diesem Zweck speichert A * Teilpfade in einer Prioritätswarteschlange, sortiert nach ungefährer Länge - der tatsächlich gemessenen Pfadlänge plus der ungefähren verbleibenden Entfernung zum Ziel. Diese Annäherung sollte unterschätzt werden ; Das heißt, die Annäherung kann kleiner als der wahre Abstand sein, aber nicht größer als dieser. Bei den meisten Aufgaben zur Pfadfindung ist eine gute, unterschätzte Schätzung der geometrische Abstand in einer geraden Linie vom Ende des Teilpfads bis zum Endpunkt. Der wirklich beste Weg zum Ziel vom Ende des Teilweges kann länger als dieser geradlinige Abstand sein, aber nicht kürzer.

Wenn A * startet, enthält die Prioritätswarteschlange nur einen Teilpfad: den Startpunkt. Der Algorithmus entfernt wiederholt den vielversprechendsten Pfad aus der Prioritätswarteschlange, dh den Pfad mit der kleinsten ungefähren Länge. Wenn dieser Pfad am Endpunkt endet, hat der Algorithmus die Aufgabe abgeschlossen. Die Prioritätswarteschlange stellt sicher, dass kein anderer Pfad besser sein kann. Andernfalls generiert A * ab dem Ende des Teilpfads, den er aus der Warteschlange entfernt hat, mehrere neue Pfade, wobei Einheitsschritte in alle möglichen Richtungen ausgeführt werden. Er stellt diese neuen Pfade wieder in die Prioritätswarteschlange und beginnt den Prozess erneut.

Zählen

A * arbeitet mit einem Diagramm : einer Reihe von Knoten, die durch Kanten verbunden sind . In einer gitterbasierten Welt bezeichnet jeder Knoten eine separate Netzzelle, und jede Kante ist eine Verbindung zu benachbarten Zellen im Norden, Süden, Osten oder Westen.

Bevor wir A * für den Wald von runden Hindernissen aus ausführen können, müssen wir es in ein Diagramm konvertieren. Alle Wege durch den Wald bestehen aus abwechselnden Segmenten von Linien und Bögen. Sie sind die Kanten des Pfadgraphen. Die Endpunkte dieser Kanten werden zu Knoten.

Ein Pfad durch ein Diagramm besteht aus einer Reihe von Knoten, die durch Kanten verbunden sind:


Sowohl Segmente als auch Bögen sind Kanten des Diagramms. Wir werden die Segmente als Übergangskanten bezeichnen , da der Pfad sie verwendet, um sich zwischen Hindernissen zu bewegen. Wir nennen Bögen die umhüllenden Kanten , weil ihre Aufgabe auf dem Weg darin besteht, die Seiten der Hindernisse zu umgehen.

Als nächstes werden wir einen einfachen Weg untersuchen, um einen Wald mit Hindernissen in ein Diagramm umzuwandeln: Wir werden alle möglichen Übergangskanten und Hüllkurven der Kanten erzeugen.

Übergangskantengenerierung

Die Kanten des Übergangs zwischen zwei Kreisen sind Liniensegmente, die beide Kreise kaum berühren. Solche Segmente werden als Tangenten an zwei Punkte bezeichnet , und für jedes Kreispaar gibt es vier solcher Tangenten. Tangenten an zwei Punkte, die sich zwischen den Kreisen schneiden, werden als interne Tangenten an zwei Punkte bezeichnet , und diejenigen, die nach außen verlaufen, werden als externe bezeichnet .

Innere Tangenten an zwei Punkte

In der Vergangenheit war die Suche nach internen Tangenten wichtig für die Berechnung der Länge des Riemens, der zwei Riemenscheiben unterschiedlicher Größe verbindet. Die Aufgabe, interne Tangenten an zwei Punkten zu erzeugen, wird daher als Riemenproblem bezeichnet . Um die internen Tangenten an zwei Punkte zu ermitteln, müssen Sie den Winkel berechnen $$$\ theta$ in der Zeichnung unten.


Wie sich herausstellte, für Kreise mit Zentren $$$A$ und $$$B$ und Radien $$$r_A$ und $$$r_B$ deren Zentren sind in einiger Entfernung $$$d$ ::

$$

$$\ theta = \ arccos {{r_A + r_B} \ über {d}}$$

Definieren $$$\ theta$ wir können die Punkte leicht finden $$$C$ , $$$D$ , $$$E$ und $$$F$ .

Externe Tangenten an zwei Punkte

Bei der Konstruktion externer Tangenten (dies ist die Aufgabe von Riemenscheiben ) wird eine ähnliche Technik verwendet.


Für äußere Tangenten können wir finden $$$\ theta$ wie folgt:

$$

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

Es spielt keine Rolle, welcher der Kreise größer ist, A oder B, aber wie Sie auf dem Bild sehen können, $$$\ theta$ auf Seite A gelegt, die B am nächsten liegt, aber auf Seite B, die am weitesten von A entfernt ist.

Sichtlinie

Zusammen bilden die inneren und äußeren Tangenten an zwei Punkte zwischen den beiden Kreisen die Kanten des Übergangs zwischen den Kreisen. Was aber, wenn eine oder mehrere Übergangskanten den dritten Kreis schließen?


Wenn die Übergangskante von einem anderen Kreis überlappt wird, müssen wir diese Kante verwerfen. Um einen solchen Fall zu erkennen, verwenden wir eine einfache Berechnung des Abstands zwischen einem Punkt und einer Linie . Wenn der Abstand von der Übergangskante zur Mitte des Hindernisses kleiner als der Radius des Hindernisses ist, überlappt das Hindernis die Übergangskante, sodass wir es verwerfen müssen.

Berechnung der Entfernung von einem Punkt $$$C$ zu einem geraden Liniensegment $$$\ overline {AB}$ Wir werden die folgende Methode verwenden :

Zuerst berechnen wir $$$u$ - Teil der Entfernung entlang des Segments $$$\ overline {AB}$ wo die Senkrechte den Punkt schneidet $$$C$ ::

$$

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

Dann berechnen wir die Position $$$E$ auf $$$\ overline {AB}$ ::

$$

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

Entfernung $$$d$ von $$$C$ zu schneiden $$$\ overline {AB}$ Ist die Entfernung von $$$C$ vorher $$$E$ ::

$$

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

Als $$$d <r$ Der Kreis überlappt die Sichtlinie von $$$A$ in $$$B$ und die Kante muss verworfen werden. Wenn $$$d \ ge r$ dann die Sichtlinie von $$$A$ in $$$B$ existiert und die Rippe sollte verlassen werden.

Edge Envelope Generation

Die Knoten des Diagramms verbinden die Übergangskante mit der Hüllkurvenkante. In den vorherigen Abschnitten haben wir Übergangskanten generiert. Um die Hüllkurven der Kanten zu erzeugen, beginnen wir am Endpunkt der Übergangskante, gehen um den Kreis herum und enden am Endpunkt einer anderen Übergangskante.


Um die Menge der Hüllkurven der Kanten eines Kreises zu finden, finden wir zuerst alle, die den Kreis der Übergangskanten tangieren. Erstellen Sie dann die Hüllkurven der Kanten zwischen allen Endpunkten der Übergangskanten auf dem Kreis.

Alles zusammenfügen

Nachdem wir Übergangskanten, Hüllkurven von Kanten und Knoten generiert und dann alle überlappenden Übergangskanten verworfen haben, können wir ein Diagramm erstellen und mit dem A * -Algorithmus nach dem Pfad suchen.

Verbesserungen

Das von uns untersuchte Verfahren zur Erzeugung von Graphen funktioniert gut genug, um den Algorithmus zu erklären, kann jedoch in vielerlei Hinsicht verbessert werden. Solche Verbesserungen ermöglichen es dem Algorithmus, weniger CPU- und Speicherressourcen zu verbrauchen und mehr Situationen zu bewältigen. Schauen wir uns einige Situationen an.

Hindernisse, die sich gegenseitig betreffen

Möglicherweise haben Sie bemerkt, dass sich in den oben gezeigten Beispielen runde Hindernisse nicht überlappten und sich nicht einmal berührten. Unter der Annahme, dass sich die Kreise berühren können, erschwert dies die Suche nach dem Pfad

Zwei-Punkt-Tangenten

Denken Sie daran, dass Tangenten an zwei Punkte mithilfe dieser Formel für interne Tangenten gefunden werden können:

$$

$$\ theta = \ arccos {{r_A + r_B} \ über {d}}$$

und Formeln für externe Tangenten:

$$

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

Wenn sich zwei Kreise berühren oder schneiden, gibt es keine internen Tangenten zwischen ihnen. In diesem Fall $$${r_A + r_B} \ über d$ mehr als eine. Da der Wert des Arccosins außerhalb des Definitionsbereichs liegt $$$[- 1, 1]$ nicht definiert, ist es wichtig, den Schnittpunkt der Kreise zu überprüfen, bevor das Arccosin gefunden wird.

Wenn sich ein Kreis vollständig in einem anderen befindet, gibt es keine externen Tangenten zwischen ihnen. In diesem Fall $$${r_A - r_B} \ über d$ außerhalb der Reichweite $$$[- 1, 1]$ Das heißt, es hat kein Arccosin.

Sichtbarkeit der Übergangskante

Wenn wir die Möglichkeit zulassen, Hindernisse zu berühren oder zu überqueren, ergeben sich neue Fälle bei der Berechnung der Sichtlinie der Übergangskanten.

Erinnern Sie sich an die Berechnung $$$u$ - Teil des Abstands entlang der Kante des Übergangs, in dem die Senkrechte zum Punkt die Kante berührt. Wenn das Berühren der Kreise nicht zulässig ist, wird der Wert angezeigt $$$u$ außerhalb der Reichweite $$$[0,1]$ Das heißt, der Kreis kann die Kante nicht berühren, da er dazu einen der Endpunkte der Kante berühren müsste. Dies ist nicht möglich, da die Endpunkte einer Kante bereits andere Kreise berühren.

Wenn wir jedoch die Möglichkeit von überlappenden Kreisen zulassen, dann die Werte $$$u$ außerhalb der Reichweite $$$[0,1]$ kann die Sichtlinie entlang der Kante überlappen. Dies entspricht Fällen, in denen sich der Kreis hinter dem Ende der Übergangskante befindet, den Endpunkt jedoch überlappt oder berührt. Um solche Fälle mathematisch zu verfolgen, werden wir begrenzen $$$u$ Intervall $$$[0,1]$ ::

$$

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

Umschlag Sichtlinie

Wenn sich Hindernisse berühren oder schneiden können, können die Hüllkurven der Kanten auf die gleiche Weise wie die Übergangskanten durch Hindernisse blockiert werden. Betrachten Sie die Umschlagkante aus der folgenden Abbildung. Wenn die Hülle der Rippe ein anderes Hindernis berührt, ist die Rippe blockiert und muss weggeworfen werden.


Um festzustellen, ob die Hüllkurve der Kante durch ein anderes Hindernis blockiert ist, verwenden wir die folgende Methode , um die Punkte zu bestimmen, an denen sich zwei Kreise schneiden. Wenn Kreise Zentren an Punkten haben $$$A$ und $$$B$ und Radien $$$r_A$ und $$$r_B$ wo $$$d$ - Abstand zwischen $$$A$ und $$$B$ Für den Anfang müssen wir mehrere Fälle überprüfen. Wenn sich die Kreise nicht berühren (d. H. $$$d> r_A + r_B$ ),
sind eins in dem anderen ( $$$d <| r_A - r_B |$ ) oder match ( $$$d = 0$ und $$$r_A = r_B$ ), dann können Kreise die Umschläge des anderen nicht beeinflussen.

Wenn eine dieser Bedingungen nicht erfüllt ist, schneiden sich die Kreise an zwei Punkten. Wenn sich die Kreise berühren, fallen diese beiden Punkte zusammen. Betrachten Sie die Radikalachse, die die Schnittpunkte verbindet. es ist senkrecht zur Verbindungslinie $$$A$ und $$$B$ irgendwann $$$C$ . Wir können die Entfernung berechnen $$$a$ von $$$A$ vorher $$$C$ wie folgt:

$$

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

Finden $$$a$ wir können den Winkel finden $$$\ theta$ ::

$$

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

Wenn $$$\ theta$ ist Null, dann berühren sich die Kreise bei $$$C$ . Ansonsten gibt es zwei Schnittpunkte, die positiv und negativ entsprechen $$$\ theta$ .


Als nächstes bestimmen wir, ob einer der Schnittpunkte zwischen dem Start- und dem Endpunkt der Hüllkurve der Kante liegt. Wenn ja, dann blockiert das Hindernis die Hüllkurvenkante, und wir müssen diese Kante verwerfen. Beachten Sie, dass wir den Fall nicht berücksichtigen müssen, wenn sich die Hüllkurve der Kante vollständig innerhalb des Hindernisses befindet, da das Abschneiden entlang der Sichtlinie für die Übergangskanten diese Kante bereits verworfen hat.

Nach Änderungen an der Berechnung der Tangenten an zwei Punkten und der Sichtlinie für die Übergangskanten und die Hüllkurven der Kanten funktioniert alles korrekt.

Variabler Akteurradius und Minkowski-Erweiterung

Bei der Berechnung der Navigation eines runden Objekts in der Welt der kreisförmigen Hindernisse können Beobachtungen berücksichtigt werden, die die Lösung des Problems vereinfachen. Erstens kann man die Arbeit vereinfachen, indem man feststellt, dass die Bewegung eines Kreises mit dem Radius r durch den Wald der Bewegung eines Punktes durch denselben Wald mit einer einzigen Änderung ähnlich ist: Der Radius jedes Hindernisses nimmt um r zu . Dies ist ein äußerst einfacher Fall für die Anwendung der Minkowski-Summe . Wenn der Radius des Akteurs größer als Null ist, vergrößern wir vor dem Start einfach die Hindernisse.

Aufgeschobene Kantengenerierung

Im Allgemeinen ein Diagramm für einen Wald aus $$$n$ Hindernisse enthält $$$O (n ^ 2)$ Übergangskanten, aber da jeder von ihnen auf Sichtlinie mit überprüft werden muss $$$n$ Hindernisse, dann ist die gesamte Graphgenerierungszeit $$$O (n ^ 3)$ . Darüber hinaus können Paare von Übergangskanten zur Bildung von Hüllkurven führen, und jede von ihnen muss mit jedem Hindernis auf die Sichtlinie überprüft werden. Aufgrund der hohen Effizienz des A * -Algorithmus wird jedoch normalerweise nur ein Teil dieses großen Diagramms betrachtet, um den optimalen Pfad zu erstellen.

Wir können Zeit sparen, indem wir während der Ausführung des A * -Algorithmus kleine Teile des Diagramms im laufenden Betrieb generieren, anstatt die gesamte Arbeit im Voraus zu erledigen. Wenn A * den Pfad schnell findet, wird nur ein kleiner Teil des Diagramms generiert. Dazu verschieben wir die Kantengenerierung in die Funktion neighbors() .

Es gibt mehrere Fälle. Zu Beginn des Algorithmus benötigen wir Nachbarn des Startpunkts. Dies sind die Kanten des Übergangs vom Startpunkt zur linken und rechten Kante jedes Hindernisses.

Der nächste Fall ist, wenn A * gerade auf den Punkt gekommen ist $$$p$ am Rande eines Hindernisses $$$C$ entlang der Übergangskante: neighbors() sollten die Hüllkurven der Kanten zurückgeben, von denen $$$p$ . Dazu bestimmen wir, welche Übergangskanten aus dem Hindernis herausgehen, indem wir die Tangenten an zwei Punkten dazwischen berechnen $$$C$ und alle anderen Hindernisse, die alle wegwerfen, die nicht in Sichtweite sind. Dann finden wir alle Umschläge der Kanten, die sich verbinden $$$p$ Mit diesen Übergangskanten lassen Sie diejenigen fallen, die durch andere Hindernisse blockiert sind. Wir geben alle diese Hüllkurven der Kanten zurück und speichern die Übergangskanten für die Rückgabe bei einem nachfolgenden Aufruf an neighbors() .

Der letzte Fall ist, wenn A * entlang des Hindernisses um die Umschlagkante herumging $$$C$ und er muss gehen $$$C$ entlang der Kante des Übergangs. Da im vorherigen Schritt alle Übergangskanten berechnet und gespeichert wurden, können Sie einfach den richtigen Satz von Kanten finden und zurückgeben.

Wir schneiden die spitzen Umschläge der Rippen ab

Umschlagrippen verbinden Übergangskanten, die einen Kreis berühren. Es stellt sich jedoch heraus, dass viele dieser Umschlagrippen nicht für eine optimale Verwendung geeignet sind. Wir können den Algorithmus beschleunigen, indem wir sie eliminieren.

Der optimale Weg durch den Wald der Hindernisse besteht immer aus abwechselnden Übergangskanten und Kantenhüllen. Angenommen, wir geben einen Knoten ein $$$A$ und entscheiden, wie man da rauskommt:


Melden Sie sich an $$$A$ bedeutet, wir bewegen uns im Uhrzeigersinn ( $$$\ circlearrowright$ ) Wir müssen durch den Knoten austreten, damit wir uns weiter im Uhrzeigersinn bewegen können ( $$$\ circlearrowright$ ), das heißt, wir können nur durch den Knoten beenden $$$B$ oder $$$D$ . Wenn Sie durch verlassen $$$C$ dann eine Beugung ( $$$\ curlywedge$ ) Wege, die niemals optimal sein werden. Wir müssen solche spitzen Kanten herausfiltern.

Beachten Sie zunächst, dass A * ohnehin jede nicht orientierte Kante verarbeitet. $$$P \ longleftrightarrow Q$ wie zwei orientierte Kanten $$$P \ longrightarrow Q$ und $$$Q \ longrightarrow P$ . Wir können dies nutzen, indem wir die Kanten und Knoten mit Orientierung markieren.

1. Knoten $$$P$ werden Knoten mit Orientierung - im Uhrzeigersinn ( $$$P \ circlearrowright$ ) oder gegen den Uhrzeigersinn ( $$$P \ circlearrowleft$ ) Pfeile.
2. Unorientierte Übergangskanten $$$P \ longleftrightarrow Q$ werden orientierte Kanten $$$P, p \ longrightarrow Q, \ hat {q}$ und $$$Q, q \ longrightarrow P, \ hat {p}$ wo $$$p$ und $$$q$ Sind Orientierungen und $$$\ hat {x}$ bedeutet die entgegengesetzte Richtung $$$x$ .
3. Unorientierte Rippenumschläge $$$P \ longleftrightarrow Q$ werden orientierte Kanten $$$P \ circlearrowright \ longrightarrow Q \ circlearrowright$ und $$$P \ circlearrowleft \ longrightarrow Q \ circlearrowleft$ . Hier erfolgt die Filterung: Wir aktivieren nicht $$$P \ circlearrowright \ longrightarrow Q \ circlearrowleft$ und $$$P \ circlearrowleft \ longrightarrow Q \ circlearrowright$ , weil eine Richtungsänderung Knicke erzeugt ( $$$\ curlywedge$ )

In unserer Schaltung der Knoten $$$A$ wird in zwei Knoten verwandeln, $$$A \ circlearrowright$ und $$$A \ circlearrowleft$ es hat eine eingehende Übergangskante $$$\ longrightarrow A \ circlearrowright$ und ausgehende Übergangskante $$$A \ circlearrowleft \ longrightarrow$ . Wenn wir auf die Straße gehen $$$A \ circlearrowright$ dann sollte durch den Knoten verlassen $$$\ circlearrowright$ Das wird entweder eine Übergangskante sein $$$B \ circlearrowright \ longrightarrow$ (durch die Umschlagkante $$$A \ circlearrowright \ longrightarrow B \ circlearrowright$ ) oder Übergangskante $$$D \ circlearrowright \ longrightarrow$ (durch die Umschlagkante $$$A \ circlearrowright \ longrightarrow D \ circlearrowright$ ) Wir können nicht durchkommen $$$C \ circlearrowleft \ longrightarrow$ , weil sich die Drehrichtung auf diese Weise ändert und wir die Hüllkurve der Kante gefiltert haben $$$A \ circlearrowright \ longrightarrow C \ circlearrowleft$ .

Durch Herausfiltern dieser spitzen Kantenhüllkurven aus dem Diagramm haben wir die Effizienz des Algorithmus erhöht.

Schnittkanten abschneiden

Teilpfade können abgeschnitten werden, deren letzte Kanten des Übergangs die vorletzte Kante des Übergangs schneiden.

Polygonale Hindernisse

Siehe Game Programming Gems 2 , Kapitel 3.10, Optimieren der Sichtbarkeitspfad-Pfadfindung, geschrieben von Thomas Young. In diesem Kapitel werden Beschneidungsknoten erläutert, jedoch nicht für Kreise, sondern für Polygone.

Referenzen

• Die Aufgabe der Gürtel
• Riemenscheibenaufgabe
• Abstand zwischen Punkt und Linie
• Schnittpunkt zweier Kreise