Jaki jest najskuteczniejszy sposób znalezienia punktu przecięcia pocisku i mapy bitowej?

W odpowiedzi na moje wcześniejsze pytanie dotyczące znalezienia nachylenia terenu mapy bitowej 2D muszę teraz poznać najlepszy sposób znalezienia punktu na terenie 2D, w który trafił pocisk. Oczywiście widzę, czy jakieś piksele pod pociskiem przecinają teren, ale mówią, że przesunęły się dość głęboko w teren.

Jaki jest najlepszy sposób, aby cofnąć się, aby ustalić, gdzie początkowo się zderzył? Mógłbym przesunąć X pikseli jednocześnie do poprzedniej pozycji pocisku, ale jaka byłaby dobra wartość X? I czy jest mądrzejszy sposób? Może przesunięcie o połowę odległości, a potem o ćwierć itd.?

W przypadku testów zderzeniowych nie powinieneś przeprowadzać testów statycznych kleszcza za kleszczem, powinieneś wykonywać testy śledzenia / przeciągnięcia.

Istnieje wyczerpująca lista różnych formuł dla różnych rodzajów prymitywów: http://www.realtimerendering.com/intersections.html

To oczywiście zakładając, że możesz rozbić swój teren na pewien zestaw prymitywów, na których możesz testować (np. Segmenty linii). Można to zrobić na różne sposoby.

Zobacz także to pytanie (tylko nieznacznie powiązane): Jaki jest dobry algorytm do wykrywania kolizji między ruchomymi sferami?

Wyszukiwanie binarne nie pomoże, jeśli masz cienkie fragmenty scenerii i szybko poruszające się pociski - możesz je przegapić.

Myślę, że najlepszą opcją jest przeciągnięcie linii z przodu pocisku wzdłuż ścieżki, którą podąża, piksel za jednym razem. Możesz najpierw sprawdzić granicę całego woluminu, aby uniknąć robienia tego na każdym kroku.

Ponieważ pocisk prawdopodobnie nie przesunie ogromnej liczby pikseli na każdą klatkę (nie byłoby gładko na ekranie), nie widzę powodu, aby nie sprawdzać każdego piksela na ścieżce. Algorytm linii Bressenham jest twoim przyjacielem i upewnia się, że masz lokalną kopię bitmapy, ponieważ ogólnie nie chcesz mieć dostępu do pamięci wideo dla każdego piksela. Zakłada się, że teren mapy bitowej jest w pełni losowy (jak na zniszczenia robaków). Jeśli twój świat jest oparty na kafelkach, możesz pominąć każdy kafelek, o którym wiesz, że jest pusty, ale jak wspomniano wcześniej, chyba że masz ogromną liczbę pocisków do sprawdzenia, nie mogłem wymyślić platformy, która potrzebowałaby zbyt wolno aby przetestować piksel po pikselu, a nie będziesz musiał definiować swojego świata w prymitywach (klon robaków sprawiłby, że byłoby to trudne)

Oprócz innych odpowiedzi możesz przyspieszyć tę czynność, jeśli chcesz zrobić małą księgowość dotyczącą „zbierania” wiązki pikseli w bloki o „znanym podobnym stanie”. Np. Możesz zapisać wysokość najwyższego kawałka terenu, więc możesz przyjąć za pewnik, że pocisk nie uderzy niczego, o ile jest powyżej tego. Możesz także zapisać wysokość najniższej przestrzeni „powietrznej”, abyś wiedział, że jeśli pocisk dotrze na tę wysokość, to musi coś uderzyć (chociaż może to być najlepiej wykorzystane jako kontrola zdrowia psychicznego). Idąc dalej, możesz przechowywać prostokąty reprezentujące obszary, które są wszystkim terenem i inne prostokąty, które są powietrzem, ale może to być więcej pracy niż wartości.

Ostatecznie najlepszą metodą będzie prawdopodobnie „przechowywanie wysokości każdej kolumny terenu”, a następnie po prostu obliczanie wysokości pocisku na każdym etapie jego ścieżki. Nie mogę rozmawiać z bardziej nowoczesnymi grami, ale wierzę, że kiedy stworzyłeś „jaskinię” w Spalonej Ziemi, to teren nad tą jaskinią spadł prosto w dół, nie pozostawiając żadnych nawisów. Jeśli chcesz zwisów, praca będzie nieco większa, ale będzie przedłużeniem tego podstawowego pomysłu. (Wskazówka: najpierw uruchom podstawowy pomysł!)

Ponieważ twój teren jest prawdopodobnie całkowicie arbitralny, nie ma skrótów. Nawet jeśli zmusisz teren do utworzenia splajnu lub czegoś takiego, będzie to denerwować, gdy zaczniesz go niszczyć, a testy przecięcia linii z splajnem są iteracyjne i niedoskonałe lub wyczerpujące i bezcelowo powolne dla twojego rodzaju problemu.