Hej!

Crosspost na pl.sci.matematyka, pl.sci.fizyka i pl.comp.programming. FUT
na tę ostatnią.

Sądzę, że temat pasuje na wszystkie trzy grupy, jeśli ktoś uważa, iż tak
nie jest, przepraszam za OT. Na pl.sci.matematyka pisałem o tym problemie,
ale w tym poście chcę go uściślić i opisać moje próby rozwiązania.

Zadałem sobie dla zabawy problem do rozwiązania, który wydawał się dosyć
prosty, ale w rezultacie okazał się znacznie trudniejszy, niż mi się na
początku wydawało.

Zaczynamy od tego, że przestrzenią, w której się poruszamy jest
dwuwymiarowa przestrzeń kosmiczna o bardzo uproszczonej fizyce (np. brak
grawitacji; w domyśle, jeśli o którymś prawie tu nie wspominam, to nie
działa ono w tej przestrzeni). Rozpatrujemy statek kosmiczny, którego
fizyka ruchu jest również bardzo uproszczona.

Parametry statku opisane są przez następujący zestaw parametrów:
- Prędkość maksymalna. Statek może przekroczyć prędkość maksymalną tylko
po działaniu siły trzeciej (na przykład na skutek kolizji). Przy pomocy
pokładowych silników jest w stanie co najwyżej osiągnąć prędkość
maksymalną. Jeśli leci szybciej, przy pomocy silników może co najwyżej
zwolnić.
- Przyspieszenie. Ponieważ w locie piszę sobie programik symulujący
opisane środowisko, jednostką przyspieszenia są piksle/s^2.
- Zwrotność wyrażona w stopniach na sekundę. W odróżnieniu od prędkości
stosuję tu jeszcze bardziej uproszczony model, to znaczy nie istnieje
przyspieszenie kątowe. Statek jest w stanie w dowolnej chwili obrócić się
w dowolną stronę - pod warunkiem, że sumarycznie nie przekroczy wartości
swojej zwrotności.

Ruch statku realizowany jest w zadanym czasie (w domyśle, jest to zwykle
jedna sekunda) i podzielony jest na skończoną liczbę kroków, na przykład
100. W każdym z kroków statek ma do dyspozycji ułamek swoich możliwości,
czyli na przykład jeśli jego przyspieszenie wynosi 100px/s^2, to w jednym
kroku może przyspieszyć o 1 px/s^2 (przyspieszenie jest utożsamione z siłą
ciągu silników). Podobnie jest ze zwrotnością, ale oczywiście zasada ta
nie dotyczy prędkości maksymalnej.

Zadanie jest następujące. Mamy dane parametry początkowe, wśród których
znajdują się parametry statku, jego obecne położenie, wektor ruchu oraz
wektor kierunku opisujący, w którą stronę zwrócony jest statek (kierunki
obu wektorów nie muszą się pokrywać). Poza tymi parametrami dany jest
dodatkowo punkt docelowy. Ogólnym celem jest osiągnięcie przez statek
danego punktu w wyznaczonym czasie. Jeśli nie jest to możliwe, statek musi
spróbować dolecieć jak najbliżej wybranego punktu. Uwaga - punkt musi
zostać osiągnięty (w miarę możliwości) po zakończeniu cyklu czasowego,
czyli po sekundzie od rozpoczęcia lotu. Jeśli więc na przykład statek leci
na wprost celu, może okazać się konieczne spowolnienie jego lotu, aby nie
osiągnął celu zbyt szybko.

W czasie każdego ze stu kroków statek ma możliwość podjęcia dwóch decyzji.
Pierwszą z nich jest obrót o pewien kąt ograniczony jego zwrotnością.
Wartość decyzji musi zawrzeć się w zakresie [-1.0, 1.0], gdzie skrajne
wartości odpowiadają, odpowiednio, obrotowi w lewo i w prawo. Drugim jest
zastosowanie silników - i wartość również musi zawrzeć się w takim samym
zakresie. 1.0 oznacza maksymalny ciąg do przodu, -1.0 - maksymalny ciąg
wstecz (hamowanie). Po podjęciu decyzji najpierw zostaje zaaplikowany
obrót, a potem przyspieszenie. W praktyce druga operacja sprowadza się do
dodania do obecnego wektora ruchu wektora o długości równej chwilowemu
przyspieszeniu i skierowanego w stronę, w którą skierowany jest statek.

Celem jest napisanie mechanizmu decydującego, na bazie danych wejściowych,
jakie decyzje dotyczące ruchu statku podjąć w każdym z "kroków".

Żeby nie było, że chcę gotowiec, sam próbowałem rozwiązać ten problem, ale
bez większych rezultatów.

Najpierw pomyślałem o takim rozwiązaniu. Niech StT (Ship-to-target) będzie
wektorem zaczepionym w statku i wskazującym na cel. Jeżeli podzielimy go
na liczbę kroków, która pozostała do końca ruchu, otrzymamy "idealny"
wektor, który w danym ruchu chcielibyśmy osiągnąć, nazwijmy go Dsv
(Destination-step-vector). Teraz dzielimy wektor obecnego ruchu na 100
części (bo podczas każdego kroku statek rusza się o 1/100 wektora ruchu) i
pojedynczą część nazywamy Mv (Movement-vector). Teraz od Dsv odejmujemy Mv
i dostajemy wektor ciągu, który trzeba przyłożyć, aby przekształcić Mv w
Dsv. Następnie obracamy statek w stronę tego wektora, a jeśli jest już
ustawiony we właściwym kierunku, przykładamy ciąg, aby zmodyfikować wektor
ruchu.

Rozwiązanie to działa... do pewnego stopnia. Kłopot polega na tym, że
wektor docelowy zmienia się z każdym ruchem, co w efekcie zwykle powoduje,
że statek zaczyna zataczać kręgo dookoła celu zamiast do niego dolecieć.

Po pierwszej porażce zacząłem się zastanawiać, jak poleciałbym statkiem,
gdybym mógł ręcznie kierować jego kierunkiem i ciągiem i zauważyłem pewną
ciekawą zależność, że moja strategia zależałaby w dużym stopniu od
możliwości statku. Jeśli na przykład miałbym do dyspozycji duże
przyspieszenie, to od razu obrałbym wektor, który skontrowałby ewentualny
ruch w niewłaściwą stronę i jednocześnie kierował statek w stronę celu.
Gdyby przyspieszenie było niewielkie, najpierw poświęciłbym całą moc
silnika na skontrowanie obecnego ruchu (jeśli byłby niewłaściwy), a
dopiero potem skierowałbym statek w stronę celu i próbował do niego
dolecieć. Problem polega na tym, że nie wiem za bardzo, jak włączyć
powyższy fakt w ścieżkę obliczeń.

Zastanawiałem się nad wyrażeniem obecnego ruchu statku jako sumy
składowych X i Y, ale w układzie współrzędnych wyznaczonych przez wektor
wskazujący na cel. Wówczas wiedziałbym dokładnie, jaki ruch muszę
kontrować. Tylko że nie dało mi to zbyt dużo w kontekście podjęcia
właściwej decyzji.

Napisałem w C#/4.0 programik, który umożliwia puszczenie symulacji
jakiegoś rozwiązania, jeśli jest ktoś chętny, to mogę dopisać kilka
komentarzy i udostępnić.

Chętnie wysłucham wszystkich pomysłów :)

--
! ._______. Warning: Lucida Console sig! //) !
! || spk || www.spook.freshsite.pl / _ """*!
! ||_____|| spook at op.pl / ' | ""!
! | ___ | tlen: spoko_ws gg:1290136 /. __/"\ '!
! |_|[]_|_| May the SOURCE be with you! \/) \ !