Wie berechne ich Pfade für Objekte mit begrenzter Beschleunigung?

Angenommen, ich habe ein Auto und ein Auto hat einen bestimmten Mindestwenderadius und ich möchte dieses Auto von Punkt a nach Punkt b fahren, aber das Auto zeigt nicht auf Punkt b. Wie berechne ich einen Pfad zu Punkt b? Die Ausrichtung am Punkt b angeben zu können, wäre ebenfalls gut (sagen wir, Sie möchten zu Ihrer Auffahrt fahren und dann in Ihre Garage einfahren - es nützt nicht viel, wenn Sie über Ihren Rasen zu Ihrer Auffahrt gelangen und sind seitwärts gerichtet :)

Ein Zeiger auf die Dokumentation (oder auch nur ein Name) wäre vollkommen in Ordnung - ich habe Probleme, überhaupt etwas zu finden.

Bei meinen Versuchen funktionieren sie in einfachen Fällen, scheitern jedoch kläglich in Situationen, in denen Punkt b näher an a liegt als der minimale Wenderadius.

Wie würden Sie beispielsweise einen ähnlichen Pfad bestimmen (den fett gedruckten Pfad):

Bearbeiten: In meinem eigentlichen Problem gibt es einige einfache Pfadbeschränkungen, aber ich habe bereits einen A * -Algorithmus, der funktioniert, aber es ermöglicht den Dingen, sofortige Kursänderungen vorzunehmen, so dass es albern aussieht, wenn ein Auto plötzlich eine 90 ° -Drehung macht auf einen Cent, wenn sie an einen Wendepunkt kommen.

Ich habe die vollständigen Gleichungen dafür noch nicht durchgearbeitet, aber hier sind einige Bilder, die uns helfen sollen, das Problem in den Griff zu bekommen. Es läuft auf eine gewisse Geometrie hinaus:

( Autosymbole über Kenney )

Von jedem Startpunkt und jeder Ausrichtung aus können wir zwei Kreise mit unserem minimalen Wenderadius zeichnen - einen links und einen rechts. Diese beschreiben die Punkte auf dem engstmöglichen Weg zu unserem Weg.

Wir können das Gleiche für jede gewünschte Endposition und Ausrichtung tun. Diese Kreise beschreiben das engstmögliche Ende unseres Weges.

Jetzt reduziert sich das Problem darauf, einen Pfad zu finden, der einen der Startkreise mit einem der Endkreise verbindet und jeden entlang seiner Tangente küsst.

(Dies setzt voraus, dass wir keine Hindernisse dazwischen finden müssen, was in der Frage nicht erwähnt wurde. Stormwinds Antwort bezieht sich darauf, wie wir Navigationsdiagramminformationen für diese Art von Problemen verwenden können. Sobald wir die Folge von Knoten haben Um durchzukommen, können wir die folgende Methode auf jedes Segment des Plans anwenden.)

Wenn wir der Einfachheit halber gerade Linien verwenden, erhalten wir ungefähr Folgendes:

Dies gibt uns den Grenzfall. Sobald Sie mit dieser Methode einen Pfad gefunden haben, können Sie einen oder beide Start- und Endkreise künstlich aufblasen, um einen weniger direkten, aber glatteren Pfad zu erhalten, bis zu dem Punkt, an dem sich die beiden Kreise küssen.

Berechnung dieser Pfade

Lassen Sie uns die Fälle für eine Drehrichtung herausarbeiten - sagen wir, wir beginnen unseren Weg mit einer Rechtskurve.

Das Zentrum unseres rechten Wendekreises ist:

startRightCenter = carStart.position + carStart.right * minRadius

Nennen wir den Winkel des geraden Abschnitts unseres Pfades (gemessen von der positiven x-Achse). pathAngle

Wenn wir einen Vektor von rightCenterdem Punkt zeichnen, an dem wir den Wendekreis verlassen (an diesem Punkt müssen wir pathAngle zugewandt sein), dann ist dieser Vektor ...

startOffset = minRadius * (-cos(pathAngle), sin(pathAngle))

Das heißt, der Punkt, an dem wir den Kreis verlassen, muss sein ...

departure = startRightCenter + startOffset

Der Punkt, an dem wir wieder in einen Wendekreis eintreten, hängt davon ab, ob wir mit einer Linkskurve oder einer Rechtskurve enden möchten:

// To end with a right turn:
reentry = endRightCenter + startOffset

// To end with a left turn: (crossover)
reentry = endLeftCenter - startOffset

Nun, wenn wir unseren Job richtig gemacht haben, verbindet die Linie departurezu reentrysoll , dass sie senkrecht startOffset:

dot(reentry - departure,  startOffset) = 0

Und das Lösen dieser Gleichung gibt uns die Winkel, unter denen dies wahr ist. (Ich verwende hier einen Plural, weil es technisch gesehen zwei solche Winkel gibt, aber einer davon beinhaltet das Rückwärtsfahren, was normalerweise nicht das ist, was wir wollen.)

Ersetzen wir als Beispiel den Fall von Rechtskurve zu Rechtskurve:

dot(endRightCenter + startOffset - startRightCenter - startOffset, startOffset) = 0
dot(endRightCenter - startRightCenter, startOffset) = 0
pathAngle = atan2(endRightCenter - startRightCenter)

Der Crossover-Fall ist komplizierter - es ist der, für den ich noch nicht die ganze Mathematik ausgearbeitet habe. Ich werde die Antwort vorerst ohne veröffentlichen, falls es für Sie nützlich ist, während ich die verbleibenden Details ausarbeite.

Bearbeiten: Ziel innerhalb des minimalen Wenderadius

Es stellt sich heraus, dass diese Methode oft sofort funktioniert, selbst wenn das Ziel näher als unser Mindestdrehabstand liegt. Zumindest ein Teil eines der Wiedereintrittskreise endet außerhalb des Abbiegeradius, sodass wir einen brauchbaren Weg finden können, solange es uns nichts ausmacht, dass es ein bisschen wie eine Brezel aussieht ...

Wenn uns der Weg, den wir so bekommen, nicht gefällt (oder wenn einer nicht machbar ist - ich habe nicht jeden Fall gründlich geprüft - vielleicht gibt es unmögliche), können wir immer geradeaus oder rückwärts fahren, bis wir einen geeigneten finden Kusskontakt zwischen einem Start- und einem Endkreis, wie oben dargestellt.

Dies hängt sehr stark vom Rest Ihres Datenmodells für die Navigation ab. Dh. Welche Daten haben Sie zur Hand, was können Sie einfach hinzufügen und wie verbrauchen Sie sie?

Nehmen Sie ein ähnliches Szenario aus einem Verkehrssystem auf dem Wasser und unter der Annahme, dass

• Sie befinden sich in einer Spielschleife
• Sie haben ein Knotenpfadsystem
• Ihre Autos verhalten sich wie autonome Objekte, die sich "von innen" mit eigener Kraft und Lenkung steuern
• Ihre Autos bewegen sich nicht wie auf Schienen

Sie könnten so etwas wie unten haben (verzeihen Sie mir das kindliche Aussehen der Bilder)

(Die roten Quadrate sind die Knoten, rote Linien sind Knotenverbindungen. Angenommen, Sie haben einen Pfadfindungslöser verwendet, mit dem die Knoten 1 bis 9 durchfahren werden können. Die Knoten 4 bis 9 sind auf dem Bild zu sehen, und Sie möchten die durch die grüne Linie angezeigten Knoten durchlaufen , zur Garage am Knoten Nr. 9; Sie möchten jedoch nicht genau an der grünen Linie fahren, sondern auf natürliche Weise auf der rechten Fahrspur bleiben und reibungslose Manöver durchführen).

Jeder Knoten hätte Metadaten, die beispielsweise einen Radius oder mehrere für verschiedene Zwecke enthalten. Einer von ihnen ist der blaue Kreis, der den Autos eine zielgerichtete Anleitung bietet .

In jedem Fall muss das Fahrzeug die nächsten beiden Knotenpunkte P (weiter) und P (weiter + 1) und ihre Positionen kennen. Natürlich hat das Auto auch eine Position. Ein Auto zielt auf die rechte Tangente des blauen Metadatenkreises von P (weiter). Autos fahren in die entgegengesetzte Richtung, damit sie nicht kollidieren. Wenn Sie auf die Tangente zielen, kann sich das Auto dem Kreis aus jeder Richtung nähern und sich immer rechts halten. Dies ist ein grobes Grundprinzip, das auf viele Arten verbessert werden kann.

P (next + 1) wird benötigt, um eine Entfernung zu bestimmen. Wenn das Auto P (next) erreicht oder sich in einem Radius seiner Metadaten befindet, kann es seinen Lenkwinkel anpassen, je nachdem, wie weit P (next + 1) entfernt ist. Dh. Wenn es nah ist, drehen Sie viel, wenn es weit weg ist, drehen Sie wenig. Anscheinend muss es auch andere Regeln und Randbedingungen geben, zum Beispiel die Berechnung eines Abstands zwischen dem Auto und einer Hilfslinie basierend auf den Tangenten auf der rechten Seite von P (weiter) und P (weiter + 1) und eine Korrektur durch diese - ein Wille, auf der gestrichelten (über dem Bild) und gepunkteten (unter dem Bild) Linie zu bleiben.

In jedem Fall vergisst das Auto, wenn es einen Knoten passiert , diesen und beginnt, die nächsten beiden zu betrachten .

Auf deine Frage. Anscheinend kann es beim Erreichen von Knoten 7 (im Bild oben, im Bild unten als Knoten 2 gesehen) nicht genug drehen .

Eine mögliche Lösung es einige Hilfslinien zu konstruieren und ein weiteren Treffer aller Zeiten zu halten , und hat dann das Auto zu bewegen , indem es die eigenen Physik - Einstellungen (Beschleunigung mit einer bestimmten Geschwindigkeit, Rückwärts langsamer, nehmen Knoten Metadaten SPEEDLIMITS berücksichtigt, Bremsen zu einem bestimmten oder berechneten G usw.). Wie gesagt, das Auto ist in diesem Szenario ein autonomes, selbstbeschreibendes, selbsttragendes Objekt.

Haben Sie die grünen Hilfslinien 1,2,3 . Wenn das Auto den Magentakreis erreicht , biegt es nach rechts ab. Zu diesem Zeitpunkt können Sie bereits berechnen, dass dies nicht erfolgreich sein wird (Sie kennen die maximale Drehrate und können die Kurve berechnen und sehen, dass beide Helplines 2 und 3 gekreuzt werden). Drehen Sie die Lenkung ganz nach rechts und lassen Sie sie vorwärts fahren (in Schritten der Physik) und verlangsamen Sie sie, wenn sie die Hilfslinie 3 erreicht (nähert sich - verwenden Sie Schwellenwerte, f (dist zur Helpline) usw.). Wenn es sich in der Hilfslinie 3 befindet, wechseln Sie in den Rückwärtsmodus und drehen Sie die Lenkung auf die entgegengesetzte Position . Lassen Sie es umkehren, bis es die Hilfslinie 4 erreicht(die Verbindungslinie zwischen Knoten 1 und 2 - Google für "Point at Side of Line-Algorithmus"). Wenn Sie es erreichen, verlangsamen Sie es, gehen Sie wieder in den Vorwärtsfahrmodus und drehen Sie das Rad. Wiederholen, bis die Straße frei ist - anscheinend war es diesmal mit 1 zusätzlichen Manöver ausreichend.

Dies ist die allgemeine Idee: Während der Spielschleife oder beim Überprüfen des Spiels Task Que System:

• Überprüfen Sie die Position, Geschwindigkeit, den Winkel usw. des Fahrzeugs anhand der aktuellen Kantengrenzen und des aktuellen Ziels .
• Wenn Sie noch nicht erreicht sind , fahren Sie mit Ihrer Arbeit fort (lassen Sie die Physik sie bewegen; das Auto hat eine Drehzahl und einen Gang). Fügen Sie eine neue Prüfung in Ihr Warteschlangensystem ein, die beispielsweise in 0,1 s erfolgt.
• Wenn erreicht , neue Bedingungen berechnen , Daten einstellen und beginnen . Fügen Sie in z. B. 0,1 s eine neue Prüfung in das Warteschlangensystem ein.
• Schließen Sie den Schleifenzyklus ab - fahren Sie fort und wiederholen Sie den Vorgang.

Indem den Knoten und den Autos ausreichende Daten gegeben werden, wird es Bewegung und Fortsetzung geben.

Bearbeiten: Und hinzufügen: Dies erfordert natürlich eine Feinabstimmung. Für Ihr Simulationsverhalten sind möglicherweise andere Hilfslinien, Metadaten, Kreise usw. erforderlich. Dies würde jedoch eine Vorstellung von einer möglichen Lösung geben.

Am Ende habe ich getan, was DMGregory vorgeschlagen hat, und es funktioniert gut. Hier ist ein relevanter Code (wenn auch nicht eigenständig), der zur Berechnung der beiden Tangentenstile verwendet werden kann. Ich bin mir sicher, dass dieser Code nicht effizient ist und wahrscheinlich nicht in allen Situationen korrekt ist, aber er funktioniert bisher für mich:

bool Circle::outer_tangent_to(const Circle & c2, LineSegment & shared_tangent) const {
    if (this->direction != c2.direction) {
        return false;
    }
    if (this->radius != c2.radius) {
        // how to add it: http://mathworld.wolfram.com/Circle-CircleTangents.html
        // just subtract smaller circle radius from larger circle radius and find path to center
        //  then add back in the rest of the larger circle radius
        throw ApbException("circles with different length radius not supported");
    }

    auto vector_to_c2 = c2.center - this->center;
    glm::vec2 normal_to_c2;
    if (this->direction == Circle::CW) {
        normal_to_c2 = glm::normalize(glm::vec2(-vector_to_c2.y, vector_to_c2.x));
    } else {
        normal_to_c2 = glm::normalize(glm::vec2(vector_to_c2.y, -vector_to_c2.x));
    }

    shared_tangent = LineSegment(this->center + (normal_to_c2 * this->radius),
                                 c2.center + (normal_to_c2 * this->radius));
    return true;
}


bool Circle::inner_tangent_to(const Circle & c2, LineSegment & tangent) const {

    if (this->radius != c2.radius) {
        // http://mathworld.wolfram.com/Circle-CircleTangents.html
        // adding this is non-trivial
        throw ApbException("inner_tangents doesn't support circles with different radiuses");
    }

    if (this->direction == c2.direction) {
        // inner tangents require opposing direction circles
        return false;
    }

    auto vector_to_c2 = c2.center - this->center;
    auto distance_between_circles = glm::length(vector_to_c2);

    if ( distance_between_circles < 2 * this->radius) {
//      throw ApbException("Circles are too close and don't have inner tangents");
        return false;
    } else {
        auto normalized_to_c2 = glm::normalize(vector_to_c2);
        auto distance_to_midpoint = glm::length(vector_to_c2) / 2;
        auto midpoint = this->center + (vector_to_c2 / 2.0f);

        // if hypotenuse is oo then cos_angle = 0 and angle = 90˚
        // if hypotenuse is radius then cos_angle = r/r = 1 and angle = 0
        auto cos_angle = radius / distance_to_midpoint;
        auto angle = acosf(cos_angle);

        // now find the angle between the circles
        auto midpoint_angle = glm::orientedAngle(glm::vec2(1, 0), normalized_to_c2);

        glm::vec2 p1;
        if (this->direction == Circle::CW) {
            p1 = this->center + (glm::vec2{cos(midpoint_angle + angle), sin(midpoint_angle + angle)} * this->radius);
        } else {
            p1 = this->center + (glm::vec2{cos(midpoint_angle - angle), sin(midpoint_angle - angle)} * this->radius);
        }

        auto tangent_to_midpoint = midpoint - p1;
        auto p2 = p1 + (2.0f * tangent_to_midpoint);
        tangent = {p1, p2};

        return true;
    }
};

Hier sind zwei Filme des obigen Codes in Aktion:

Hier ist ein "äußerer" Pfad: http://youtube.com/watch?v=99e5Wm8OKb0 und hier ist ein "Kreuzungspfad": http://youtube.com/watch?v=iEMt8mBheZU

Wenn dieser Code hilft, Sie aber Fragen zu einigen der Teile haben, die hier nicht gezeigt werden, schreiben Sie einfach einen Kommentar und ich sollte ihn in ein oder zwei Tagen sehen.