Przemieszczanie statków między dwiema planetami wzdłuż ramki, pomijając pewne równania przyspieszenia

OK, opublikowałem to już na stronie math.stackechange.com, ale nie otrzymałem żadnych odpowiedzi :(

Najpierw jest zdjęcie mojego problemu, a następnie opis:

Więc skonfigurowałem wszystkie punkty i wartości.

Statek zaczyna poruszać się po lewej planecie P1z S=0.27 Degreesgametickiem, a kiedy do niego dociera Point A, zaczyna podążać za krzywą Béziera aż do osiągnięcia Point D, a następnie podróżuje wokół właściwej planety P2z tyknięciem S=0.42 Degreesna grę. Różnica Spolega na tym, że podróżuje z tą samą prędkością ruchu wokół planet.

Jak dotąd tak dobrze, uruchomiłem to, teraz mój problem.

Kiedy S P1i S P2różnią się bardzo, statek przeskakuje między dwiema prędkościami, gdy osiąga miejsce docelowe, co wygląda dość źle. Więc muszę przyspieszyć statek między Point Ai Point Dod S P1do S P2.

To, czego mi brakuje, jest w kolorze fioletowym, są to:

• Sposób na obliczenie tyknięć, po których statek porusza się wzdłuż Beziera, biorąc pod uwagę przyspieszenie.

• I sposób na znalezienie pozycji na krzywej Béziera na podstawie T, ponownie biorąc pod uwagę przyspieszenie.

ATM Liczę długość beziera, obliczając odległość między Njego punktami. Myślę , że potrzebuję sposobu na skalowanie Tpotrzebnego do obliczenia Béziera odpowiednio do przyspieszenia.

OK, mam wszystko działające, zajęło to wieczność, więc opublikuję tutaj moje szczegółowe rozwiązanie.
Uwaga: wszystkie próbki kodu są w JavaScript.

Podzielmy więc problem na podstawowe części:

1. Musisz obliczyć długość oraz punkty pomiędzy 0..1krzywą Beziera

2. Musisz teraz wyregulować skalowanie, Taby przyspieszyć statek z jednej prędkości na drugą

Poprawienie Beziera

Znalezienie kodu do rysowania krzywej Beziera jest łatwe, istnieje jednak wiele różnych podejść, jednym z nich jest algorytm DeCasteljau , ale można również użyć równania dla sześciennych krzywych Béziera:

// Part of a class, a, b, c, d are the four control points of the curve
x: function (t) {
    return ((1 - t) * (1 - t) * (1 - t)) * this.a.x
           + 3 * ((1 - t) * (1 - t)) * t * this.b.x
           + 3 * (1 - t) * (t * t) * this.c.x
           + (t * t * t) * this.d.x;
},

y: function (t) {
    return ((1 - t) * (1 - t) * (1 - t)) * this.a.y
           + 3 * ((1 - t) * (1 - t)) * t * this.b.y
           + 3 * (1 - t) * (t * t) * this.c.y
           + (t * t * t) * this.d.y;
}

Dzięki temu można teraz narysować krzywą Beziera dzwoniąc xi yz tktórego waha się od 0 to 1rzućmy okiem:

Uh ... to nie jest równomierny rozkład punktów, prawda?
Ze względu na charakter krzywej Béziera punkty na niej 0...1mają różne arc lenghts, więc segmenty w pobliżu początku i końca są dłuższe niż te, które znajdują się w pobliżu środka krzywej.

Równomierne odwzorowanie T na parametryzacji długości łuku na krzywej AKA

Co więc zrobić? Cóż, w prostych słowach potrzebujemy funkcji do mapowania naszego Tna tkrzywej, aby nasze T 0.25wyniki tbyły na 25%długości krzywej.

Jak to zrobimy? No cóż, my Google ... ale okazuje się, że termin ten nie jest tak łatwy do przeszukiwania , że w pewnym momencie trafisz na ten plik PDF . Co na pewno jest świetną lekturą, ale w przypadku, gdy już zapomniałeś wszystkich matematyki, których nauczyłeś się w szkole (lub po prostu nie lubisz tych symboli matematycznych), jest to całkiem bezużyteczne.

Co teraz? Cóż, idź i Google trochę więcej (czytaj: 6 godzin), a w końcu znajdziesz świetny artykuł na ten temat (w tym ładne zdjęcia! ^ _ ^ "):
Http://www.planetclegg.com/projects/WarpingTextToSplines.html

Robiąc rzeczywisty kod

Jeśli po prostu nie mogłeś się powstrzymać przed pobraniem tego pliku PDF, chociaż już dawno straciłeś swoją wiedzę matematyczną (i udało ci się pominąć link do świetnego artykułu), możesz teraz pomyśleć: „Boże, to zajmie setki linii kodu i tony procesora ”

Nie, nie będzie. Ponieważ robimy to, co robią wszyscy programiści, jeśli chodzi o matematykę:
po prostu oszukujemy.

Parametryzacja długości łuku, leniwy sposób

Spójrzmy prawdzie w oczy, nie potrzebujemy nieskończonej precyzji w naszej grze, prawda? Więc jeśli nie pracujesz w NASA i nie planujesz wysyłać ludzi na Marsa, nie potrzebujesz 0.000001 pixelidealnego rozwiązania.

Więc jak mamy map Tna t? To proste i składa się tylko z 3 kroków:

1. Oblicz Npunkty na krzywej za pomocą ti zapisz arc-length(zwaną też długością krzywej) w tej pozycji w tablicy

2. Aby odwzorować Tna tnajpierw pomnożyć Tprzez całkowitą długość krzywej dostać u, a następnie przeszukać tablicę długościach dla indeksu o największej wartości, która jest mniejsza niżu

3. Jeśli mieliśmy dokładne trafienie, zwróć wartość tablicy o tym indeksie podzieloną przez N, jeśli nie interpoluj trochę między punktem, który znaleźliśmy, a następnym, podziel ponownie rzecz przez Ni wróć.

To wszystko! Spójrzmy teraz na pełny kod:

function Bezier(a, b, c, d) {
    this.a = a;
    this.b = b;
    this.c = c;
    this.d = d;

    this.len = 100;
    this.arcLengths = new Array(this.len + 1);
    this.arcLengths[0] = 0;

    var ox = this.x(0), oy = this.y(0), clen = 0;
    for(var i = 1; i <= this.len; i += 1) {
        var x = this.x(i * 0.05), y = this.y(i * 0.05);
        var dx = ox - x, dy = oy - y;        
        clen += Math.sqrt(dx * dx + dy * dy);
        this.arcLengths[i] = clen;
        ox = x, oy = y;
    }
    this.length = clen;    
}

To inicjuje naszą nową krzywą i oblicza arg-lenghts, a także przechowuje ostatnią długość jako total lengthkrzywą, kluczowym czynnikiem jest tutaj this.lennasza N. Im wyższa, tym dokładniejsze będzie odwzorowanie, ponieważ krzywa wielkości na powyższym obrazku 100 pointswydaje się wystarczająca, jeśli potrzebujesz tylko dobrego oszacowania długości, coś w rodzaju 25wykona już zadanie, mając tylko 1 piksel w naszym przykład, ale wtedy będziesz mieć mniej precyzyjne mapowanie, co spowoduje nierównomierne rozłożenie Tmapowania t.

Bezier.prototype = {
    map: function(u) {
        var targetLength = u * this.arcLengths[this.len];
        var low = 0, high = this.len, index = 0;
        while (low < high) {
            index = low + (((high - low) / 2) | 0);
            if (this.arcLengths[index] < targetLength) {
                low = index + 1;

            } else {
                high = index;
            }
        }
        if (this.arcLengths[index] > targetLength) {
            index--;
        }

        var lengthBefore = this.arcLengths[index];
        if (lengthBefore === targetLength) {
            return index / this.len;

        } else {
            return (index + (targetLength - lengthBefore) / (this.arcLengths[index + 1] - lengthBefore)) / this.len;
        }
    },

    mx: function (u) {
        return this.x(this.map(u));
    },

    my: function (u) {
        return this.y(this.map(u));
    },

Rzeczywisty kod odwzorowania, najpierw robimy proste binary searchna naszych przechowywanych długościach, aby znaleźć największą długość, która jest mniejsza targetLength, a następnie po prostu zwracamy lub wykonujemy interpolację i zwracamy.

    x: function (t) {
        return ((1 - t) * (1 - t) * (1 - t)) * this.a.x
               + 3 * ((1 - t) * (1 - t)) * t * this.b.x
               + 3 * (1 - t) * (t * t) * this.c.x
               + (t * t * t) * this.d.x;
    },

    y: function (t) {
        return ((1 - t) * (1 - t) * (1 - t)) * this.a.y
               + 3 * ((1 - t) * (1 - t)) * t * this.b.y
               + 3 * (1 - t) * (t * t) * this.c.y
               + (t * t * t) * this.d.y;
    }
};

Znów oblicza się to tna krzywej.

Czas na wyniki

Do tej pory używasz, mxa myotrzymujesz równomierne rozłożenie Tna krzywej :)

Czy to nie było trudne? Po raz kolejny okazuje się, że do gry wystarczy proste (choć nie idealne rozwiązanie).

Jeśli chcesz zobaczyć pełny kod, dostępna jest Gist:
https://gist.github.com/670236

Wreszcie przyspieszenie statków

Pozostało już tylko przyspieszyć statki na ich drodze, odwzorowując pozycję, na Tktórej następnie używamy, aby znaleźć się tna naszej krzywej.

Najpierw potrzebujemy dwóch równań ruchu , a mianowicie ut + 1/2at²i(v - u) / t

W rzeczywistym kodzie wyglądałby tak:

startSpeed = getStartingSpeedInPixels() // Note: pixels
endSpeed = getFinalSpeedInPixels() // Note: pixels
acceleration = (endSpeed - startSpeed) // since we scale to 0...1 we can leave out the division by 1 here
position = 0.5 * acceleration * t * t + startSpeed * t;

Następnie zmniejszamy to 0...1, wykonując:

maxPosition = 0.5 * acceleration + startSpeed;
newT = 1 / maxPosition * position;

I proszę bardzo, statki poruszają się teraz płynnie wzdłuż ścieżki.

W przypadku, gdy to nie działa ...

Kiedy to czytasz, wszystko działa dobrze i elegancko, ale początkowo miałem pewne problemy z częścią przyspieszania, kiedy wyjaśniając problem komuś na czacie gamedev, znalazłem ostatni błąd w moim myśleniu.

W przypadku, gdy nie zapomniałeś już o zdjęciu w pierwotnym pytaniu, wspomnę stam, okazuje się, że sjest to prędkość w stopniach , ale statki poruszają się wzdłuż ścieżki w pikselach, a ja o tym zapomniałem. Więc w tym przypadku musiałem przekonwertować przemieszczenie w stopniach na przemieszczenie w pikselach, okazuje się, że jest to dość łatwe:

function rotationToMovement(planetSize, rotationSpeed) {
    var r = shipAngle * Math.PI / 180;
    var rr = (shipAngle + rotationSpeed) * Math.PI / 180;
    var orbit = planetSize + shipOrbit;
    var dx = Math.cos(r) * orbit - Math.cos(rr) * orbit;
    var dy = Math.sin(r) * orbit - Math.sin(rr) * orbit;
    return Math.sqrt(dx * dx + dy * dy);
};

I to wszystko! Dziękuje za przeczytanie ;)

Problem polega na tym, że statek nie wybrałby naturalnie tej trajektorii. Nawet jeśli działa idealnie, nadal nie będzie wyglądać dobrze.

Jeśli chcesz zasymulować płynne przejście między planetami, sugerowałbym jego modelowanie. Równania są bardzo proste, ponieważ masz tylko dwie znaczące siły: grawitację i ciąg.

Musisz tylko ustawić swoje stałe: Masa P1, P2, statek

Z każdym tyknięciem gry (czas: t) robisz 3 rzeczy

1. Obliczyć grawitację p1 na statku i p2 na statku, dodać powstałe wektory do wektora ciągu.

2. Oblicz swoją nową prędkość na podstawie nowego przyspieszenia od kroku 1

3. Poruszaj statkiem zgodnie z nową prędkością

Może to wydawać się dużo pracy, ale można to zrobić za pomocą kilkunastu linii kodu i będzie wyglądać bardzo naturalnie.

Jeśli potrzebujesz pomocy z fizyką, daj mi znać.

Znalazłem doskonały artykuł wyjaśniający możliwe rozwiązanie tego problemu na przykładzie kodu napisanego w javascript. Działa poprzez „przesuwanie wartości t” we właściwym kierunku.

Zamiast tego możemy wykorzystać fakt, że średnia długość nogi d_avg dla dowolnego rozkładu kropek jest prawie identyczna z długościami ramion, które wytworzyłyby równomiernie rozmieszczone kropki (to podobieństwo wzrasta wraz ze wzrostem n). Jeśli obliczymy różnicę d_err między rzeczywistą długością nogi d a średnią długością nogi d_avg, wówczas parametr czasu t odpowiadający każdemu punktowi można przesunąć, aby zmniejszyć tę różnicę.

To pytanie ma już wiele fajnych odpowiedzi, ale uznałem to rozwiązanie za warte odnotowania.

Dziękujemy za doskonałą stronę opisującą sposób rozwiązania tego problemu. Zrobiłem coś nieco innego niż ty w jednym szczególe, ponieważ byłem głęboko ograniczony pamięcią: nie buduję tablicy, ani nie muszę jej szukać odpowiedniego „segmentu” za pomocą wyszukiwania binarnego. Dzieje się tak, ponieważ zawsze wiem, że przechodzę od jednego końca mojej krzywej Beziera do drugiego: Dlatego po prostu pamiętam segment „bieżący” i jeśli widzę, że wykroczę poza granice tego segmentu, aby obliczyć następny pozycję, obliczam następny (lub poprzedni) segment (na podstawie kierunku podróży). Działa to całkiem dobrze w mojej aplikacji. Jedyną usterką, którą musiałem rozwiązać, było to, że na niektórych krzywych wielkość segmentów była tak mała, że ​​mój następny wykres do wskazania był - w rzadkich przypadkach - o więcej niż jeden segment przed bieżącym, więc zamiast po prostu iść do '

Nie wiem, czy to ma sens, ale z pewnością mi pomogło.

Tego rodzaju modelowanie jest dziwne i może dawać dziwne nielogiczne wyniki. Zwłaszcza jeśli prędkość planet startowych jest naprawdę wolna.

Modeluj statki siłą ciągu.

Kiedy statki znajdą się na ostatniej orbicie na planecie startowej, przyspiesz z pełnym ciągiem.

Kiedy statek znajdzie się w pewnej odległości, użyj ciągu wstecznego, aby spowolnić statek do prędkości orbity docelowej planety.

Edycja: Wykonaj całą symulację jednocześnie, gdy węzeł ma zamiar opuścić orbitę. albo wysyłaj wszystkie dane, albo wysyłaj tylko kilka wektorów ruchu w odstępach i interpoluj między nimi.

Jeśli dobrze to rozumiem, twój problem jest nadmiernie ograniczony.

Uważam, że chcesz, aby statek kosmiczny podróżował określoną ścieżką między orbitami w pewnym czasie t , a także chcesz, aby przyspieszył od prędkości s1 do prędkości s2 w tym samym czasie t . Niestety, nie można (ogólnie) znaleźć przyspieszenia, które spełnia oba te ograniczenia jednocześnie.

Będziesz musiał nieco rozluźnić swój problem, aby go rozwiązać.

Natknąłem się na tę odpowiedź, ponieważ chcę równomiernie rozdzielić punkty wzdłuż ścieżki SVG, która wykorzystuje krzywą Beziera.

Mimo, że MDN mówi, że jest przestarzałe, możesz użyć go, path.getPointAtLengthaby uzyskać poprawny wynik. https://developer.mozilla.org/en-US/docs/Web/API/SVGPathElement/getPointAtLength

Obecnie działa w Chrome / Safari / Firefox i powinien również działać w IE / Edge, ale nie zweryfikowałem tych 2.

Problem z przyjętym rozwiązaniem

Jako funkcja wykładnicza Beziera , spodziewamy się różnych wskaźników postępu w różnych obszarach krzywej.

Ponieważ rozwiązanie Ivo interpoluje liniowo między tymi początkowymi próbkami wykładniczymi , niedokładności będą silnie tendencyjne w kierunku końców / środka krzywej (zwykle sześciennej), gdzie te delty są największe; więc jeśli częstotliwość próbkowania nie Nzostanie znacznie zwiększona, jak sugeruje, błędy są widoczne, a przy pewnym poziomie powiększenia zawsze będą widoczne dla danego N, tj. odchylenie jest nieodłączne dla tego algorytmu. Nie nadaje się np. Do grafiki wektorowej, gdzie powiększenie może być nieograniczone.

Przeciwdziałanie stronniczości poprzez kontrolowane pobieranie próbek

Alternatywnym rozwiązaniem jest liniowo przemapować distanceaby tpo przeciwdziałaniu naturalne nastawienie, że funkcja produkuje Beziera.

Zakładając, że tego właśnie pragniemy:

curve length = 10

t      distance
0.2    2
0.4    4
0.6    6
0.8    8
1.0    10

ale oto, co otrzymujemy z funkcji pozycji Beziera:

t      distance
0.2    0.12
0.4    1.22
0.6    2.45
0.8    5.81
1.0    10.00

Patrząc na Npobrane próbki, możemy zobaczyć, gdzie delty odległości są największe, i ponownie próbkować („podzielić”) w połowie odległości między dwiema sąsiednimi odległościami, zwiększając Nje o 1. Na przykład, dzieląc na t=0.9(która jest w połowie największej delty), możemy otrzymać:

0.8    5.81
0.9    7.39
1.0    10.00

Powtarzamy ten proces dla następnego największego przedziału odległości, dopóki maksymalna delta między dowolnymi dwoma odległościami w całym zestawie nie spadnie poniżej niektórych minDistanceDelta, a dokładniej, mniej niż epsilonod określonych odległości, które chcemy zamapować na kroki t; możemy następnie liniowo map nasze pożądanych tczynności do odpowiednich distances. W ten sposób tworzona jest tablica mieszająca / mapa, do której można tanio uzyskać dostęp i której wartości można przewijać między użytkownikami w czasie wykonywania bez uprzedzeń.

Gdy zestaw rośnie N, koszt jego powtórzenia wzrasta, więc najlepiej zrobić to jako proces wstępny. Za każdym razem N, gdy wzrasta, dodaj dwa nowe wynikowe interwały do intervalskolekcji, usuwając jednocześnie stary, pojedynczy interwał, który zastąpiły. Jest to struktura, nad którą pracujesz, aby znaleźć następny największy przedział do podziału na dwa. Posortowanie intervalswedług odległości ułatwia wszystko, ponieważ możesz po prostu oderwać następny element pracy od końca i podzielić itd.

W efekcie powstaje coś, co idealnie chcielibyśmy:

epsilon: 0.01

t            distance
0.200417     2.00417
0.3998132    3.9998132
0.600703     6.00703
0.800001     8.00001
0.9995309    9.995309

Ponieważ zgadujemy na każdym kroku, nie uzyskamy dokładnych dokładnych odległości itp. 2, 4Których chcieliśmy, ale poprzez powtarzanie iteracji zbliżają się one wystarczająco do pożądanych wartości odległości, dzięki czemu możesz mapować swoje tkroki z odpowiednią dokładnością, eliminując uprzedzenia z powodu do prawie równo odległych próbek.

Możesz następnie pobrać np. Tak t=0.5jak Ivo w swojej odpowiedzi, tj. Interpolując dwie najbliższe wartości powyżej ( 3.9998132i 6.00703).

Wniosek

W większości przypadków rozwiązanie Ivo będzie działać dobrze, ale w przypadkach, w których za wszelką cenę należy unikać stronniczości, upewnij się, że twoje distancesą tak równomiernie rozproszone, jak to możliwe, a następnie liniowo zmapowane t.

Zauważ, że dzielenie może być wykonywane stochastycznie zamiast dzielenia środka za każdym razem, na przykład moglibyśmy podzielić ten pierwszy przykładowy przedział t=0.827zamiast w t=0.9.