Witam. Dzisiaj poruszymy najbardziej newralgiczny punk wszystkich gier komputerowych – kolizje.

Bez zapoznania się z  tym tematem praktycznie nie da się stworzyć żadnej gry.  Szeroko rozumiane kolizje są jedynym sposobem na wykrycie interakcji gracza z systemem aplikacji. Wszystkie zdarzenia w grach zależne są od dotknięć, odbić, uderzeń lub zbliżeń pewnych obiektów do siebie. Błędy w mechanizmie obsługi kolizji są jednocześnie powodem większości bugów zdarzających się w grach. Dlatego warto poświęcić jak najwięcej czasu, aby dokładnie zgłębić ten temat. Dzisiaj omówimy tylko jego niewielką część, jednak wkrótce można spodziewać się kontynuacji na naszym wortalu.

Stworzymy dzisiaj program, który zobaczyć możecie na filmiku poniżej lub na żywo tutaj.

Na początku trzeba zaznaczyć, że obsługa kolizji w grach dzieli się na dwie zasadnicze części:

- Wykrycie kolizji – problem geometryczny związany z wykryciem nachodzenia na siebie pewnych figur w przestrzeni.

- Odpowiedź kolizji – problem fizyczny związany z obsługą zderzeń kolidujących ze sobą obiektów. Nie wszystkie kolizje w grach są fizycznie obsługiwane. Niektóre kończą się np. zniknięciem danego obiektu lub dodaniem punktów po jej wykryciu.

Jeżeli zabieramy się za tak poważny temat związany z fizyką oraz geometrią matematyczną, to powinniśmy wykorzystać pewne potężne matematyczne narzędzie, które bardzo ułatwi nam pracę – wektory. Pewnie już słyszeliście, że prawdziwa grafika komputerowa nie może istnieć bez wektorów. Jest to prawda. Bronienie się przed wykorzystywaniem wektorów przy programowaniu grafiki (a w szczególności grafiki trójwymiarowej) jest stratą czasu i energii włożonej w projekt. Reprezentowanie pewnych parametrów opisujących stan oraz zachowanie obiektów za pomocą wektorów usprawnia pracę i ułatwia wykonywanie wielu złożonych operacji na nich. Dlatego niechęć do wektorów, która często towarzyszy młodym programistom, należy w sobie zwalczyć i pogodzić się z faktem, że czas poświęcony na ich opanowanie zwróci nam się w przyszłości wielokrotnie.

Do sprawnego korzystania z wektorów niezbędna jest biblioteka funkcji umożliwiających wykonywanie podstawowych operacji na nich. Bibliotekę taką można oczywiście napisać samemu, jednak my skorzystamy z już gotowej, doskonałej biblioteki Sylvester, którą notabene wykorzystywały wszystkie nasze dotychczasowe aplikacje m.in. przy wykonywaniu przekształceń układu współrzędnych. Biblioteka Sylvester opisuje nie tylko wektory. Znajdują się tam, również definicje operacji na macierzach, liniach oraz powierzchniach płaskich. Dokładny opis funkcji, oraz samą bibliotekę znajdziemy pod adresem http://sylvester.jcoglan.com/docs. Dokumentacja przyda się do zrozumienia działania naszego dzisiejszego programu.

Tyle słowem wstępu, zabierzmy się za pisanie kodu. Stworzymy dzisiaj prosty symulator ruchu piłki w zamkniętym czworokącie. Postaramy się odwzorować model fizyki zawierający takie elementy, jak: ruch liniowy, prędkość liniową, opór powietrza, wykrycie kolizji z płaszczyzną oraz aplikację impulsu liniowego po zderzeniu. Efekt końcowy zobaczyć możecie na powyżej. Proponuje również pobrać kod gotowej aplikacji i śledzić go w trakcie przerabiania lekcji. Zabierzmy się do pracy.

Potrzebne będą nam następujące obiekty trójwymiarowe: arena o wymiarach 24 X 20 , kula o promieniu 1 oraz niewielka strałka. Kula będzie się poruszała w dwóch wymiarach wewnątrz areny. Strzałka natomiast pokazywała będzie kierunek wektora nadającego prędkość kuli. Każdy z tych obiektów reprezentowała będzie odpowiednia klasa.

Na początku stworzymy klasę c_Arena. W tym celu do katalogu scripts dodajemy plik o nazwie arena.js i umieszczamy w nim następujący kod:

function c_Arena(){
 this.absorption = 0.1;
 this.model = new Model();
 this.planes = new Array();
 this.planes_amount = 4;
 this.draw = c_Arena_draw;
 this.init = c_Arena_init;
}

function c_Arena_init()
{
 this.model.init("textures/arena.jpg",0,0,Arena_geometry.vertices, Arena_geometry.texCoords, Arena_geometry.indices);
 this.planes[0] = Plane.create([0,0,-10], [0,0,1]);
 this.planes[1] = Plane.create([0,0,10], [0,0,-1]);
 this.planes[2] = Plane.create([12,0,0], [-1,0,0]);
 this.planes[3] = Plane.create([-12,0,0], [1,0,0]);
}

function c_Arena_draw()
{
 this.model.display();
}

Jak widać klasa posiada cztery zmienne oraz dwie metody. Zmienna absorption reprezentuje ilość energii, jaką ściany areny pochłaniały będą podczas uderzenia (zderzenia kuli ze ścianami areny nie będą idealnie sprężyste). Dodatkowo tworzymy tablicę, która zawierała będzie obiekty prostych odpowiadających krawędziom areny oraz zmienną planes_amount określającą ilość owych krawędzi. Zmienna model jest obiektem stworzonej przez nas na jednym z wcześniejszych tutoriali klasy Model. W metodzie init inicjowany jest właśnie ten obiekt. Jako parametry podajemy tutaj tablice z danymi obiektu areny oraz adres do tekstury. Dodatkowo w metodzie tej tworzymy obiekty prostych, które potrzebne będą przy obsłudze kolizji. Konstruktor klasy Plane jako parametry przyjmuje dowolny punkt leżący na płaszczyźnie oraz tablicę współrzędnych jej wektora normalnego. Metoda draw Służyła będzie do wyświetlania obiektu. Jak widać klasa jest dość prosta.

Kod klasy c_Ball jest trochę bardziej skomplikowany. Spójrzymy na nią:

function c_Ball()
{
 this.ray = 1;
 this.position = $V([0,0,0]);
 this.absorption = 0.02;
 this.move = false;
 this.velocity = $V([0,0,0]);
 this.min_velocity = 0.5;
 this.resistence = $V([0,0,0]);
 this.air_coefficient = 0.001;
 this.push_velocity = 50;
 this.model = new Model();

 this.init = c_Ball_init;
 this.draw = c_Ball_draw;
 this.animate = c_Ball_animate;
 this.push = c_Ball_push;
}

Na początku omówimy zmienne:

• ray określa promień kuli, w naszym przypadku 1.
• absorption – ilość energii pochłanianej przez kulę w momencie uderzenia.
• position jest to obiekt klasy wektor stworzony za pomocą konstruktora Vector.create(), do którego $V jest skrótem. Wektor ten reprezentował będzie położenie kuli (początkowo w punkcie 0,0,0).
• move jest to zmienna logiczna ustawiona na true, gdy obiekt jest w ruchu, oraz na false, gdy stoi w miejscu.
• velocity jak można się domyślić jest to wektor reprezentujący prędkość ruchu obiektu.
• min_velocity jest to minimalna prędkość, poniżej której obiekt przestaje się poruszać.
• resistance – wektor sił oporu działających na obiekt w danym momencie. W naszym modelu jedyną siłą oporu będzie opór powietrza.
• air_coeficient – uproszczony współczynnik oporu powietrza.
• push_velocity – wartość wektora prędkości nadawana w momencie pchnięcia.
• model – obiekt klasy model reprezentujący trójwymiarowy obiekt kuli.

Klasa zawiera również metody push, draw, animate oraz init. Zaczniemy od metody init.

function c_Ball_init()
{
 this.model.init("textures/ball.jpg",0,0,Ball2_geometry.vertices,Ball2_geometry.texCoords,0);
}

Znajduje sie tutaj inicjacja obiektu klasy Model.

function c_Ball_draw()
{
  mvPushMatrix();
   mvTranslate(this.position.elements);
   this.model.display();
  mvPopMatrix();
}

W metodzie draw wyświetlany jest nasz obiekt po uprzednim przesunięciu bierzącego położenia układu współrzędnych o wartość wektora position. Przydatna jest tutaj metoda elements klasy Vector zwracająca tablicę wartości poszczególnych współrzędnych obiektu. Oczywiście przed modyfikacją układu współrzędnych odkładamy go na stos i zdejmujemy z powrotem po całej operacji, aby obiekty rysowane na scenie po kuli nie podlegały tej modyfikacji.

Wszystkie obliczenia związane z ruchem kuli wykonywane są w metodzie animate. Rzecz jasna nic nie dzieje się, jeśli zmienna move ustawiona jest na false. Oto kod:

function c_Ball_animate()
{
 if( this.move ){
  //obliczenie siły oporu powietrza
  this.resistance = this.velocity.toUnitVector().x( this.air_coefficient*this.velocity.modulus()*this.velocity.modulus()*-1 );

  //zmniejszenie wektora prędkości o wektor siły oporu
  this.velocity = this.velocity.add(this.resistance);

  //zmiana pozycji o wektor prędkości
  this.position = this.position.add(this.velocity.x(elapsed_s));

  //wyzerowanie prędkości jeśli jest bardzo mała
  if( this.velocity.modulus() < this.min_velocity ){
   this.velocity.setElements([0,0,0]);
   this.move = false;
  }
 }
}

Na początku obliczana jest wartość wektora siły oporu powietrza. Przy tak prostym obiekcie wystarczy wykorzystać uproszczony wzór na opór powietrza, w którym jego wartość równa jest iloczynowi współczynnika oporu powietrza przez długość wektora prędkości podniesioną do kwadratu. Wartość tę mnożymy przez znormalizowany wektor prędkości naszego obiektu. Oczywiście wartość musi być pomnożona przez -1, aby wektor siły oporu skierowany był w kierunku przeciwnym do wektora prędkości.

Wyliczony w ten sposób wektor dodajemy do wektora prędkości. Następnie zmieniamy położenie obiektu dodając do wektora position wektor prędkości pomnożony przez ilość czasu, jaki upłynął od ostatniej klatki. Na koniec sprawdzamy jeszcze, czy aktualna prędkość nie spadła poniżej prędkości minimalnej. Jeśli tak to zerujemy wektor prękości i ustawiamy zmienną move na false.

Ostatnią metodą klasy c_Ball jest metoda push.

function c_Ball_push(angle)
{
 this.velocity = this.velocity.setElements([0,0,this.push_velocity]).rotate(angle * Math.PI / 180.0,  Line.create([0,0,0], $V([0,1,0])));
 this.move = true;
}

Służy ona do nadania wartości wektorowi prędkości w momencie pchnięcia. Operacja wygląda w ten sposób, że najpierw nadajemy odpowiednią wartość tylko dla współrzędnej z, po czym obracamy wektor o kąt podany jako parametr metody. Do obrotu wykorzystujemy metodę rotate, która jako pierwszy parametr przyjmuje wartość kąta mierzonego w radianach, natomiast jako drugi – obiekt linii, dookoła której wykonany ma być obrót. Dla lepszego zrozumienia działania funkcji rotate odsyłam do dokumentacji biblioteki sylvester.

Została nam jeszcze do napisania ostatnia klasa – c_Arrow.

function c_Arrow()
{
 this.model = new Model();
 this.angle = 0;
 this.init = c_Arrow_init;
 this.draw = c_Arrow_draw;
}

function c_Arrow_draw()
{
 mvPushMatrix();
 mvRotate(this.angle, [0,1,0]);
 this.model.display();
 mvPopMatrix();
}

function c_Arrow_init()
{
 this.model.init("textures/arrow.jpg",0,0,BlenderExport.Cone.vertices,BlenderExport.Cone.texCoords,BlenderExport.Cone.indices);
}

Jak widać jest ona bardzo prosta. Zmienna angle reprezentuje obrót strzałki. Później zostanie ona przekazana jako parametr metody push klasy c_Ball.

Ok. Klasy mamy przygotowane, teraz stworzymy sobie odpowiednie obiekty. W pliku index.html dodajemy następujący kod.

var Ball = new c_Ball;
var Arena = new c_Arena;
var Arrow = new c_Arrow;

W pliku init.js inicjujemy stworzone obiekty

function g_Init()
{
 Ball.init();
 Arena.init();
 Arrow.init();
}

W animate.js wywołujemy metodę animate dla obiektu Ball

function g_Animate()
{
 Ball.animate();
}

A w draw.js wyświetlamy obiekty

function g_Draw()
{
 gl.clear(gl.COLOR_BUFFER_BIT | gl.DEPTH_BUFFER_BIT)
 perspective(45, 1.333, 0.1, 100.0);
 loadIdentity();
 mvTranslate([0.0, 0.0, -28]);
 mvRotate(90,[1,0,0]);
 Ball.draw();
 Arena.draw();
 Arrow.draw();
}

Możemy już uruchomić nasz program, jednak nic ciekawego się w nim jeszcze nie dzieje. Czas na wprowadzenie obsługi klawiatury. W tym celu w głównym pliku w funkcji webGLStart() dodajemy dwie linijki kodu:

document.onkeydown = handleKeyDown;
document.onkeyup = handleKeyUp;

Przechwytujemy w ten sposób zdarzenia związane z naciśnięciem i puszczeniem dowolnego klawisza i podpinamy pod nie własne funkcje, które wyglądają następująco:

var currentlyPressedKeys = Array();

function handleKeyDown(event)
{
 currentlyPressedKeys[event.keyCode] = true;
}

function handleKeyUp(event)
{
 currentlyPressedKeys[event.keyCode] = false;
}

Na początku tworzymy tablicę currentlyPressedKeys, która będzie przechowywała boolowskie wartości mówiące o tym, czy dany klawisz jest wciśnięty, czy nie. I właśnie w tym celu funkcja handleKeyDown() ustawia wartość odpowiedniego elementu w tablicy na true, natomiast handleKeyUp() na false.  Pole event.keyCode określa kod Unicode wciśniętego znaku.

Dzięki powyższym operacjom otrzymujemy tablicę opisującą zawsze aktualny stan wszystkich znaków klawiatury. Teraz wystarczy tylko ją wykorzystać. W tym celu tworzymy następującą funkcję:

function g_Handle_keys()
{
 if (currentlyPressedKeys[32])
 {
  //space
  Ball.push(Arrow.angle);
 }
 if (currentlyPressedKeys[37])
 {
   // Left cursor key
   Arrow.angle++;
 }
 if (currentlyPressedKeys[39])
 {
   // Right cursor key
   Arrow.angle++;
 }
 if (currentlyPressedKeys[38])
 {
  // Up cursor key
  Arrow.angle -= 5;
 }
 if (currentlyPressedKeys[40])
 {
  // Down cursor key
  Arrow.angle += 5;
 }
}

Funkcja działa w bardzo prosty sposób. Jeżeli wartość elementu tablicy currentlyPressedKeys o indexie odpowiadającym danemu klawiszowi ustawiona jest na true, następuje jego obsługa.

I tak po wciśnięciu spacji wywołujemy metodę push obiektu Ball, natomiast klawisze strzałek służyły będą do modyfikacji zmiennej angle obiektu Arrow, czyli do obrotu strzałki nadającej wartość wektorowi prędkości kuli w momencie pchnięcia.

Funkcję g_Handle_keys() wywołujemy w globalnej pętli programu, czyli w funkcji tick()

function tick()
{
 g_Time_tick();
 g_Handle_keys();
 g_Animate();
 g_Draw();
}

Uruchamiamy program i zaczyna robić się trochę ciekawiej. Klawiszami PageUp oraz PageDown możemy obracać naszą strzałkę, natomiast po wciśnięciu spacji następuje pchnięcie kuli w wyznaczonym kierunku. Spora część pracy jest już wykonana, jednak chcemy jeszcze aby nasza kula odbijała się od ścian areny. Nadszedł więc czas na kolizje.

Mechanizm obsługi kolizji umieszczamy w funkcji g_Animate.js() po wywołaniu metody animate obiektu Ball. Wygląda on następująco:

const min_dist = 5;
if(Ball.move)
{
  for(var i=0; i intersectionPoint.modulus() )
      {
        do {
          Ball.position = Ball.position.add( Arena.planes[i].normal.x( 0.01 ) );
          movedPlane = Arena.planes[i].translate(Arena.planes[i].normal.x(Ball.ray));
          intersectionPoint = movedPlane.intersectionWith( $L([0,0,0], Ball.position) );
        } while( Ball.position.modulus() > intersectionPoint.modulus() )

    	dot = Ball.velocity.dot( Arena.planes[i].normal );
    	if( dot < 0 ){ dot *= -1; }

    	arena_impulse = Arena.planes[i].normal.x( dot ).x( 2-Arena.absorption-Ball.absorption );
    	Ball.velocity = Ball.velocity.add( arena_impulse );
      }
    }
  }
}

Obsługa kolizji wykonywana jest tylko, gdy kula znajduje się w ruchu. Cały mechanizm umieszczamy w pętli dla każdej ze ścian areny. Na początku następuje sprawdzenie, czy kolizja w ogóle nastąpiła.

Najprościej wykrycie kolizji można by było wykonać poprzez mierzenie odległości środka kuli od ściany i sprawdzenie, czy jest ona mniejsza od promienia kuli. W tej metodzie istnieje jednak pewne ryzyko. Na wolniejszych komputerach oraz przy dużej prędkości lotu może się zdarzyć, że kula między kolejnymi wywołaniami detektora kolizji pokona odległość większą niż jej średnica i zdarzy się to akurat w momencie zbliżania się do krawędzi. W takim wypadku w jednej klatce kula będzie znajdowała się przed ścianą po jednej stronie, i w kolejnej klatce – za ścianą po drugiej stronie. W obu przypadkach odległość będzie większa od promienia, więc kolizja nie zostanie zarejestrowana. Problem ten rozwiązać można na kilka sposobów, my zastosujemy bardziej pewną, choć mniej kompleksową metodę. Algorytm wygląda następująco:

Najpierw sprawdzamy, czy kula położona jest bliżej ściany od minimalnej odległości, dla której wykonujemy dalsze działania. Definiuje ją stała min_dist, która powinna być mniejsza od odległości między ścianą znajdująca się najbliżej środka sceny, a jej środkiem.

Jeśli odległość jest mniejsza od min_dist, znajdujemy punkt przecięcia prostej przecinającej środek sceny oraz punk położenia środka kuli, z bieżącą ścianą przysuniętą do środka sceny o odległość równą promieniowi kuli (movedPlane). Do przesunięcia prostej wykorzystujemy metodę translate(), natomiast do znalezienia punktu przecięcia – metodę intersectionWith() klasy Plane. Metoda intersectionWith() zwraca punkt reprezentowany przez wektor, jego wartość przypisujemy do zmiennej intersectionPoint.

Następnie sprawdzamy, czy środek kuli położony jest dalej od środka sceny, niż znaleziony punkt intersectionPoint. Oba punkty reprezentowane są przez wektor, więc do znalezienia odległości od środka wystarczy obliczyć jego długość. Idealnie nadaje się więc do tego metoda modulus(). Jeśli warunek jest spełniony - nastąpiła kolizja. Trzeba ją teraz obsłużyć.

Przed obsługą odbicia musimy wyciągnąć nasz obiekt ze stanu penetracji. Stan penetracji jest to taki stan, w którym dwa obiekty nachodzą na siebie. Nie jesteśmy w stanie wykryć kolizji dokładnie w momencie zetknięcia się ze sobą dwóch obiektów, dlatego po jej wykryciu cofamy jeden z nich o odległość, jaką nachodzi na drugi.

W naszym przypadku realizujemy to w ten sposób, że w pętli przesuwamy kulę o pewną niewielką odległość wzdłuż normalnej ściany, w którą uderzył, po czym sprawdzamy, czy obiekt wyszedł ze stanu penetracji (tym samym warunkiem, którym wykrywamy kolizje). Jeśli nie – powtarzamy operację. I tak do skutku.

Gdy mamy już pewność, że obiekty nie nachodzą na siebie, wyliczamy iloczyn skalarny wektora prędkości kuli oraz wektora normalnego bierzącej powierzchni, po czym przypisujemy go do zmiennej dot. Wartość tę wykorzystamy do określenia długości wektora impulsu uderzenia ściany. Im mniejszy kąt pomiędzy tymi wektorami, tym ta wartość będzie większa. Albo inaczej mówiąc im większy kąt między płaszczyzną ściany a wektorem prędkości, tym większa wartość zmiennej dot. Jest to logiczne, ponieważ, jeżeli kula uderzy w ścianę na wprost (największy kąt), siła odbicia będzie największa, natomiast jeżeli uderzy w nią pod pewnym kątem, ściana odbije ją z mniejszą siłą.

Wektor impulsu uderzenia wyliczamy nadając długość równą zmiennej dot wektorowi normalnemu ściany, po czym mnożymy go przez dwa (bez tego kula „przykleiła” by się do ściany) oraz zmniejszamy o ilość energii, jaką pochłaniają obydwa obiekty w momencie uderzenia. Wyliczony w ten sposób impuls dodajemy do wektora prędkości kuli.

No i to wszystko. Odpalamy program i widzimy, że po pchnięciu kula faktycznie odbija się od ścian areny.

Pokazany algorytm wykrycia kolizji jest wygodny, choć ma pewne ograniczenia. Nadaje się tylko do zamkniętych wielokątów wypukłych zawierających w sobie środek sceny. Dodatkowo stała min_dist powinna być mniejsza od odległości między środkiem sceny, a ścianą znajdującą się najbliżej środka.

Kod stworzonego dzisiaj programu możecie pobrać tutaj. Jest on prosty, ale może być bazą do bardziej rozbudowanego modelu fizyki. Może komuś uda się na tej podstawie napisać grę sportową o piłce nożnej