Jak mogę wdrożyć szybkie, dokładne wykrywanie kolizji 2D?

11

Dobrze wiem, jak wykryć kolizję dwóch lub więcej obiektów 2D, ale interesuje mnie, jak zdecydować, czy sprawdzić kolizję. W poprzednich projektach po prostu sprawdzałem każdy obiekt względem każdego innego obiektu (wiem, poziom głupoty O (n ^ 2)) i stworzyłem mniej płynną rozgrywkę.

Różne fora witają wielkość Quadtrees, B-Drzewa i każdego innego rodzaju drzewa lub struktury, o których możesz pomyśleć.

Jaka jest najbardziej efektywna struktura dla określenia, czy należy sprawdzić kolizję?

2d collision-detection data-structure Mike Cluck
źródło
1
Jedną z rzeczy, które warto rozważyć, jest sprawdzanie kolizji tylko dla obiektów, które się przesunęły, i jedyne obiekty, które są blisko ciebie. Mój obecny system działa dobrze (setki tysięcy obiektów) - i to wszystko, co robię.
ultifinitus
Myślę, że gamedev.stackexchange.com/questions/14369/… może ci pomóc. pierwotnie był przeznaczony i algorytm do przetwarzania równoległego, ale myślę, że ten sam algorytm mógłby również poprawić aplikacje jednowątkowe.
Ali1S232,
1
@ultifinitus Właśnie o to pytam. Jak ustalić, które obiekty znajdują się w pobliżu, bez iteracji po każdym obiekcie i sprawdzania jego położenia?
Mike Cluck
Mike, możesz napisać do mnie e-maila na temat jakiegoś konkretnego kodu, którego użyłem, jest w c ++ - lub mogę dać ci podstawową strukturę, choć z tego powodu może być dość dwuznaczna i skomplikowana.
ultifinitus
1
To nie jest duplikat, ponieważ pytałem, jaka struktura najlepiej nadaje się do ustalenia, czy powinniśmy zawracać sobie głowę sprawdzaniem kolizji. To drugie pytanie dotyczyło kolizji przezroczystych i nieprzejrzystych. Nie wspominając o tym, że pytanie zostało zadane około rok przed tym, z którym się łączyłeś.
Mike Cluck

Odpowiedzi:

12

W grze 2d, chyba że obiekty 2D mają bardzo ciężki rozkład na jedną stronę mapy, prawie zawsze jest to jednolita siatka. Złożoność pamięci jest prosta (proporcjonalna do wymiarów mapy), z rozsądnym rozkładem, ma czas wyszukiwania O (1) i średnią log (liczba obiektów / (wiersze * kolumny)) ^ 2 testy przecięcia wykonane na komórkę. Możesz zdecydować o sprawdzeniu tylko komórek, w których poruszał się obiekt, co znacznie poprawia geometrię statyczną. Łatwo jest modyfikować jednolitą siatkę w locie (znacznie mniej kłopotu niż w rozwiązaniach opartych na drzewach) i jest łatwiejsza do wdrożenia. Jedynym momentem, w którym powiedziałbym, aby nie używać go w grze 2D, jest to, że wymagania pamięci jednolitej siatki stają się zbyt duże (powiedzmy, że Space Sim jest rzadki, ale ogromny).

Darcy Rayner
źródło
Jak to rozwiązanie radzi sobie z obiektami graniczącymi z 2 lub 4 komórkami siatki?
ashes999
1
Każda komórka, na którą obiekt się nakłada, uważa się za znajdującą się w, więc obiekt może znajdować się w wielu komórkach. Większość struktur danych przestrzennych poradzi sobie z problemem nakładania się w podobny sposób.
Darcy Rayner
Wow, to bardzo mądre. +1 na zdrowie koleś.
ashes999
1

Jeśli twój świat ma jeden bardzo „długi” wymiar (nazwij go X), w porównaniu do innych możesz zachować obiekty na liście uporządkowanej, którą możesz ponownie posortować, gdy się poruszają, a następnie wykrywanie kolizji oznacza tylko sprawdzanie obiektów, które zachodzą na siebie w osi X.

Inną możliwością jest prowadzenie aktywnych / pasywnych list obiektów i nie zawracaj sobie głowy obiektami pasywnymi (które w ogóle się nie poruszają).

Jeśli wszystkie są średnimi obiektami widocznymi dla gracza na ekranie, wszystko kontra wszystko prawdopodobnie nie jest takie złe.

Poza tym jestem z Darcy, jednolita siatka jest dobra.

MarkR
źródło