Wykrywanie kolizji za pomocą krzywych


12

Pracuję nad grą 2D, w której chciałbym przeprowadzić wykrywanie kolizji między ruchomym okręgiem a jakimś statycznym łukiem (być może krzywym Beziera).

Obecnie moja gra zawiera tylko proste linie jako geometrię statyczną i wykrywam kolizję, obliczając odległość od koła do linii i rzutując okrąg poza linię, na wypadek gdyby odległość była mniejsza niż promień okręgów.

Jak mogę zrobić tego rodzaju wykrywanie kolizji w stosunkowo prosty sposób? Wiem na przykład, że Box2D oferuje wykrywanie kolizji z krzywymi Beziera. Nie potrzebuję w pełni funkcjonalnego mechanizmu wykrywania kolizji, po prostu coś, co może zrobić to, co opisałem.


AKTUALIZACJA: Wielkie dzięki za wspaniałe odpowiedzi! Będę musiał przeczytać krzywe Beziera, aby w pełni zrozumieć opisaną metodę. Wrócę do ciebie.

Odpowiedzi:


6

29/09/2012 - 23:20

Stworzyłem git Repo tutaj: https://github.com/ArthurWulfWhite/Bezier-Distance/

Stąd możesz pobrać pliki źródłowe w formacie zip. Zawiera także demo, które można skompilować za pomocą FlashDevelop. Aby skorzystać z wersji demo, otwórz projekt we Flash Develop i kliknij „Testuj projekt”. Podczas uruchamiania wersji demo kliknij LMB, aby losowo wyznaczyć nową krzywą Beziera i nowy okrąg.

Powodzenia!

Link zip jest trudny do zobaczenia - wystarczy użyć Ctrl + F i wpisać zip. To źródło przedstawia kilka tygodni badań i programowania, mam nadzieję, że ci się spodoba.


Jeśli planujesz rekurencyjne dzielenie Beziera na segmenty i sprawdzanie kolizji z nimi, sugeruję utworzenie 100 100 tablic (siatki) i umieszczenie każdego segmentu w czterech najbliższych kwadratach, więc musisz tylko sprawdzić kolizje z 4/10 000 z segmentuje każdą ramkę.

Myślę, że skorzystasz z box2d zarówno jako programista, jak i twórca gier, ponieważ istnieje wiele ukrytych przeszkód w tworzeniu „prostego” silnika fizyki, który sprawia, że ​​ruch wydaje się nieco wyboisty i mniej płynny, niż mógłby być.

Stara odpowiedź: czysty sposób.

Możesz faktycznie sprawdzić, czy koło koliduje z krzywą Beziera, sprawdzając odległość między odległością między środkiem okręgu a najbliższym punktem na krzywej.

Równanie odległości (ogólnie)

wyjaśnione:

Równanie Beziera:

q(t) = (1-t) * ((1-t) * start.(x,y) + t * control.(x,y)) + t*(t * control.(x,y) + (1 - t) * end.(x,y))

Można to podsumować do (z pewną algebrą) - pominę. (X, y) dla czytelności (wciąż są punktami, a nie jedną liczbą)

q(t) = (start -2 * cont + end) t^2 + (-2 * start + 2 * control) + start

Odległość od punktu (x, y) wynosi:

sqrt ((q(t).x - point.x)^2 + (q(t).y - point.y)^2)

Aby znaleźć najbliższy punkt beziera do piłki, musisz wyprowadzić i znaleźć wszystkie punkty, w których pochodna jest równa zero (pierwiastki). Jest to wielomian trzeciego stopnia, więc możesz użyć formuły zamkniętej, ale może to być niewiarygodne, ponieważ precyzja ułamków reprezentowanych przez zmiennoprzecinkowy komputer może być niewystarczająca. O wiele lepiej jest użyć Newtona lub czegoś takiego.

Pochodna, dla której musisz znaleźć korzenie, to:

Zakładając: a = początek b = kontrola c = koniec d = punkt środkowy koła

Pochodna wykorzystująca wolfram alfa

Trudną częścią jest pomnożenie tych punktów, musisz użyć iloczynu.

Jeśli chcesz, mam do tego kod i mogę go tutaj udostępnić w postaci funkcji, która po prostu zwraca wartość logiczną, jeśli występuje kolizja lub nie i kąt kolizji. Podczas naiwnego wdrażania takiego silnika zderzeniowego mogą pojawić się pewne problemy, na przykład szybko poruszająca się kula może zostać złapana między dwiema krzywymi.

Zalecam na razie tego unikać, po prostu zsumuj współczynniki dla osi x i dla osi y i dodaj je.

Użyj dowolnej niezawodnej metody, takiej jak Newton, aby znaleźć pierwiastki, sprawdź odległość od punktów początkowych na ramce, 0 <= t <= 1 do środka okręgu i sprawdź odległość dla dwóch końców bezier (początek i koniec) do środka okręgu, w zależności od tego, który z nich jest najbliższy, powie ci, czy doszło do kolizji.

Jeśli promień jest mniejszy niż minimalna odległość, dochodzi do kolizji.

Kąt jest w przybliżeniu tym, który znajduje się między środkiem okręgu a najbliższym punktem na ramce.

Biorąc to pod uwagę, jeśli naprawdę chcesz stworzyć grę z fizyką kolizyjną, proponuję po prostu iterować bez Beziera

    q(t) = (1-t) * ((1-t) * start.(x,y) + t * control.(x,y)) + t*(t * control.(x,y) + (1 - t) * end.(x,y))

Podziel każdy kawałek na środku rekurencyjnie, aż będzie wystarczająco mały, powiedzmy 10 pikseli lub mniej, następnie z grubsza zbuduj bezier z pudełek i użyj Box2d do fizyki, ponieważ możliwe jest, że napisanie całego tego kodu wykrywania kolizji okaże się świetnym czas, który nie poprawia rozgrywki. Korzystanie z Box2d sprawdziło się w wielu projektach w przeszłości.


Metodę, którą opisujesz, obliczając najkrótszy punkt krzywej, jest dokładnie ta, której obecnie używam z liniami zamiast krzywych. Ale robienie tego samego dla krzywych za pomocą metody, którą wyjaśniasz, wydaje się nieco zbyt skomplikowane. Co, jak rozumiem, jest również tym, co myślisz. A jeśli chodzi o Box2D. Jestem pewien, że to świetna robota. Ale fizyka w mojej grze jest naprawdę bardzo prosta, dlatego zdecydowałem, że w pełni rozwinięty silnik fizyki to przesada.
paldepind

Ile przedmiotów jest w twojej grze? Ilu może ze sobą kolidować? Czasami użycie silnika fizyki może przynieść ogromne korzyści, takie jak dokładne obliczenie czasu kolizji. (klatek przyczyna są dyskretne i kolizje są prawdziwe (nie zdarzają się właśnie podczas renderowania ramkę)
AturSams

Często niż nieoczekiwane wyzwania przy wdrażaniu czegoś nowego i piękno korzystania z interfejsu 2D fizyki, polega na tym, że jest to tak samo jak używanie dowolnego języka programowania, nie wymaga specjalnego wysiłku z Twojej strony, niż zainwestowanie kilku godzin w naukę tego i wyniki są bardzo zadowalające.
AturSams,

Dodałem teraz kilka dodatkowych szczegółów, powodzenia. :)
AturSams

Tworzę prostą grę podobną do Elasto Mania. Tylko trzy ruchome okręgi i geometria statyczna. Cały silnik jest gotowy i działa świetnie. Pozostało mi tylko pozwolić na krzywe, które zamierzam rozwiązać dzięki pomocy w tej odpowiedzi :) Zapraszam do opublikowania wspomnianego kodu. Jak myślisz, jak właściwe byłoby wykorzystanie w prawdziwym życiu? Lepsze niż przekształcenie Beziera w małe linie?
paldepind

7

Aby to zrobić:

  • Podziel krzywą Beziera na segmenty linii odcinkowej i zapisz je.

  • Umieść wszystkie te segmenty w wyrównanym do osi obwiedni dla całej krzywej.

Wykrywanie kolizji :

1) sprawdź, czy kula znajduje się w głównym obwiedni. jeśli nie, nie ma kolizji.

2) w przeciwnym razie sprawdź, czy którykolwiek z wyliczonych powyżej poszczególnych segmentów nie koliduje ze sferą. Zobacz artykuł Przecięcie linii i kuli z Wikipedii .

EDYCJA: jeśli potrzebujesz wysokiej precyzji i chcesz dobrej wydajności, możesz również utworzyć główną ramkę graniczną dla całej krzywej, a następnie podzielić krzywą na dwa segmenty (np .: [0.0 - 0.5]i [0.5 - 1.0]). Tworzenie bouding pole dla każdego z nich, a następnie ponownie podzielić każdy z tych segmentów w dwóch segmentów (dając w ten sposób [0 - 0.25], [0.25 - 0.5]a [0.5 - 0.75], [0.75 - 1.0]). Kontynuuj tak, aż osiągniesz wystarczającą precyzję. na końcu będziesz miał binary treeobwiednię z głównym obwiednią krzywej w katalogu głównym i segmentami linii w liściach. wyszukiwanie w drzewie da ci O(log n)zamiast O(n)(gdzie n= liczba segmentów linii dla krzywej)


To rozwiązanie ma dla mnie sens i jest zdecydowanie najłatwiejsze do zrozumienia i mogę się z tym pogodzić. Ale jestem ciekawy, czy istnieje bardziej „czysta” opcja.
paldepind

5

Przecięcie linii z krzywą Beziera osiąga się matematycznie, dzieląc krzywą. Oznacza to poleganie na właściwości wypukłego kadłuba krzywej i dzielenie jej na mniejsze łuki z różnymi wielokątami kontrolnymi w sposób podobny do divide-et-impera.

W tym artykule omówiono to do pewnego momentu: http://students.cs.byu.edu/~tom/557/text/cic.pdf .

Zaletą jest to, że algorytm działa z dowolną linią, wystarczy zastosować sztywną transformację do krzywej, aby można było uznać linię docelową za równoległą do osi Ox.

Podobnie możesz sprawdzić względem koła i wielokąta każdego takiego łuku Beziera, gdy podzielisz łuk Beziera na dwa pod-łuki. Okrąg powinien przecinać wielokąt kontrolny łuku, aby test krzywej do okręgu miał sens.


Nie przeczytałem jeszcze tego artykułu. Ale jak przejść od przecięcia linii z krzywą Beziera do przecięcia koła i Beziera? Sprawdzanie kolizji z okręgiem i wielokątem wydaje mi się zbyt skomplikowane.
paldepind
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.