Autor Wątek: Wykrycie kolizji w 2D  (Przeczytany 2564 razy)

Offline AS

  • Użytkownik
    • Homepage

# Wrzesień 07, 2010, 19:24:34
Można sobie zobaczyć o czym mówię na: http://eiti.esimple.pl/kloce/
(Lub przeczytać to: Mamy planszę 600x400px po której poruszamy zielonym kwadratem za pomocą myszki. Co sekundę dochodzą nam czerwone kwadraty, które poruszają się jednostajnie, odbijają od ścian i przenikają przez siebie. Gra kończy się w momencie gdy zielony dotknie któregokolwiek z czerwonych. Zarówno zielony jak i czerwone kwadraty mają stały rozmiar 80x80px)

Dysponujemy współrzędnymi (sx,sy) - środka zielonego oraz wektorem enemyArray długości enemies z współrzędnymi środków wszystkich czerwonych. Enemies, oprócz liczby czerwonych, to również liczba sekund jakie upłynęły od początku gry i co za tym idzie - wynik gracza.

Do tej pory sprawdzanie kolizji następowało w najprostszy możliwy sposób - brutalna pętelka wokół enemyArray i sprawdzanie dla każdego czerwonego czy nie zahacza o zielonego. Także liniówka w stosunku do enemies. Niestety funkcja collision() odpalana jest co 10 milisekund, żeby od razu wyłapywać haniebną przegraną gracza.

Może ma ktoś pomysł na lepszy algorytm?
« Ostatnia zmiana: Wrzesień 08, 2010, 21:44:59 wysłana przez AS »

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Karol

  • Użytkownik

# Wrzesień 07, 2010, 20:11:21
Nie za częste te sprawdzenia? IMHO z 40ms by starczyło, aby było ok i płynnie. A szybszego w obliczeniach niż sprawdzenie nachodzenia na siebie dwóch prostokątów to chyba nie ma (bodajże 4 warunki na test).

Offline AS

  • Użytkownik
    • Homepage

# Wrzesień 07, 2010, 20:25:30
Te ms były wyznaczane metodą prób i błędów 10 ms jest w sam raz. Więcej powoduje, że można "przeskoczyć" nad czerwonym. Zresztą ms są bez znaczenia, chodzi o algorytm.

Możliwe, że można zmniejszyć liczbę sprawdzeń. Np. mamy po prawej stronie (od naszego zielonego) czerwony kloc. Sprawdzamy go. Nie ma kolizji. Więc już nie ma sensu sprawdzać pozostałych czerwonych leżących na prawo od tego przed chwilą sprawdzonego. Bo wiadomo, że kolizji z nimi tym bardziej nie będzie. Coś w tym kierunku może, może jakiś podział planszy na obszary...
« Ostatnia zmiana: Wrzesień 07, 2010, 22:47:52 wysłana przez AS »

Offline Spider100

  • Moderator
    • Strona domowa

# Wrzesień 07, 2010, 22:22:20
Chwilę myślałem nad tym problemem, pierwsze co wpadło mi do głowy to algorytm SAP (Sweep and Prune) lub spatial hashing (przy ograniczeniu maksymalnej wielkości boxa) jednak nic z tego nie będzie raczej...
W przypadku gdy wszystkie obiekty się przemieszczają trudno by aktualizacja danych (w jakiejś zorganizowanej strukturze) trwała krócej niż przebieg pętli i zwykle sprawdzenie kolizji.

Offline AS

  • Użytkownik
    • Homepage

# Wrzesień 08, 2010, 21:54:23
Spatial hashing - to by było chyba dobre, gdyby wszystkie kloce odbijały się od siebie, czerwone też. Blisko.

Tego algorytmu Sweep and Prune nie znałem i na chwilę obecną nie rozumiem go, szczerze mówiąc. Ale skoro nic z tego nie będzie raczej...

Offline Minus

  • Użytkownik

# Wrzesień 08, 2010, 22:21:21
W czasie update pozycji enemy to przy okazji sprawdzić kolizję z graczem. Wbrew pozorom o jedną pętle mniej :)

Offline cybek

  • Użytkownik
    • Strona domowa!

# Wrzesień 10, 2010, 18:33:23
Żeby nie można było przeskoczyć, to najprościej by było chyba wyznaczyć prostokąt jaki się tworzy ze starej i nowej pozycji obiektu i na jego podstawie sprawdzać kolizje.

Offline AS

  • Użytkownik
    • Homepage

# Wrzesień 10, 2010, 18:44:51
Nie rozumiem. Mógłbyś bardziej rozwinąć?

Offline djsmtih

  • Użytkownik

# Wrzesień 12, 2010, 00:35:57
Kolega miał chyba na myśli sześciokąt :)
Idea jest taka ,że zapisujesz poprzednią pozycje gracza i dwa kwadraty (na starej i nowej pozycji) łączysz tak aby powstała bryła wypukła. Dla ruchu po przekątnej będzie to jakiś sześciokąt dla ruchu wzdłuż osi prostokąt.
Po stworzeniu takiej bryły liczysz dla niej kolizje.

Offline rm-f

  • Użytkownik
    • Tu trolluje

# Wrzesień 12, 2010, 00:41:34
Kolega miał chyba na myśli sześciokąt :)
Idea jest taka ,że zapisujesz poprzednią pozycje gracza i dwa kwadraty (na starej i nowej pozycji) łączysz tak aby powstała bryła wypukła. Dla ruchu po przekątnej będzie to jakiś sześciokąt dla ruchu wzdłuż osi prostokąt.
Po stworzeniu takiej bryły liczysz dla niej kolizje.
Nie, chodziło oto by polizyć b-boxa z starej i nowej pozycji.
Jeżeli koliduje z wielkim bratem, to potem trzeba policzyć dokładną kolizję ;)

Offline Spider100

  • Moderator
    • Strona domowa

# Wrzesień 12, 2010, 23:55:36
Tyle że to zamiast optymalizować cokolwiek zwiększy ilość obliczeń, bo nadal trzeba test wykonywać dla każdego obiektu.

Offline yorp

  • Użytkownik
    • ProfessionGG Project

# Wrzesień 13, 2010, 01:01:48
tak jak spider100 (albo mial to na mysli ;) ), podziel sobie przestrzen najprostszym algorytmem, albo po prostu wyznacz maksymalne przesuniecie jakie gracz moze wykonac i sprawdzaj kolizje tylko z tymi kwadratami, ktore znajduja sie w promieniu przesuniecia + box.

Offline lethern

  • Użytkownik

# Wrzesień 13, 2010, 02:40:32
Cytuj
Tyle że to zamiast optymalizować cokolwiek zwiększy ilość obliczeń, bo nadal trzeba test wykonywać dla każdego obiektu.
Ta procedura będzie odpalana za każdym ruchem, a nie co 10ms, i przede wszystkim, daje *zbyt* dużą skuteczność (można znaleźć kolizję tam, gdzie jej nie było, jeśli zorbi się zbyt dużą bryłę, np. po 200ms)


Jeśli chcesz zoptymalizować ilość sprawdzeń, możesz spróbować pomysłu z podzieleniem terenu na części i sprawdzaniu tylko obiektów z danego kawałka (i ew. przylegających). Ale tego typu algorytmów jest raczej sporo, kwestia poszukać
« Ostatnia zmiana: Wrzesień 13, 2010, 02:43:14 wysłana przez lethern »

Offline AS

  • Użytkownik
    • Homepage

# Wrzesień 13, 2010, 18:45:48
Albo po prostu wyznacz maksymalne przesuniecie jakie gracz moze wykonac i sprawdzaj kolizje tylko z tymi kwadratami, ktore znajduja sie w promieniu przesuniecia + box.
Maksymalne przesunięcie jakie gracz jest w stanie wykonać w czasie nawet 1ms jest... maksymalne. Tzn. można niestety szybko przeskoczyć kursorem z jednego końca ekranu w drugi.

Cytat: lethern
Ale tego typu algorytmów jest raczej sporo, kwestia poszukać
Oj szukam już trochę i jak widać - nic. Gdybyś znał jakiś to podpowiedz, wystarczy mi tylko jeden, działający.

Offline Minus

  • Użytkownik

# Wrzesień 13, 2010, 20:23:56
Kod: (cpp) [Zaznacz]
if( blok.x+blok.w < gracz.x ) return COLLISION_DUPA; else
if( blok.x > gracz.x+gracz.w ) return COLLISION_DUPA; else
if( blok.y+blok.h < gracz.y ) return COLLISION_DUPA; else
if( blok.y > gracz.y+gracz.h ) return COLLISION_DUPA; else
    return COLLISION_SUCCEED;