Jak obliczyć ścieżki dla obiektów o ograniczonym przyspieszeniu?

Powiedzmy na przykład, że mam samochód, a samochód ma określony minimalny promień skrętu i chcę jeździć tym samochodem od punktu a do punktu b, ale samochód nie jest skierowany do punktu b. Jak obliczyć ścieżkę do punktu b? Określenie orientacji w punkcie b również byłoby dobre (powiedz, że chcesz jechać na podjazd, a następnie wjechać do garażu - nie przyniesie to wiele dobrego, jeśli dojdziesz do podjazdu, przejeżdżając przez trawnik i są skierowane bokiem :)

Wskaźnik do dokumentacji (a nawet tylko nazwa) byłby całkowicie w porządku - nie mogę nic znaleźć.

W moich próbach działają one w prostych przypadkach, ale zawodzą niefortunnie w sytuacjach, takich jak gdy punkt b jest bliższy niż minimalny promień skrętu.

Na przykład, jak określisz ścieżkę podobną do tej (pogrubiona ścieżka):

edytuj: W moim rzeczywistym problemie istnieją pewne proste ograniczenia ścieżki, ale już mam algorytm A *, który działa, ale pozwala on na natychmiastowe zmiany kursu, więc wygląda to głupio, gdy samochód nagle skręca o 90˚ za dziesięciocentówkę, kiedy dotrą do punktu zwrotnego.

Nie opracowałem do tej pory pełnych równań, ale oto kilka elementów wizualnych, które pomogą nam rozwiązać problem. Sprowadza się do pewnej geometrii:

( Ikony samochodów przez Kenney )

Z dowolnego punktu początkowego i orientacji możemy narysować dwa okręgi z naszym minimalnym promieniem skrętu - jeden po lewej, drugi po prawej. Opisują one punkty na jak najściślejszym początku naszej ścieżki.

Możemy zrobić to samo dla dowolnej żądanej pozycji końcowej i orientacji. Kręgi te opisują najściślejszy możliwy koniec naszej ścieżki.

Teraz problem sprowadza się do znalezienia ścieżki, która łączy jedno z początkowych kół z jednym z końcowych kół, całując je wzdłuż stycznej.

(Zakłada się, że nie musimy szukać ścieżki pomiędzy przeszkodami pomiędzy nimi, o czym nie wspomniano w pytaniu. Odpowiedź Stormwind dotyczy sposobu wykorzystania informacji z wykresu nawigacyjnego dla tego rodzaju problemów. Po uzyskaniu sekwencji węzłów aby przejść, możemy zastosować poniższą metodę do każdego segmentu planu).

Jeśli dla uproszczenia używamy linii prostych, otrzymujemy coś takiego:

To nas ogranicza. Po znalezieniu ścieżki tą metodą możesz sztucznie napompować jedno lub oba koła początkowe i końcowe, aby uzyskać mniej bezpośrednią, ale gładszą ścieżkę, aż do momentu, w którym oba kręgi się pocałują.

Obliczanie tych ścieżek

Przeanalizujmy przypadki dla jednego kierunku skrętu - powiedzmy, że zaczynamy naszą drogę od skrętu w prawo.

Środek naszego prawego promienia skrętu to:

startRightCenter = carStart.position + carStart.right * minRadius

Nazwijmy kąt prostego odcinka naszej ścieżki (mierzony od dodatniej osi x) pathAngle

Jeśli narysujemy wektor od rightCenterpunktu, w którym opuszczamy okrąg zawracający (w tym momencie musimy być skierowani w stronę pathAngle), to ten wektor jest ...

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

Oznacza to, że punktem wyjścia z kręgu musi być ...

departure = startRightCenter + startOffset

Punkt, w którym ponownie wkraczamy w okrąg skrętu, zależy od tego, czy zamierzamy zakończyć zakręt w lewo, czy w prawo:

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

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

Teraz, jeśli dobrze wykonaliśmy naszą pracę, linia łącząca departurez reentrypowinna być prostopadła do startOffset:

dot(reentry - departure,  startOffset) = 0

A rozwiązanie tego równania da nam kąt (kąty), pod jakim to jest prawdziwe. (Używam liczby mnogiej, ponieważ technicznie istnieją dwa takie kąty, ale jeden z nich obejmuje jazdę do tyłu, co zwykle nie jest tym, czego chcemy)

Jako przykład zamieńmy skręt w prawo na literę skrętu w prawo:

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

Przypadek crossovera jest bardziej skomplikowany - to ten, na który jeszcze nie wypracowałem całej matematyki. Na razie opublikuję odpowiedź bez odpowiedzi, na wypadek, gdyby była dla Ciebie przydatna podczas opracowywania pozostałych szczegółów.

Edycja: Miejsce docelowe w minimalnym promieniu skrętu

Okazuje się, że ta metoda często działa natychmiast po wyjęciu z pudełka, nawet gdy miejsce docelowe jest bliżej niż nasza minimalna odległość skrętu. Przynajmniej część jednego z kręgów powrotnych kończy się poza promieniem skrętu, co pozwala nam znaleźć realną ścieżkę, o ile nie przeszkadza nam, że robi się trochę w stylu precla ...

Jeśli nie podoba nam się ścieżka, którą dostajemy w ten sposób (lub jeśli nie jest to wykonalne - nie sprawdziłem dokładnie wszystkich przypadków - być może są niemożliwe), zawsze możemy jechać prosto do przodu lub do tyłu, dopóki nie znajdziemy odpowiedniego całowanie kontaktu między kołem początkowym i końcowym, jak pokazano na schemacie powyżej.

To bardzo zależy od reszty modelu danych do nawigacji. To znaczy. jakie dane masz pod ręką, co możesz łatwo dodać i jak je wykorzystać.

Biorąc podobny scenariusz z systemu ruchu na wodzie i przy założeniu, że

• jesteś w pętli gry
• masz system ścieżki do węzła
• twoje samochody zachowują się jak autonomiczne obiekty, które kontrolują się „od wewnątrz”, wykorzystując własną siłę i sterowanie
• twoje samochody nie poruszają się jak po szynach

możesz mieć coś takiego poniżej (wybacz mi dziecinny wygląd zdjęć)

(Czerwone kwadraty są węzłami, czerwone linie są połączeniami węzłów. Załóżmy, że użyłeś solwera identyfikującego ścieżki, który dał węzłom 1-9 przejazd; węzły 4-9 widoczne na obrazie i chcesz przejść przez węzły wskazane zieloną linią , do garażu w węźle nr 9; jednak nie chcesz jechać dokładnie zieloną linią, zamiast tego pozostań naturalnie na prawym bocznym pasie i rób płynne manewry).

Każdy węzeł miałby metadane, które przechowują na przykład promień lub wiele, dla różnych celów. Jednym z nich jest niebieskie kółko, które zapewnia wskazówki dotyczące celowania samochodów .

Za każdym razem pojazd musi znać następne dwa punkty węzłowe P (następny) i P (następny + 1) oraz ich pozycje. Oczywiście samochód ma również pozycję. Samochód ma na celu styczną po prawej stronie niebieskiego okręgu metadanych P (dalej). Podobnie samochody jadące w przeciwnym kierunku, dlatego nie zderzą się. Celowanie w styczną oznacza, że ​​samochód może zbliżyć się do koła z dowolnego kierunku i zawsze trzymać się prawej strony. Jest to z grubsza podstawowa zasada, którą można poprawić na wiele sposobów.

P (następne + 1) jest potrzebne do określenia odległości - gdy samochód osiągnie P (następny) lub znajdzie się w promieniu metadanych, może dostosować kąt skrętu w zależności od odległości P (następne + 1). To znaczy. jeśli jest blisko, obróć dużo, jeśli jest daleko, obróć mało. Najwyraźniej muszą istnieć również inne reguły i warunki na krawędzi, na przykład obliczenie odległości między samochodem a linią pomocniczą na podstawie stycznych prawej strony P (dalej) i P (dalej + 1), i przez to korekta - wola pozostania na linii przerywanej (powyżej rys.) i kropkowanej (poniżej rys.).

W każdym razie, gdy samochód mija jeden węzeł , zapomina o nim i zaczyna patrzeć na kolejne dwa .

Na twoje pytanie Najwyraźniej po dotarciu do węzła 7 (na zdjęciu powyżej, widzianego jako węzeł 2 na poniższym obrazku), nie może się wystarczająco obrócić .

Jednym z możliwych rozwiązań jest zbudowanie niektórych linii pomocy i utrzymanie celu przez cały czas , a następnie pozwolić samochodowi poruszać się według jego własnych ustawień fizycznych (przyspieszać z określoną prędkością, cofać się wolniej, brać pod uwagę ograniczenia prędkości metadanych węzła, hamować przy danym lub obliczonym G itp.). Jak powiedziano, samochód jest w tym scenariuszu autonomicznym, samoopisującym się, samonośnym przedmiotem.

Miej zielone linie pomocy 1,2,3 . Gdy samochód dociera do magenta kręgu , zaczyna skręcać w prawo. W tym momencie możesz już obliczyć, że się nie powiedzie (znasz maksymalną prędkość skrętu i możesz obliczyć krzywą, i zobaczysz, że przecina ona obie linie pomocy 2 i 3). Skręć całkowicie w prawo i pozwól mu jechać do przodu (przyrosty fizyki) i zwolnij, gdy dojdzie do linii pomocy 3 (zbliża się do progów użycia, f (dystans do linii pomocy) itp.). Gdy znajdzie się na linii pomocy 3, przejdź do trybu cofania , przekręć kierownicę do pozycji całkowicie przeciwnej . Odwróć, aż dojdzie do linii pomocy 4(linia połączenia między węzłem 1 a 2 - google dla „algorytmu punktu z boku linii”). Zwolnij, gdy się do niego zbliży, przejdź ponownie do trybu jazdy do przodu , obróć koło. Powtarzaj, aż droga będzie wolna - najwyraźniej tym razem wystarczyło 1 dodatkowego manewru.

Jest to ogólny pomysł: podczas pętli gry lub podczas sprawdzania systemu kolejki zadań gry:

• Sprawdź pozycję samochodu, prędkość, kąt itp. W stosunku do aktualnych limitów krawędzi i celu ,
• Jeśli jeszcze tego nie osiągnąłeś , kontynuuj to, co robiłeś (pozwól, aby fizyka go przesunęła; samochód ma obroty i bieg). Wstaw nowy czek w swoim systemie kolejkowym, na przykład za 0,1 s.
• Po osiągnięciu oblicz nowe warunki, ustaw dane i rozpocznij . Wstaw nowy test, który ma się zdarzyć w systemie kolejkowym, na przykład w 0,1 s.
• Zakończ cykl pętli - kontynuuj, powtarzaj.

Podając węzłom i samochodom wystarczające dane, nastąpi ruch i kontynuacja.

Edycja: I dodawanie: To oczywiście wymaga dopracowania. Twoja symulacja behawioralna może wymagać różnych linii pomocy, metadanych, okręgów itp. To dałoby pomysł na jedno możliwe rozwiązanie.

Skończyło się na tym, że zasugerowałem DMGregory i działa dobrze. Oto odpowiedni kod (choć nie samodzielny), którego można użyć do obliczenia dwóch stylów stycznych. Jestem pewien, że ten kod nie jest wydajny i prawdopodobnie nie jest nawet poprawny we wszystkich sytuacjach, ale do tej pory działa dla mnie:

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;
    }
};

Oto dwa filmy z powyższym kodem w akcji:

Oto „zewnętrzna” ścieżka: http://youtube.com/watch?v=99e5Wm8OKb0, a oto ścieżka „przejściowa”: http://youtube.com/watch?v=iEMt8mBheZU

Jeśli ten kod pomaga, ale masz pytania dotyczące niektórych części, które nie zostały tutaj pokazane, po prostu opublikuj komentarz i powinienem go zobaczyć za dzień lub dwa.