Planowanie trajektorii 2D statku kosmicznego z fizyką

[10]}realizuję grę 2D ze statkami w kosmosie.

Aby to zrobić, używam LÖVE, który owija Box2D Lua. Ale wierzę, że na moje pytanie może odpowiedzieć każdy, kto lepiej rozumie fizykę niż ja-więc pseudo kod jest akceptowany jako odpowiedź.

Mój problem polega na tym, że nie wiem, jak prawidłowo przenieść moje statki kosmiczne na świecie 2D z obsługą fizyki. Konkretniej:

Statek masy m znajduje się w pozycji początkowej {x, y}. Ma wektor prędkości początkowej {vx, vy} (może być {0,0}).

Celem jest punkt w {xo,yo}. Statek musi dotrzeć do celu z prędkością {vxo, vyo} (lub w jego pobliżu), podążając najkrótszą trajektorią.

Istnieje funkcja o nazwie update(dt), która jest wywoływana często (tj. 30 razy na sekundę). Na tej funkcji statek może modyfikować swoją pozycję i trajektorię, stosując "impulsy" do siebie. Wielkość impulsów jest binarna: można ją zastosować w danym kierunku, lub nie stosować go w ogóle). W kodzie wygląda to tak:

function Ship:update(dt)
  m = self:getMass()
  x,y = self:getPosition()
  vx,vy = self:getLinearVelocity()
  xo,yo = self:getTargetPosition()
  vxo,vyo = self:getTargetVelocity()
  thrust = self:getThrust()

  if(???)
    angle = ???
    self:applyImpulse(math.sin(angle)*thrust, math.cos(angle)*thrust))
  end
end

Pierwszy {[8] } jest tam, aby wskazać, że w niektórych przypadkach (chyba) lepiej byłoby "nie impulsować" i opuścić statek "dryf". Druga ??? część polega na obliczeniu kąta impulsu na danym dt.

Jesteśmy w kosmosie, więc możemy ignorować takie rzeczy jak tarcie powietrzne.

Chociaż byłoby bardzo miło, Nie szukam kogoś, kto by to za mnie zakodował; umieściłem tam kod, aby mój problem jest zrozumiały.

Potrzebuję strategii-sposobu na zaatakowanie tego. Znam podstawy fizyki, ale nie jestem ekspertem. Na przykład, czy ten problem ma nazwę? Tego typu rzeczy.

Wielkie dzięki.

EDIT: Beta dostarczyła prawidłową strategię na to i sędzia uprzejmie wdrożył ją bezpośrednio w LÖVE, w komentarzach.

EDIT2: po więcej googlowania znalazłem również openSteer . Jest na C++, ale robi to, co udawałem. Prawdopodobnie będzie bądź pomocny dla każdego, kto osiągnie to pytanie.

Author: Judge Maygarden, 2010-04-01

6 answers

To się nazywa planowanie ruchu i nie jest trywialne.

Oto prosty sposób na uzyskanie nieoptymalnej trajektorii:

    Przestań. Zastosuj ciąg przeciwny do kierunku prędkości, aż prędkość wyniesie zero.
  1. Oblicz ostatnią nogę, która będzie przeciwieństwem pierwszej, ciąg stały od startu stojącego, który doprowadza statek do x0 i v0. Punkt startowy znajduje się w odległości |v0|^2/(2*thrust) od x0.
  2. dostać się do punktu wyjścia (a następnie dokonać ostatnia noga). Przejście z jednego stojącego punktu do drugiego jest łatwe: pchaj w jego kierunku, aż będziesz w połowie drogi, a następnie pchaj do tyłu, aż zatrzymasz się.

Jeśli chcesz szybkiego i brudnego podejścia do optymalnej trajektorii, możesz użyć podejścia iteracyjnego: zacznij od podejścia nieoptymalnego, powyżej; to tylko sekwencja czasowa kątów ciągu. Teraz spróbuj zrobić małe zmiany tej sekwencji, utrzymując populację sekwencji, które zbliżają się do celu. Odrzuć najgorsze, eksperymentuj z najlepszymi ... jeśli czujesz się odważny, możesz zrobić z tego algorytm genetyczny ... i przy odrobinie szczęścia zacznie się to kręcić.

Jeśli chcesz dokładnej odpowiedzi, użyj rachunku różniczkowego. Spróbuję, a jeśli mi się uda, zamieszczę tutaj odpowiedź.

EDIT: Oto dokładne rozwiązanie prostszego problemu.

Załóżmy, że zamiast ciągu, który możemy skierować w dowolnym kierunku, mamy cztery stałe silniki kierujące w {+X, + Y, - X, - Wskazówki. W danym momencie wystrzelimy co najwyżej jeden z + / - X i co najwyżej jeden z +/-Y (nie ma sensu strzelać +X i-X w tym samym czasie). Więc teraz problemy X i Y są niezależne (nie są w pierwotnym problemie, ponieważ ciąg musi być dzielony między X i Y). Musimy teraz rozwiązać problem 1-D ... i zastosować go dwa razy.

Okazuje się, że najlepsza trajektoria polega na pchaniu w jednym kierunku, potem w drugim i nie wracaniu ponownie do pierwszego. (Wybieg jest przydatne tylko wtedy, gdy rozwiązanie drugiej osi zajmie więcej czasu niż Twoje, więc masz czas na zabicie.) Najpierw Rozwiąż problem prędkości: Załóżmy (WLOG), że prędkość docelowa jest większa niż prędkość początkowa. Aby osiągnąć prędkość docelową, potrzebny jest okres ciągu ( + ) czasu trwania

T = (Vf - Vi)/a

(używam Vf: prędkość końcowa, Vi: prędkość początkowa, a: wielkość ciągu.)

Zauważamy, że jeśli to wszystko, co robimy, lokalizacja nie wyjdzie dobrze. Rzeczywista ostateczna lokalizacja będzie be

X = (Vi + Vf)T/2

Więc musimy dodać korektę

D = Xf - X = Xf -(Vi+Vf)T/2

Teraz, Aby miejsce wyszło dobrze, dodajemy okres ciągu w jednym kierunkuprzed i równy okres w przeciwnym kierunkuPo . To pozostawi ostateczną prędkość niezakłóconą, ale da nam trochę przesunięcia. Jeśli czas trwania tego pierwszego okresu (i trzeciego) wynosi t, to przesunięcie, które otrzymujemy z niego, wynosi

d = +/-(at^2 + atT)

+ / - zależy od tego, czy wciśniemy + wtedy -, czy - następnie +. Załóżmy, że jest +. Rozwiązujemy kwadrat:

t = (-aT + sqrt(a^2 T^2 + 4 a D))/2a
I skończyliśmy.
 8
Author: Beta,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-04-01 18:23:52

W przypadku braku dodatkowych informacji, możemy założyć, że istnieją 3 siły działające na statek i ostatecznie dyktujące jego trajektorię:

  • "impulsy ": [użytkownik/program sterowany] Siła.
    Użytkownik (lub program) wydaje się mieć pełną kontrolę nad tym, tj. kontroluje kierunek impulsu i jego ciągu (prawdopodobnie w zakresie od 0 do max)
  • jakaś zewnętrzna siła : nazwij to grawitacją, cokolwiek...
    Taka siła może być napędzana przez kilka źródeł ale jesteśmy po prostu zainteresowani połączoną siłą: w danym czasie i przestrzeni ta zewnętrzna siła działa na statek z określoną siłą i kierunkiem. Użytkownik / program nie ma nad nimi kontroli.
  • inercja : jest to związane z aktualną prędkością i kierunkiem statku. Siła ta zwykle powoduje, że statek porusza się w bieżącym kierunku z aktualną prędkością. Mogą istnieć inne parametry sterujące bezwładnością, ale generalnie jest ona proporcjonalna do zarówno prędkość, jak i masa statku (intuicyjnie łatwiej będzie zatrzymać statek, jeśli jego aktualna prędkość jest mniejsza i / lub jeśli jego masa jest mniejsza)

Najwyraźniej użytkownik / program kontroluje tylko (w granicach) pierwszą siłę.
Nie jest jasne, z pytania, czy problem pod ręką jest:

  • [Problem A] napisać program, który odkrywa dynamikę systemu (i / lub dostosowuje się do zmian tej dynamiki).
    albo..
  • [Problem B] to zaproponuj model-wzór - który może być użyty do obliczenia połączonej siły ostatecznie przyłożonej do statku: "ważonej" sumy impulsu sterowanego przez użytkownika i dwóch pozostałych sił napędzanych przez system / fizykę.

To drugie pytanie, Problem B, jest łatwiej i zwięźle wyjaśnione, więc zaproponujmy następujący model:

Constant Parameters:
  ExternalForceX   = strength of the external force in the X direction
  ExternalForceY   = id. Y direction
  MassOfShip       = coeficient controlling 
Variable Parameters:
  ImpulseAngle     = direction of impulse
  ImpulseThrust    = force of thrust
Formula:
  Vx[new] = (cos(ImpulseAngle) * ImpulseThrust) + ExternalForceX  + (MassOfShip * Vx[current])
  Vy[new] = (sin(ImpulseAngle) * ImpulseThrust) + ExternalForceY  + (MassOfShip * Vy[current])

Zauważ, że powyższy model zakłada stałą siłę zewnętrzną (stałą zarówno pod względem siły, jak i kierunku); to znaczy: podobną do tej z pole grawitacyjne stosunkowo odległe od wyświetlanego obszaru (podobnie jak grawitacja ziemska, rozpatrywana w zasięgu boiska piłkarskiego). Jeśli skala wyświetlanego obszaru jest duża w stosunku do źródła (- ów) sił zewnętrznych, termin środkowy powyższych wzorów należy zmodyfikować tak, aby obejmował: współczynnik trygonometryczny oparty na kącie między środkiem źródła a bieżącą pozycją i / lub współczynnik proporcjonalny [odwrotnie] oparty na odległości między środkiem źródła. źródło i aktualna pozycja.
Podobnie zakłada się, że masa statku pozostaje stała, może być zmienna, bazując na masie statku po opróżnieniu, do której masa paliwa jest usuwana/dodawana w miarę postępu gry.

Teraz... Wszystko to zakłada, że dynamika systemu jest kontrolowana przez projektanta gry: zasadniczo wybierając zestaw wartości dla wspomnianego parametru i ewentualnie dodając trochę złożoności w matematyce wzoru (a także zapewniając odpowiednie skalowanie, aby ogólnie "utrzymać" statek w obszarze wyświetlania).

Co by było, gdyby zamiast tego dynamika systemu była łatwo zaprogramowana w grze (i zakładana jako ukryta / losowa), a zadaniem jest napisanie programu, który będzie stopniowo decydował o kierunku i wartości ciągu impulsów do kierowania statku do docelowego celu, w taki sposób, aby jego prędkość na celu była jak najbliżej getTargetVelocity()? To jest "Problem A".

Ten typ problem można rozwiązać za pomocą kontrolera PID . W nuthell taki kontroler "decyduje" o ilości akcji (w tym przypadku gry = jaki kąt impulsu i ilość ciągu zastosować), na podstawie trzech, ważonych, czynników, luźno zdefiniowanych poniżej: {]}

  • jak odległe są obecne wartości od "zadanego punktu": jest to P = proporcjonalna część PID
  • Jak szybko zbliżamy się do" punktu zadanego": jest to D = Pochodna części PID
  • Jak długo i jak bardzo daleko nam do "punktu zadanego": jest to i = Intergralowa część PID

Mniej zaawansowany kontroler może na przykład używać tylko współczynnika proporcjonalnego. Skutkowałoby to oscylacją, czasami z dużą amplitudą po obu stronach zadanego punktu ("jestem X jednostki daleko od miejsca, w którym powinienem być: pozwól mi szarpnąć kierownicę i nacisnąć gaz"). Takie przekroczenie punktu zadanego jest łagodzone przez czynnik Pochodny ("tak, wciąż nie jestem tam, gdzie powinienem być ale postęp, który zrobiłem od czasu ostatniego sprawdzenia jest bardzo duży: lepiej trochę zwolnić"). Wreszcie część integralna bierze pod uwagę fakt, że wszystkie rzeczy są równe w odniesieniu do połączonej części proporcjonalnej i pochodnej, mniejsze lub większe działanie byłoby właściwe w zależności od tego, czy byliśmy" poza torem " przez długi czas, czy nie i znacznie poza torem byliśmy przez cały ten czas (np. "Ostatnio śledziliśmy raczej blisko miejsca, w którym powinniśmy być, nie ma sensu robić rash moves")

Możemy omówić szczegóły implementacji kontrolerów PID do konkretnych potrzeb gry Statek kosmiczny, jeśli jest to faktycznie wymagane. Pomysł polegał na dostarczeniu smaku tego, co można zrobić.

 3
Author: mjv,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-04-01 16:15:14

Aby po prostu dostać się z aktualnej pozycji do miejsca docelowego z prędkością początkową, następnie zastosować ciąg wzdłuż znormalizowanej różnicy między najkrótszą ścieżką a aktualną prędkością. Nie potrzebujesz tego kąta.

-- shortest path minus initial velocity
dx,dy = x0 - x - vx, y0 - y - vy

-- normalize the direction vector
magnitude = sqrt(dx*dx + dy*dy)
dx,dy = dx/magnitude, dy/mangitude

-- apply the thrust in the direction we just calculated
self:applyImpulse(thrust*dx, thrust*dy)

Zauważ, że nie bierze to pod uwagę prędkości celu, ponieważ staje się to niezwykle skomplikowane.

Mam bardzo mały moduł Lua do obsługi wektorów 2D w Ten pojemnik na pasty. Możesz z niego korzystać. Powyższy kod zmniejszyłby do:

d = destination - position - velocity
d:normalize()
d = d * thrust
self:applyImpulse(d.x, d.y)
 1
Author: Judge Maygarden,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-04-01 14:54:22

Wyrzucasz paliwo? Twoja masa zmieni się z czasem.

Ciąg jest siłą reaktywną. To szybkość zmiany masy, razy prędkość wydechu w stosunku do statku kosmicznego.

Czy masz siły zewnętrzne? Jeśli to zrobisz, muszą one wejść do obliczeń impulsowych.

Załóżmy magiczny ciąg bez wyrzucania masy i bez zewnętrznych sił.

Impuls ma jednostki pędu. To Całka siły nad czas.

Po pierwsze, musisz dowiedzieć się dokładnie, co API nazywa "ciąg" i impuls. Jeśli podajesz mu ciąg pomnożony przez Skalar (liczbę), to applyImpulse musi zrobić coś innego z Twoim wejściem, aby móc użyć go jako impulsu, ponieważ jednostki nie pasują do siebie.

Zakładając, że Twój "ciąg" jest siłą, następnie pomnożysz ten ciąg przez przedział czasu (1/30 sekundy), aby uzyskać impuls i rozbić składniki.

Nie wiem czy odpowiadam na twoje pytanie, ale mam nadzieję, że to pomoże Ci trochę zrozumieć fizykę.

 0
Author: John,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-04-01 14:40:42

Łatwiej o tym pomyśleć, jeśli rozdzielimy prędkość statku na składniki, równoległe i prostopadłe do wektora prędkości celu.

Biorąc pod uwagę wzdłuż osi prostopadłej, statek chce jak najszybciej zbliżyć się do pozycji celu, a następnie pozostać tam.

Wzdłuż osi równoległej powinien przyspieszać w dowolnym kierunku, który zbliży go do docelowej prędkości. (Oczywiście jeśli to przyspieszenie zajmie z dala od punktu docelowego, musisz zdecydować, co zrobić. Przelecieć obok punktu, a potem zawrócić?)

Poradziłbym sobie z tymi dwoma osobno, i pewnie najpierw prostopadle. Gdy zacznie działać, a jeśli to nie okaże się wystarczająco miłe, możesz zacząć myśleć o tym, czy istnieją sposoby, aby statek wystrzelił inteligentne kąty między prostopadłymi i równoległymi.

(EDIT: zapomniałem też wspomnieć, że to będzie wymagało pewnej korekty, aby poradzić sobie ze scenariuszem gdzie są przesunięte dużo w kierunku prostopadłym, ale nie wiele w kierunku równoległym. Ważną lekcją jest wzięcie składników, które dają użyteczne liczby, na których można oprzeć decyzję.)

 0
Author: Chris Burt-Brown,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-04-01 15:02:55

Twój kąt jest odwrotną styczną przeciwną / przylegającą

So angle = InvTan (VY/VX)

Nie wiesz, o czym mówisz, jeśli chodzi o chęć dryfowania??

 -1
Author: MindStalker,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-04-01 14:06:00