Kolizje w grach 2D

Zestawienie najpopularniejszych rodzajów kolizji w grach (2D).

Mimo, że kilka kilka (chyba 2) poradników o kolizjach w grach 2D to są one nieco rozrzucone (SAT, bounding-boxy), dlatego postanowiłem zebrać razem w 1 poradniku najbardziej popularne sposoby wykrywania kolizji.

Będę tutaj używał opisów typowo matematycznych przy użyciu języka c++, więc nie jest wymagana znajomość żadnych bibliotek do pisania gier. Do zrozumienia tego co tu się dzieje wystarczy znajomość programowania (w dowolnym języku) na poziomie podstawowym oraz wiedza matematyczna na poziomie gimnazjum/liceum.

Czym są kolizje?


Kolizja w grach to nic innego jak wykrycie, czy 2 obiekty przedstawione przy użyciu figur geometrycznych mają części wspólne, inaczej mówiąc: czy się przecinają. Wykrywanie kolizji służy do m.in. zapobiegania przechodzenia przez siebie dwóch obiektów fizycznych (np. kolizje pomiędzy graczem, a ścianami), wykrycia kliknięcia myszą na obiekcie etc.

Do wykrywania kolizji posługujemy się uproszczonymi wersjami obiektów w zależności od potrzeb, im większe uproszczenie obiektu tym szybsze wykrycie kolizji, jest to szczególnie ważne w momencie gdy na scenie mamy kilka set lub więcej obiektów fizycznych. Jednak im większe uproszczenie tym mniej dokładnie wykrycie kolizji (ilustruje to obrazek poniżej).

W grach dwuwymiarowych najczęstsze uproszczenia obiektów to kolizje pomiędzy: punktami, czworokątami i okręgami i nimi się właśnie zajmiemy, pozostałymi zajmiemy się w ramach innych artykułów (np. wielokątami).

Reprezentacje kolizji w grze
Reprezentacje kolizji w grze

 

Notacja


W dalszej części poradnika będę korzystał z klas takich jak Vector2, Box, Circle i są one zdefiniowane następująco:

Jak widzimy są to najprostsze z możliwych implementacji tych prymitywów i w większości przypadków w zupełności nam wystarczą.

obiekty

 

Implementacja


We wstępie tego paragrafu chciałbym zaznaczyć, że nie znajdziecie tutaj implementacji SAT, a to dlatego że mówimy o prostych algorytmach do wykrywania kolizji, a on już takim prostym nie jest.

 

Punkt-Punkt

Najprostszy z możliwych wypadków, jak wiemy kolizja pomiędzy dwoma obiekatmi zachodzi wtedy gdy istnieją punkty wspólne (punkty przecięcia) pomiędzy tymi obiektami. W przypadku punktów, kolizja zachodzi wtedy gdy punkty są sobie równe.

 

Punkt-Okrąg

Jak wiemy z matematyki, to punkt jest wewnątrz okręgu wtedy i tylko wtedy gdy odległość pomiędzy nim, a środkiem okręgu jest mniejsza bądź równa jego promieniowi.

 

Punkt-Prostokąt (Box)

Tutaj sprawa robi się nieco ciekawsza, ponieważ musimy sobie założyć, że boki naszego czworokąta są równoległe odpowiednio do osi OX i OY, ponieważ opisany poniżej sposób nie działa w przypadku obiektów na których zadziałaliśmy rotacją. Zatem, kiedy punkt jest wewnątrz prostokąta? Chyba zgodzisz się ze mną, że wtedy gdy jego pozycja x jest większa lub równa od lewej pionowej krawędzi oraz mniejsza lub równa pozycji jego prawej krawędzi, analogicznie powtarzamy nasze rozumowanie dla pozycji y.

 

Okrąg-okrąg

Wkraczamy na tereny ciekawszych sytuacji, ponieważ o ile sytuacje z punktem były zazwyczaj dość intuicyjne i trywialne, tak tutaj warto jest sięgnąć po wiedzę matematyczną, którą zdobywa się (o ile dobrze pamiętam) w liceum. Skorzystamy tutaj z twierdzenia o styczności okręgów, czyli przypomnijmy sobie kryterium na styczność okręgów:

Niech: (O,r), (P,R) 2 okręgu o środkach w dowolnych punktach O i P oraz dowolnych promieniach: r,R. Wtedy dla dowolnych okręgów O i P prawdziwe są zależności:

  • okręgi są styczne zewnętrznie (mają 1 punkt wspólny) <=> |OP| = r + R
  • okręgi przecinają się (mają 2 punkty wspólne) <=> |r-R| < |OP| < r + R
  • okręgi są styczne wewnętrznie (1 punkt wspólny) <=> |OP| = |r-R|
  • okręgi są rozłączne wewnętrznie (mniejszy okrąg jest wewnątrz większego) <=> |OP| < |r-R|

Mamy tu potencjalnie sporo liczenia, wszystkie sytuacje powyżej przedstawiają wypadki gdy okręgu posiadają chociaż 1 punkt wspólny, czyli moment gdy występuje kolizja.

Jednak istnieje trik, który pozwala ułatwić wiele rzeczy i zminimalizować ilość obliczeń: jeżeli rozpatrzymy sytuację gdy okręgi NIE mają części wspólnych, tzn. sytuację gdy nie występuje kolizja i zanegujemy wartość tego wyrażenia to otrzymamy pożądany wynik.

Wiemy, że okręgi NIE mają części wspólnych <=> |OP| > r + R.

Z negacji korzysta się dość często, ponieważ jak widzimy czasami jest łatwiej sprawdzić kiedy coś nie zachodzi i później zanegować wynik, niż szukać go w tradycyjny sposób.

 

Prostokąt-Prostokąt (Box-Box)

Kolejna dość ciekawa sytuacja pod kątem matematycznym. Tak jak poprzednio musimy założyć, że ściany czworokąta są równoległe do osi OX i OY.

Tutaj musielibyśmy sprawdzać, czy kolejne wierzchołki prostokątów się zawierają w drugim prostokącie, co oczywiście potrafimy już sprawdzić jednak byłoby to pracochłonne i jak poprzednio skorzystamy z negacji i sprawdzimy kiedy 2 prostokąty są rozłączne zewnętrznie (nie mają części wspólnych).

 

Zakończenie


To wszystko jeżeli chodzi o najczęściej używane i najczęściej spotykane sytuacje, jeżeli jesteś ciekawy jak wykryć kolizję pomiędzy okręgiem, a czworokątem lub pomiędzy dowolnymi wielokątami to zapraszam do kolejnego artykułu o kolizjach 2D.

Dzięki za przeczytanie i jak zawsze:

Code ON!


  • Pan Kulomb

    Kiedy kolejny artykuł?

    • Jeżeli pytasz o kontynuację tematu kolizji, to chciałbym za jednym razem omówić dość dokładnie box-circle i co jest bardziej pracochłonne to SAT, więc najbezpieczniejszą odpowiedzią jest: „po sesji” (czyli lipiec), ale najprawdopodobniej znajdę czas wcześniej (ale kiedy to nie wiem).

  • Crax

    Nie bardzo rozumiem tan temat :/
    Kiedy konkretnie skorzystać z punk punkt?

    Jeżeli mam dwa kwadraty 32 pix na 32 pix to nie łatwiej było by po prostu obliczyć odległość środka jednego od środka drugiego?
    Jeżeli mniejsza od 32 znaczy że zachodzą na siebie, jeżeli równa 32 znaczy że się stykają, jeżeli większa od 32 znaczy że się nie stykają ani na siebie nie zachodzą.

    Po drugie, jak rozumiem najpierw wykonuj ruch, wykrywam kolizje, potem reaguje?
    Na przykład gdy poruszam się graczem, i najdę na ścianę wówczas kolizja zwróci true, że gracz stoi gdzie nie powinien i go cofnie.
    Nie lepiej by było najpierw sprawdzić czy gracz może się gdzieś przesunąć dopiero potem go przesunąć?

    • „Czysty” punkt-punkt wykonuje się mało kiedy, najczęściej przy pociskach.

      To by mogło mieć sens gdybyśmy albo pracowali na 1 obiekcie, albo wygenerowali wszystkie możliwe kombinacji nachodzenia kolizji, obliczenie odległości (szczególnie pierwiastek) jest dla procesora obciążeniem, a i tak ten sposób by się nie sprawdzał przy zrotowanych obiektach, więc w sumie to co ja przedstawiłem jest dużo lepsze bo nie wymaga wykonywania żadnych obliczeń, a twój sposób już wymaga i to nie byle jakich.

      Odnośnie twojego ostatniego pytania, to raczej druga opcja ma więcej sensu i jej się głównie używa, chociaż też z pewnymi trickami i niekoniecznie w dokładnie takiej formie jak to przedstawiłeś.

      • Crax

        Dalej mi to niewiele mówi :/
        Mój problem polega na tym że próbuje dopasować wszystko do mojego projektu.
        (gra rpg typowy silnik tibi) i w takich kategoriach to oceniam 🙂
        Wówczas cała mapa oparta jest na obiektach 32 x 32, bez rotacji duże uproszczenie itd…

        Mógł byś mi może zatem przedstawić jakiś pseudo kod obrazujące jak skorzystać z któregoś z rozwiązań jakie opisałeś wyżej. Może analiza kodu pozwolił by mi bardziej zrozumieć temat :/

  • Stefan

    Co prawda nie tworze gry, ale siedziałem nad kolizjami dobre 3h, wielkie dzięki za pomoc 🙂

  • Marian Awgul

    Chodzi mi o część „Okrąg Okrąg” – czy w komentarzu nie powinno być Odległość między środkami okręgów?

    • Tak, ma Pan rację i już poprawiam 😉

      Nie wiem w czym może być problem, bez kodu. Najlepiej jest to (kod + opis problemu) wrzucić na jakieś forum (ja jak widać stoję średnio z czasem), np na http://forum.pasja-informatyki.pl

      Pozdrawiam

      • Marian Awgul

        Już mi działa kod z tymi kolizjami…brakło mi
        biblioteki „cmath”.
        pozdrawiam