W poprzednich wpisach pokazywałem jak wykrywać kolizje pomiędzy obiektami kwadratowymi i obiektami okrągłymi. Te metody wystarczą na wykrycie prawie każdej kolizji w grach dwu wymiarowych. Nawet jeżeli kształty nie do końca będą prostokątne lub okrągłe, zawsze można je mniej więcej opisać kwadratem lub kołem. Gra na pewno będzie sprawiała wrażenie realistycznej 🙂
Póki co pokazywałem jedynie przypadki, w których w grze były tylko dwa obiekty. W tym poście opiszę jak efektywnie wykrywać kolizje pomiędzy wieloma obiektami.
Stworzyłem prosty program, podobny do opisanego w jednym ze starszych postów. Tym razem jednak trochę usprawniłem działanie kulek. Wyglądają teraz tak.
Kod można zobaczyć wyświetlając źródło strony. Zawarłem JavaScript wewnątrz pliku HTML. Nie ma w nim nic wyjątkowego. Każdy kto widział moje poprzednie posty z tej serii, powinien załapać o co chodzi w dzisiejszym kodzie.
Moim celem jest dodanie do tego programu wykrywania kolizji. Chcę aby kulki, odbijały się nie tylko od krawędzi płótna ale też od siebie nawzajem. Ponieważ mam do czynienia z okrągłymi obiektami, użyję wykrywania kolizji na podstawie odległości. Pierwszym rozwiązaniem jakie przyszło mi (i zapewne też wielu innym młodym developerom 😉 ) do głowy to stworzenie dwóch zagnieżdżonych pętli for. Dzięki temu sprawdzę każdą kulkę z każdą inną. W taki sposób wyłapię ewentualne kolizje. Do mojego programu w miejscu, w którym aktualizuję położenie obiektów, dodaję ten kod:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
function checkCollisions(balls){ for(var i = 0; i<balls.length;i++){ for(var j = 0; j<balls.length;j++){ if(checkIfHit(balls[i],balls[j])){ console.log("ball: "+i+" touching ball: "+j) } } } } function checkIfHit(obj1,obj2){ var distX = obj1.centerX() - obj2.centerX(); var distY = obj1.centerY() - obj2.centerY(); var totalRad = obj1.radius + obj2.radius; return Math.sqrt(distX*distX+distY*distY)<totalRad; } |
Sprawdzam każdą kulkę z każdą inną. Konsola wypisze odpowiednią wiadomość, jeżeli któreś kulki się się stykają. Wygląda to tak.
Już na pierwszy rzut oka coś jest nie tak. Konsola cały czas wypisuje tę samą parę, nawet jeżeli żadne kulki się nie stykają. Jest to oczywisty błąd. Kod naprawdę sprawdza każdą kulkę z każdą! Wypiszę wszystkie sprawdzane pary:
|
1 2 3 4 5 |
Kulka 0 jest sprawdzana z kulkami 0, 1, 2, 3, 4 Kulka 1 jest sprawdzana z kulkami 0, 1, 2, 3, 4 Kulka 2 jest sprawdzana z kulkami 0, 1, 2, 3, 4 Kulka 3 jest sprawdzana z kulkami 0, 1, 2, 3, 4 Kulka 4 jest sprawdzana z kulkami 0, 1, 2, 3, 4 |
Wyraźnie widać, że tworzone są pary składające się z tych samych kulek. Program loguje kolizje, w momencie, gdy kulka jest sprawdzana z samą sobą.
Łatwym sposobem na naprawienie tego jest wstawienie takiego wyrażenia warunkowego:
|
1 2 3 4 5 6 |
if(checkIfHit(balls[i],balls[j])){ if(i!=j){ balls[i].vector.x *= -1; balls[i].vector.y *= -1; } } |
Sprawdzam, czy wewnątrz drugiej pętli for i nie jest równe j. W ten sposób uniknę sprawdzania tych samych pozycji w tablicy z samymi sobą. Zmieniłem też efekt kolizji. Obracam znaki w wektorze ruchu sprawdzanej piłki. Efekt można zobaczyć tutaj.
Działa! Ok, efekt nie jest może bardzo realistyczny i czasem kulki blokują się na innych kulkach, ale nie o to chodzi w tym wpisie. Najważniejsze jest to, że udało mi się stworzyć działające kolizje pomiędzy wieloma obiektami.
Warto zwrócić uwagę, że zmieniam wektor ruchu tylko sprawdzanej kulki, a w programie wyraźnie widać, że gdy kulki się zderzają, obie zmieniają tor ruchu. Dlaczego? Ponieważ wciąż mamy duplikaty! Czyli sprawdzana kulka i tak na którą wpada, w którymś obiegu zamienią się miejscami. Te same pary są sprawdzane dwa razy, a to nie jest zbyt optymalne.
Oznacza to, że wciąż można usprawnić ten kod. Oto jak obecnie wygląda badanie par pomiędzy kulkami:
|
1 2 3 4 5 |
Kulka 0 jest sprawdzana z kulkami 1, 2, 3, 4 Kulka 1 jest sprawdzana z kulkami 0, 2, 3, 4 Kulka 2 jest sprawdzana z kulkami 0, 1, 3, 4 Kulka 3 jest sprawdzana z kulkami 0, 1, 2, 4 Kulka 4 jest sprawdzana z kulkami 0, 1, 2, 3 |
Hmm… Wciąż są tu powtórzenia. Kulka o numerze 0 jest sprawdzana z każdą inną kulką w pierwszym obiegu. Każdy następny obieg znów bada aktualną kulkę z kulką 0. Takich powtórzeń jest więcej. Jeżeli je wyeliminuję, badanie par wyglądać będzie tak:
|
1 2 3 4 5 |
Kulka 0 jest sprawdzana z kulkami 1, 2, 3, 4 Kulka 1 jest sprawdzana z kulkami 2, 3, 4 Kulka 2 jest sprawdzana z kulkami 3, 4 Kulka 3 jest sprawdzana z kulką 4 Kulka 4 Nie musi być w ogóle badana! |
W ten sposób, z 25 sprawdzeń, które miały miejsce gdy zaimplementowałem dwie pętle for na początku, zostało tylko 10. A co jeśli kulek nie było by 5 a 50? 🙂 Łatwo sobie wyobrazić jak bardzo ulepsza to wydajność gry.
Nadszedł czas na przetłumaczenie tych pięknych idei, na JavaScript. Jak się za to zabrać? Wciąż będę używał dwóch pętli for, po prostu zapobiegnę zbędnym obiegom. Oto jak wygląda ostateczna wersja funkcji checkCollisions:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
function checkCollisions(balls){ for(var i = 0; i<balls.length;i++){ for(var j = i + 1; j<balls.length;j++) { if(checkIfHit(balls[i], balls[j])){ balls[i].vector.x *= -1; balls[i].vector.y *= -1; balls[j].vector.x *= -1; balls[j].vector.y *= -1; } } } } |
Wystarczy rzut oka na wypisane badania par powyżej żeby zauważyć pewną zależność. Aktualne kulki, są badane tylko z kulkami o wyższym indeksie. Badanie tych o niższym jest zbędne. Zamiana tej idei na kod to formalność 🙂 . W drugiej pętli for inicjuję licznik tak aby był równy licznikowi zewnętrznej pętli plus jeden. W ten sposób pętla wykona tylko te obiegi, które są wymagane.
Muszę jeszcze tylko pamiętać o jednym. Każda para jest badana tylko raz. Dlatego, jeśli chcę aby efekt kolizji był widoczny na obu obiektach biorących w niej udział, muszę to zaznaczyć w kodzie.
I to wszystko. Te podstawy kombinatoryki, pozwoliły mi zaoszczędzić sporo obliczeń procesora 🙂
To już ostatni post z serii o kolizjach, ale nie ostatni o tworzeniu gier w JavaScript. Jeżeli chcesz być na bieżąco z tym co tu wrzucam, zachęcam do polubienia mojej strony na facebooku. Zawsze umieszczam tam informacje o nowych postach. Jest to też świetne miejsce aby zadać mi jakieś pytania lub przekazać swoje pomysły i uwagi.