Gra 2D, część 6: Wykrywanie kolizji i obsługa jednostek

03.02.2010 - Marcin Milewski
TrudnośćTrudność

Axis-Aligned Bounding Box

Przyjrzyjmy się wykrywaniu kolizji metodą prostokątów wyrównanych do osi układu współrzędnych. AABB będziemy reprezentować w naszym programie jako parę punktów (lewy-dolny oraz prawy-górny wierzchołek, czyli odpowiednio minimum i maksimum na każdej z osi), ale można wybrać inną reprezentację (np. jeden z wierzchołków oraz wysokość i szerokość AABB).

Pojawia się podstawowe pytanie: kiedy dwa AABB kolidują ze sobą i jak to szybko sprawdzić? Po rozrysowaniu kilku sytuacji stwierdzamy, że jeżeli co najmniej jeden z wierzchołków jednego AABB zawiera się w drugim, to zachodzi kolizja - zakładamy, że zawieranie też jest przypadkiem kolizji, gdyż, jak zobaczymy, w naszej grze nie będzie to miało znaczenia. Takie rozumowanie prowadzi do następującego algorytmu:

1
2
3
4
5
6
7
      dla każdego v, który jest wierzchołkiem pierwszego AABB:
         jeżeli v jest w drugim AABB to:
            zwróć "wystąpiła kolizja"
      dla każdego v, który jest wierzchołkiem drugiego AABB:
         jeżeli v jest w pierwszym AABB to:
            zwróć "wystąpiła kolizja"
      zwróć "brak kolizji"

Zauważmy, że sprawdzamy pewien warunek dla 8 wierzchołków. Pytanie do rozważenia: czy istnieje sytuacja, w której żaden z wierzchołków pierwszego AABB nie zawiera się w drugim AABB, a mimo to kolizja występuje?

Jest jednak dużo prostsza metoda wykrywania kolizji! Poniższy algorytm nie jest tak oczywisty jak poprzedni, ale łatwo przekonać się, że działa poprawnie. Sprawdza on, czy kolizja nie zaszła a następnie zwraca zanegowaną wartość. Kiedy więc kolizja nie zachodzi? Oto metoda klasy Aabb, która testuje wystąpienie kolizji między dwoma prostokątami:

1
2
3
4
5
6
7
8
// czy prostokąty się przecinają
bool Aabb::Collides(const Aabb & box) const {
    if (m_min_x > box.m_max_x || m_max_x < box.m_min_x
     || m_min_y > box.m_max_y || m_max_y < box.m_min_y) {
        return false;
    }
    return true;
}

Implementację klasy Aabb można uznać za zakończoną :-) Przedstawiony kod wystarczy aby sprawdzić czy kolizja wystąpiła. My jednak chcielibyśmy otrzymać także informację o miejscu jej wystąpienia, którą niebawem wykorzystamy. Zatem, mając dany prostokąt (nazwijmy go $ P $), chcemy dowiedzieć się czy koliduje on z prostokątem $ Q $ od góry, od dołu, z lewej czy z prawej strony. Zauważmy, że kiedy $ P $ jest poniżej $ Q $ to możemy powiedzieć, że $ Q $ jest powyżej $ P $, co prowadzi nas to do następujących metod:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// czy this jest powyżej box
bool Aabb::IsOver(const Aabb & box) const {
    return Collides(box) 
            && m_min_y < box.m_max_y 
            && box.m_max_y < m_max_y;
}
 
// czy this jest poniżej box
bool Aabb::IsUnder(const Aabb & box) const {
    // czyli czy box jest powyżej this
    return box.IsOver(*this);
}
 
// czy this jest po lewej stronie box'a
bool Aabb::IsOnLeftOf(const Aabb & box) const {
    return Collides(box) 
            && m_min_x < box.m_min_x
            && box.m_min_x < m_max_x;
}
 
// czy this jest po prawej stronie box'a
bool Aabb::IsOnRightOf(const Aabb & box) const {
    return box.IsOnLeftOf(*this);
}
  

Do celów testowych napiszemy metodę, która będzie wyświetlała nasz AABB na ekranie. Ten krótki kawałek kodu może okazać się bardzo pomocny zarówno do lepszego zrozumienia jak działają AABB, jak również do debugowania (ang. debugging). Oto funkcja wyświetlająca prostokąt otaczający jednostkę na ekranie. Należy ją dodać do pliku Renderer.cpp:

1
2
3
4
5
6
7
8
9
10
void Renderer::DrawAabb(const Aabb& box, double r, 
                        double g, double b, double a) const {
    const double tw = m_tile_width;
    const double th = m_tile_height;
 
    DrawQuad(box.GetMinX()*tw, box.GetMinY()*tw,
             box.GetMaxX()*th, box.GetMaxY()*th,
             r, g, b, a);
}
  

Skoro mamy już implementację AABB, moglibyśmy wypróbować ją w praktyce. Jedyne kolizje jakie możemy w tej chwili wykrywać są jedynie typu poziom (map gry) - bohater. Odłóżmy zatem na chwilę ten temat, aby zająć się dodawaniem jednostek (tj. przeciwnicy, pociski, itp.) do poziomu i zarządzaniem nimi w grze. Następnie powrócimy do tematu kolizji, gdyż mamy jeszcze sporo do zrobienia na tym polu.

Dodawanie i usuwanie jednostek z poziomu

W naszej grze, oprócz postaci sterowanej przez gracza chcemy mieć przeciwników oraz broń. Jednostki będą poruszały się ruchem jednostajnie przyspieszonym na osi pionowej oraz ruchem jednostajnym prostoliniowym. W model ruchu będzie jednak można w prosty sposób ingerować. Zwróćmy uwagę na podobieństwo postaci gracza oraz jednostek w sposobie poruszania się. Przyjmiemy następujące założenia (mimo, że nie są do końca słuszne z punktu widzenia programowania obiektowego, to jednak znacznie skrócą kod):

  • Postać gracza jest jednostką - będą potrzebne zmiany w kodzie klasy Player, aby część wspólna ich zachowania była w klasie Entity (z ang. jednostka).
  • Pociski wystrzeliwane przez gracza są jednostkami.
0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com