Algorytm obliczania ścieżki pocisku do celu o max. 2 rykoszety

Przepraszam za kiepski tytuł, ale nie miałem lepszego sposobu na sformułowanie go ...

Jest więc niesamowita gra Nintendo (tak!) Na Wii o nazwie WiiPlay . Jest w nim 9 minigier, a moja ulubiona to Czołgi! . Chodzi o niszczenie wrogich czołgów COM bez zniszczenia siebie. Oto zrzut ekranu poziomu:

Jednym ze sposobów niszczenia czołgów jest strzelanie kulami. Jest ten limonkowo-zielony czołg wroga, który strzela szybkimi pociskami, które dwukrotnie rykoszetują (o ściany i bloki). Możesz zobaczyć, jak czołg gracza może zostać natychmiast zniszczony, jeśli pozostanie tam, gdzie jest teraz, ponieważ ten zbiornik wapna na środku może wystrzelić kulę, która podąża zieloną ścieżką, którą narysowałem na obrazie.

Jako programista amator zastanawiałem się, w jaki sposób zbiornik wapna może określić, w którym kierunku powinien strzelać, aby uderzyć zbiornik gracza.

Sam o tym myślałem, ale nie wpadłem na żaden możliwy algorytm. Wyjaśnię moje wnioski na wypadek, gdyby kogoś zainspirowały. Dla uproszczenia podczas wyjaśniania zakładam, że ściana jest dowolną powierzchnią, na której kula może odbić się rykoszetem . W ten sposób izolowany prostokąt bloków tworzy cztery ściany.

Doszedłem do wniosku, że 2 punkty, w których rykoszety pocisku zawsze leżą po jednej stronie równoległoboku lub stają się przeciwnymi wierzchołkami równoległoboku. Strzelający czołg przeciwnika i czołg gracza, do którego celuje, niekoniecznie muszą być pozostałymi dwoma wierzchołkami, ale zdecydowanie leżą na liniach współliniowych z każdej z czterech stron równoległoboku. Oto ilustracja 4 możliwych sposobów utworzenia równoległoboku:

HOR-VER oznacza, że ​​kula najpierw uderza w poziomą ścianę, a następnie w pionową ścianę.

A potem utknąłem. Myślałem o poruszeniu się po linii łączącej czołg wroga i czołg gracza wokół mapy, aby zobaczyć, czy tworzy równoległobok z dowolnymi dwoma trafieniami dowolną ścianą, ale nie zawsze to działa, ponieważ czołg wroga i czołg gracza nie są niekoniecznie zbieżne z wierzchołkami równoległoboku.

Nie jestem też pewien ogólnego przebiegu algorytmu. Czy algorytm przyjmuje którąkolwiek z poniższych 2 struktur, czy może mam rację w obu tych przypadkach?

• Staraj się wymyślać możliwe ścieżki i zawsze oznaczaj jedną jako najlepszą (może być najkrótszą, najbardziej niejasną, najbardziej nieuniknioną lub połączoną i ważoną oceną opartą na wielu kryteriach) i zapomnij o reszcie. Ta, która pozostała po wszystkich obliczeniach, jest najlepsza.
• Najpierw określ wszystkie ściany, do których najpierw można dotrzeć za pomocą pocisku (kula nie musi rykoszetować na żadnej innej ścianie, aby dotrzeć do każdej z tych ścian), a następnie określ wszystkie dostępne odległości na każdej z tych ścian (czasami nie jest możliwe dotarcie do odległego punktu na ściana bez rykoszetu, jeśli w pobliżu stoi inna ściana), następnie ponownie określ wszystkie dostępne ściany za pomocą rykoszetu i wszystkie zasięgi dostępne na tych ścianach. Te 4 procesy można wykonać w sposób podobny do śledzenia promieni. Jeśli podczas każdego procesu czołg gracza zostanie trafiony jakimkolwiek promieniem, obierz ścieżkę pocisku zgodnie z tym promieniem.

Moim zdaniem ten algorytm jest trudny do zrozumienia, ponieważ:

• kula może zostać wystrzelona w dowolnym kierunku; i
• na każdej ścianie jest nieskończenie wiele punktów, tak jak w matematyce, gdzie na linii jest nieskończenie wiele punktów.

Ale ludzie Nintendo i tak to zrobili, więc ... ktoś ma pomysł?

Biorąc pod uwagę bezpośrednią linię widzenia, problem jest oczywiście trywialny. Mamy jednak do czynienia z refleksją. Prawidłowe ustalenie, które części sceny można zobaczyć, stanowi wyzwanie przy wdrażaniu odbicia jako części promienia, ponieważ może to spowodować pominięcie niektórych otworów. „Wyszukiwanie binarne” między dwoma obiecującymi kątami również nie jest wykonalne: ze względu na odbicia faktycznie widoczna przestrzeń nie jest ciągła, więc heurystyka „jeśli jest na prawo od A i na lewo od B, musi istnieć cel rozwiązanie między A i B ”jest niedopuszczalne i będzie brakowało rozwiązań„ kreatywnych ”. Zamiast tego poleciłbym zastosowanie refleksji poprzez ponowne uruchomienie znacznika z wirtualnej pozycji - pozycji, w której wydaje się, że nasz strzelający jest widziany w lustrze:

target |obstacle
   X   |
    \  |  X real position
     \   /
      \ /
   ----------- mirror surface
        \
         \
          X virtual position

Zaletą jest to, że promień lustrzany jest teraz linią prostą pochodzącą z wirtualnej pozycji. Próbowałem zilustrować tę technikę na poniższym szkicu:

X oznacza pozycję strzelania, (X) cel. Kolorowe obszary są widoczne.

1. Bezpośrednia linia wzroku: cel nie jest widoczny. Możemy jednak uderzać w powierzchnie (1) i (2).

2. Jedno odbicie. Istnieją dwie wirtualne pozycje ostrzału w obrębie przeszkód. Dolna pozycja ma bezpośredni LOS do celu, więc mamy nasze pierwsze rozwiązanie strzelania: ścieżka pocisku jest częścią promienia między celem a dolną powierzchnią lustra oraz między punktem zderzenia promień-lustro a rzeczywistą pozycją strzelania.

3. Dwa odbicia: górna wirtualna pozycja z pierwszego odbicia może widzieć część dolnej przeszkody przez jej lustrzaną powierzchnię. Ponieważ dozwolone są dwa odbicia, możemy odzwierciedlić tę pozycję w dolnej przeszkodzie. Pozycje są oznaczone jako (I) pozycja rzeczywista, (II) pozycja wirtualna z pierwszego odbicia i (III) pozycja wirtualna z drugiego odbicia.

   Z (III) mamy bezpośredni LOS do celu (X), więc znaleźliśmy inne rozwiązanie strzelania. Ścieżka pocisku biegnie wzdłuż linii X – III do drugiego punktu zderzenia lustra, następnie wzdłuż linii III – II między punktami zderzenia lustra, a na końcu wzdłuż linii II – I od pierwszego punktu zderzenia lustra do rzeczywistej pozycji I.

   W rzeczywistości dolna wirtualna pozycja z pierwszego odbicia może również zostać odbita w górnej przeszkodzie, ale nie doprowadzi to do żadnych bezpośrednich rozwiązań.

Gdy już zorientujesz się, które części przeszkód są widoczne (i dlatego można ich użyć do odbicia kuli), wdrożenie odbicia lustrzanego poprzez wyszukiwanie w pierwszej głębokości wydaje się proste. Aby znaleźć odpowiednie lustrzane powierzchnie, można zastosować techniki przedstawione w Sight & Light Nicky Case'a : zamiast wypróbowywać 360 wektorów - które mogą nie mieć otworów, a także marnować - promienie wystrzeliwujemy tylko na krawędzie przeszkód.

Właśnie poszerzam pomysł Karla Bielefeldta na odbicia 2 ścian:

Podano A i B (zbiorniki). Najpierw musisz wymienić wszystkie ściany, które A może zobaczyć, oraz listę wszystkich ścian, które B może zobaczyć. Następnie tworzysz pary, w których pierwsza ściana znajduje się na liście pięści, a druga ściana różni się od pierwszej ściany i znajduje się na drugiej liście. Musisz wykonać ten test dla wszystkich możliwych par ścian (chyba że znajdziesz sposób na wyeliminowanie kandydatów). Gdy znajdziesz R i S dla danej pary ścian, które sprawdzasz

1) jeśli A ma bezpośrednią wizję R

2) jeśli R należy do ściany1 (ściana jest tylko segmentem, nie cała linia)

3) jeśli R ma bezpośredni dostęp do S.

4) jeśli S należy do ściany2 (ściana jest tylko segmentem, nie cała linia)

5) jeśli S ma bezpośredni dostęp do B.

Aby znaleźć R i S : Ponieważ znasz ścianę 1, możesz wyznaczyć równanie liniowe styczne do ściany 1, ponieważ R należy do linii stycznej do ściany 1, masz relację między 2 współrzędnymi R (kończąc na jednym stopniu swobody dla R) Podobnie jak S (istnieje relacja między współrzędnymi S, ponieważ ten punkt należy do stępu linii do ściany2). Więc teraz masz 2 stopnie swobody i musisz mieć 2 dodatkowe niezależne równania, aby ustalić rozwiązanie. Jedno równanie to:

(AA')/(RA')=(SS')/(RS')

inne równanie to:

(BB')/(SB')=(RR')/(SR')

zauważ, że w powyższych równaniach A, A ', B, B' są znane lub można je obliczyć bezpośrednio. R 'i S' są funkcją współrzędnych R i S i równań ścian. Nie ukończyłem matematyki, więc nie wiem, jak będą wyglądać równania.

Możesz skorzystać z faktu, że kąt opuszczający rykoszet musi być taki sam, jak kąt wchodzący do niego. Dla danej poziomej ścianki z współrzędnej Y coraz dwa stałe zbiorniki ze współrzędnymi (a,b)i (d,e)istnieje tylko jeden kąt która spełnia poniższe równanie.

Wystarczy rozwiązać, xaby uzyskać odległość wzdłuż ściany, na którą musisz celować. Dwie ściany działają tak samo. Masz tylko dwa równania i dwie niewiadome.

Masz schludne diagramy pokazujące, jak kierować promienie, więc zostawię szczegóły, jak określić parę powierzchni odbijających.

Nazwijmy powierzchni, które muszą być hit pierwszej powierzchni A , a drugi B .

Spróbuj uderzyć (widoczny) krawędzie B strzelając A . Innymi słowy, określ punkty, w których można zobaczyć odbicia końców B , patrząc na A wykończone lustrem . To musi być łatwe do zrobienia, masz do dyspozycji tylko jeden punkt odbicia.

Teraz wiesz, że dwa promienie Hit (widoczny) krawędzie B . Nazwijmy je promieniami krawędzi. Oblicz ich odbicia od B; muszą przejść gdzieś poza cel. Możesz ustalić, czy cel leży między nimi, to znaczy na lewo od jednego promienia, ale na prawo od drugiego lub odwrotnie. Jest to trywialne przy użyciu ogólnego równania linii prostej .

Jeśli cel nie znajduje się między promieniami krawędzi, oczywiście nie możesz trafić go żadnym promieniem pośrednim; wybierz inną parę powierzchni.

Jeśli cel znajduje się między promieniami, wyszukaj pośredni promień uderzenia za pomocą wyszukiwania binarnego. Masz dwa kąty strzału odpowiadające promieniom krawędzi, a twój kąt trafienia leży między nimi. Pod warunkiem, że średnica kątowa celu, widziana z punktu strzału, nie jest zbyt mała, będziesz potrzebować kilku iteracji, aż znajdziesz kierunek promienia trafienia.

Oto zdjęcie:

Tutaj dwa promienie krawędzi są pokazane na czerwono i niebiesko. Najwyraźniej możesz znaleźć promień emitowany pod mniejszym kątem niż czerwony, ale większy niż czerwony, aby promień trafił w zielony cel.

Po pierwsze, pamiętasz na lekcji fizyki, kiedy mówiłeś o załamaniu światła? Twój problem można rozwiązać za pomocą tych zasad. Kąt padania jest równy kątowi odbicia. więc czołg wroga musi przebiegać pod każdym możliwym kątem dla pierwszego odbicia, aby drugie odbicie mogło trafić gracza. Kontynuuj także pomysł śledzenia promieni. To się komplikuje, gdy gracz się porusza, ale powinien być wystarczająco dobrym pomysłem, aby zacząć od algorytmu