SFML-owe zabawy #10 - Wykrywanie kolizji


2018-11-24, 03:43

Mechanizmy wykrywania kolizji są nierozłącznymi częściami każdej gry komputerowej. Początkowo to zagadnienie wygląda na skomplikowane, ale koniec końców - zawsze stosuje się pewne uproszczenia i tricki ;) Zobaczcie, jak to wygląda w naszym projekcie Mario::Edit!


Uwaga. Wszystko, o czym piszę poniżej znajduje się na branchu iteration-9 w repozytorium projektu, o tutaj: https://github.com/CppPolska/MarioEdit/tree/iteration-9. Jeżeli masz uwagi odnośnie kodu, bądź chcesz dołączyć do projektu - daj znać w komentarzu :)


Co udało się zrobić w tej iteracji?

Muszę przyznać, że bieżącą iterację potraktowałem bardzo poważnie. Działałem regularnie przez całe trzy tygodnie, dzięki czemu udało się zrobić całkiem sporo! Poszedłem naprzód zarówno z refactoringiem (który stał się nieodłączną częścią każdej iteracji) jak i z testami. Udało mi się również pociągnąć do przodu jedną funkcjonalność! :) Ale po kolei…

Refactoring & bugfixing

Obecną iterację podobnie jak poprzednie rozpocząłem od wielkiego sprzątania. A było co sprzątać :)
Poczynając od zmian związanych z nowym standardem, przez drobne potyczki nad skryptem budowania, po bugfixing.

Porządek z pointerami

Jak to się mówi: szewc bez butów chodzi. To powiedzenie idealnie pasuje do obecnej sytuacji. Pod natchnieniem napisałem ładny wpis o tym jak używać smart pointerów, ale samemu nie trzymałem się zasad, o których pisałem! Dlaczego tak wyszło? Bo “wyszło” to tutaj odpowiednie słowo. Moja wiedza na temat inteligentnych wskaźników była bardzo okrojona i niepoukładana. Byłem wtedy przekonany, że std::unique_ptr jest rozwiązaniem dla wszystkich moich problemów. Pewnego dnia przysiadłem mocniej do tematu i poukładałem sobie wszystko od nowa, w efekcie czego powstał wspomniany wpis. Okazało się wtedy, że moje założenia były… błędne (dzięki Wojtek za pomoc!). Po pierwsze, shared_ptr niesie za sobą nieco większe koszty względem unique_ptr. Po drugie, praca na shared_ptr może jednak skończyć się wyciekiem pamięci. Postanowiłem więc wszędzie tam, gdzie się da zamienić shared_ptr na unique_ptr.

Drobne zmiany w skrypcie CI

Ta zmiana wyszła całkiem przypadkiem, bo po aktualizacji systemu operacyjnego. Zainstalowałem sobie nową wersję MacOs, po czym przysiadłem do prac nad projektem. Bump. Mario::Edit nie zbudował się. W moim systemie brakowało biblioteki libstdc++, która od długiego czasu była oznaczona jako przestarzała. Mój system stwierdził, że już nie będzie jej udostępniał. Nie przypominałem sobie, abym gdziekolwiek używał tej biblioteki, zatem moje podejrzenia padły na biblioteki zewnętrzne. Po krótkim researchu okazało się, że SFML w wersji 2.5.0 z niej korzysta. Najlepszą z dostępnych opcji była aktualizacja SFML do wersji 2.5.1, która korzysta z nowej biblioteki: libc++.

Stosowanie std::variant oraz std::any

Na naszym blogu pojawiło się już kilka wpisów związanych z C++17. Nowy standard oferuje dużą gamę nowości, które rozwiązują sporo problemów w mig. Do tego grona należą m.in. variant, any oraz optional. Znalazłem w projekcie kilka miejsc, w których można by ich użyć. Popatrzmy na przykładowy listing:

if (cursor.isMouseMoved()) {
    auto registeredDragOnTiles = tileEventRegistry->getRegisteredDragOnTiles();
    for (auto &dragOnTile : registeredDragOnTiles) {
       dragOnTile->drag();
    }
}

Ten kod reprezentuje obsługę przeciągania puzelka. W innym miejscu (w innej klasie) mamy bardzo podobny kod:

if (cursor.isMouseMoved()) {
    auto registeredDragOnFigures = figureEventRegistry->getRegisteredDragOnFigures();
    for (auto &dragOnFigure : registeredDragOnFigures) {
        dragOnFigure->drag();
    }
}

Problem, z jakim się tutaj spotykamy to duplikacja kodu. Mamy dwie różne klasy typu EventRegistry, które przechowują obiekty klas, które są do siebie w pewien sposób podobne. Pytanie, które sobie zadałem brzmi: czy moglibyśmy mieć w takim razie jedną klasę, która przechowuje te elementy? Przecież nie będę chciał dodawać kolejnej klasy typu EventRegistry, kiedy będę chciał przeciągać kolejne elementy… Odpowiedź na to pytanie brzmi: TAK! Użyj std::variant! :)

W tej chwili mamy tylko jedną klasę EventRegistry, która wygląda tak:

class EventRegistry {

public:

    void registerOver(HoverableItem item);
    void unregisterOver(HoverableItem item);
    bool isOverRegistered(HoverableItem item);

    void registerDrag(DraggableItem item);
    void unregisterDrag(DraggableItem item);
    bool isDragRegistered(DraggableItem item);

    std::vector<DraggableItem> getRegisteredDrags();

private:

    std::vector<HoverableItem> registeredOvers;
    std::vector<DraggableItem> registeredDrags;

};

Tip: HoverableItem oraz DraggableItem to aliasy na typy:

typedef std::variant<
    std::shared_ptr<DynamicTile>,
    std::shared_ptr<ButtonTile>,
    std::shared_ptr<Figure>
> HoverableItem;

typedef std::variant<
    std::shared_ptr<DynamicTile>,
    std::shared_ptr<Figure>
> DraggableItem;

Kod odpowiedzialny za przesuwanie tilesów oraz figur uprościł się do postaci:

if (cursor.isMouseMoved()) {
    auto registeredDragOnTiles = eventRegistry->getRegisteredDrags();
    for (auto &dragOnItem : registeredDragOnTiles) {
        DragVisitator visitator(cursor);
        std::visit(visitator, dragOnItem);
    }
}

Teraz jest o wiele ładniej. Mamy jedną klasę, która przechowuje wszystkie “aktualnie ruszane” elementy. Nie potrzebujemy znać dokładnie tego obiektu, bo w zależności od tego, co przechowuje variant, uruchomi się inna metoda klasy DragVisitator:

void DragVisitator::operator()(std::shared_ptr<DynamicTile>& tile) {
    tile->drag(cursor.getPosition());
}

void DragVisitator::operator()(std::shared_ptr<Figure>& figure) {
    figure->drag(cursor.getPosition());
}

Bugfixing

Tak jak wyżej wspomniałem, do poprawy miałem kilka drobnych bugów. Poniżej wrzuciłem animacje przedstawiające te “najciekawsze” oraz działanie naszej aplikacji po poprawkach.


Bug 1 - Nakładanie się obiektów na siebie:

Bug1


Bugfix 1 - Nakładanie się obiektów na siebie:

Bugfix1


Bug 2 - Zmiana pozycji tilesa po fullscreenie podczas hovera:

Bug1


Bugfix 2 - Zmiana pozycji tilesa po fullscreenie podczas hovera:

Bugfix1

Nowa funkcjonalność - wykrywanie kolizji

Aby projekt nie stał w miejscu, postanowiłem, że każda nowa iteracja będzie niosła ze sobą conajmniej jedną nową funkcjonalność. Dzisiaj mam Wam do zaprezentowania bardzo prosty mechanizm wykrywania kolizji. Nie da się ukryć tego, że wszystkie elementy w grze mają postać prostokątną. Wykorzystałem ten fakt i swój system kolizji oparłem właśnie o ten kształt.

Głównym konceptem jest porównanie bieżącej odległości pomiędzy środkami dwóch prostokątów (zmienna diff) do odległości pomiędzy środkami w chwili, kiedy obydwa prostokąty “stykałyby się” ze sobą.

W chwili, kiedy obydwa prostokąty kolidują ze sobą, sprawdzane jest to, czy kolizja powstała w poziomie/pionie, a następnie wybierany jest kierunek kolizji (na podstawie pozycji obydwóch środków).

Implementacja tego rozwiązania wygląda następująco:

Collision::Collision(sf::Rect<float> first) {
    this->first = first;
}

Collision::Direction Collision::checkCollision(sf::Rect<float> second) {
    auto centerFirst = calcCenter(first);
    auto centerSecond = calcCenter(second);

    auto diff = centerFirst-centerSecond;

    bool isOutsideX = abs((long int)diff.x) >= first.width/2 + second.width/2;
    bool isOutsideY = abs((long int)diff.y) >= first.height/2 + second.height/2;
    if (isOutsideX || isOutsideY) {
        return Direction::None;
    }

    bool isHorizontalPlacement = abs((long int)diff.x) > abs((long int)diff.y);
    if (isHorizontalPlacement) {
        if (centerFirst.x > centerSecond.x) {
            return Direction::Left;
        }
        return Direction::Right;
    }

    if (centerFirst.y > centerSecond.y) {
        return Direction::Top;
    }
    return Direction::Bottom;
}

sf::Vector2f Collision::calcCenter(sf::Rect<float> rect) {
    return {rect.left + rect.width/2, rect.top + rect.height/2};
}

Całość wygląda całkiem prosto, dzięki czemu udało się napisać do tego bardzo ładne testy. Poniżej kilka przykładowych testów:

sf::Vector2f point = {200.0f, 200.0f};
float width = 100.0f;
float height = 100.0f;
sf::Rect<float> first(point.x, point.y, width, height);

TEST(CollisionTest, test_dont_collide_from_top) {
    sf::Rect<float> second(point.x, point.y-height-20, width, height);

    Collision collisionDetect(first);
    ASSERT_EQ(Collision::Direction::None, collisionDetect.checkCollision(second));
}

TEST(CollisionTest, test_collide_from_top_on_bound) {
    sf::Rect<float> second(point.x, point.y-height, width, height);

    Collision collisionDetect(first);
    ASSERT_EQ(Collision::Direction::None, collisionDetect.checkCollision(second));
}

TEST(CollisionTest, test_collide_from_top_inside) {
    sf::Rect<float> second(point.x, point.y-height+20, width, height);

    Collision collisionDetect(first);
    ASSERT_EQ(Collision::Direction::Top, collisionDetect.checkCollision(second));
}

TEST(CollisionTest, test_dont_collide_from_left) {
    sf::Rect<float> second(point.x-width-20, point.y, width, height);

    Collision collisionDetect(first);
    ASSERT_EQ(Collision::Direction::None, collisionDetect.checkCollision(second));
}

Bonus: MouseEnter i MouseLeave na kółka

Podczas tworzenia algorytmu kolizji odrobinę się zapędziłem i stworzyłem również funkcyjkę, która mówi nam, czy kursor znajduje się nad kołem. Niedługo w projekcie pojawią się elementy mające kształt koła, więc jedną rzecz będę już miał zrobioną :)

Oto implementacja:

bool Cursor::isOver(Circle circle) {
    auto mousePosition = getPosition();

    auto diff = mousePosition-circle.getPosition();
    auto diagonal = sqrt(diff.x*diff.x + diff.y*diff.y);

    return diagonal <= circle.getRadius();
}

Gdybym miał to w jednym zdaniu opisać, to powiedziałbym, że porównuję odległość pomiędzy kursorem a środkiem koła (diagonal) do długości promienia koła. Odległość pomiędzy kursorem a środkiem koła liczę ze wzoru na przekątną prosokąta, którego granice wyznaczają właśnie pozycja kursora oraz pozycja środka koła.

Do tego mamy również bardzo ładny zestaw testów:

TEST(CursorTest, test_is_not_over_circle) {
    Circle circle(sf::Vector2f(200, 200), 100);

    Cursor cursor;
    cursor.updatePosition(sf::Vector2f(99, 200));

    EXPECT_FALSE(cursor.isOver(circle));
}

TEST(CursorTest, test_is_over_circle_bound) {
    Circle circle(sf::Vector2f(200, 200), 100);

    Cursor cursor;
    cursor.updatePosition(sf::Vector2f(100, 200));

    EXPECT_TRUE(cursor.isOver(circle));
}

TEST(CursorTest, test_is_over_circle_inside) {
    Circle circle(sf::Vector2f(200, 200), 100);

    Cursor cursor;
    cursor.updatePosition(sf::Vector2f(101, 200));

    EXPECT_TRUE(cursor.isOver(circle));
}

Kolizje w akcji

System kolizji użyłem do tego, by zablokować możliwość nakładania figur na siebie. Gdybym tego nie zrobił, musiałbym zaimplementować również mechanizm kolejności podczas nakładania się figur - a to nie byłoby już takie proste. Sama klasa licząca kolizje na pewno przyda się w wielu miejscach w projekcie.

Poniżej filmik prezentujący aktualne możliwości systemu kolizji:

Kolizje w akcji

Testy - w końcu!

Ostatnim, o czym chciałem dzisiaj wspomnieć są testy. Aplikacja staje się coraz bardziej skomplikowana, przez co łatwo o błędy. Muszę w takim razie zadbać o to, aby w przyszłości pojawiało ich się coraz mniej (błędów oczywiście!), oraz by problemy raz rozwiązane nie wracały potem jak bumerang. W chwili obecnej mam przetestowaną prawie całą infrastrukturę, co napawa mnie sporą dawką optymizmu.

Usuwanie zależności z kodu

Podczas testowania klasy Cursor spotkałem się z drobnym problemem: jak dobrze przetestować taką metodę?:

bool Cursor::isOver(std::shared_ptr<Tile> tile) {
    auto mousePosition = sf::Mouse::getPosition(*(Cursor::window));
    int posX = mousePosition.x;
    int posY = mousePosition.y;

    return posX >= tile->getPosition().x && posY >= tile->getPosition().y &&
           posX <= tile->getPosition().x+tile->getSize().x &&
           posY <= tile->getPosition().y+tile->getSize().y;
}

Czy ja na prawdę potrzebuję tworzyć cały obiekt encji, aby móc przetestować tę metodę? Odpowiedź brzmi: nie! Jest to zupełnie niepotrzebna zależność, która komplikuje tylko sprawę. Problem ten rozwiązałem poprzez przekazywanie do metody jedynie tych wartości, które na prawdę są potrzebne, to znaczy: position oraz size sprawdzanego obiektu. To rozwiązanie dało mi dużą elastyczność. Obecnie nasza metoda wygląda tak:

bool Cursor::isOver(sf::Vector2f position, sf::Vector2u size) {
    auto mousePosition = getPosition();
    auto posX = mousePosition.x;
    auto posY = mousePosition.y;

    return posX >= position.x && posY >= position.y &&
           posX <= position.x+size.x &&
           posY <= position.y+size.y;
}

CI - pomijanie kodu rysującego

Podczas pisania testów klasy Cursor spotkałem się z jeszcze jednym, dosyć ważnym problemem: mimo, że lokalnie wszystkie testy mi przechodziły, to na CI pojawiał się błąd. System instalowany na travisie pozbawiony jest środowiska graficznego, zatem nie są tam dostępne funkcje rysujące oraz obsługujące teksturowanie. Mimo, że samego rysowania nie testowałem, to wysypywało się ładowanie tekstury w konstruktorze:

Cursor::Cursor() {
    this->texture = std::make_shared<sf::Texture>();
    this->texture->loadFromFile("resources/cursor.png");

    sprite = std::make_shared<sf::Sprite>(*(texture));

    float scale = 0.15;
    sprite->scale(scale, scale);
}

void Cursor::draw(std::shared_ptr<sf::RenderWindow> window) {
    updatePosition();
    window->draw(*sprite);
}

Rozwiązałem to, przez ładowanie tekstury przy pierwszym użyciu metody draw():

Cursor::Cursor() {
    sprite = std::make_unique<sf::Sprite>();

    float scale = 0.15;
    sprite->scale(scale, scale);
    sprite->setPosition(sf::Vector2f(0, 0));
}

void Cursor::draw(std::shared_ptr<sf::RenderWindow> window) {
    if (texture == nullptr) {
        texture = std::make_unique<sf::Texture>();
        texture->loadFromFile("resources/cursor.png");
        sprite->setTexture(*texture);
    }
    window->draw(*sprite);
}

Czego nie udało się zrobić?

No niestety, nie udało mi się skończyć implementacji zmian rozmiaru figur. Niby dużo nie zostało, ale ciągle natrafiam na nowe problemy, przez co idzie trochę wolniej.

Plany na następną iterację

Następną całą iterację chciałbym poświęcić figurom. Po pierwsze - chciałbym dokończyć mechanizm zmiany ich rozmiaru. Po drugie, chciałbym aby figury już dołączyły do puzelków, które można ściągać z górnej belki. Dodatkowo, będę chciał zacząć pisać testy dla zachowań obiektów domenowych - puzelków właśnie oraz figur. Zatem krótko w punktach:

  1. Implementacja funkcjonalności zmiany rozmiaru figur
  2. Ściąganie figur z górnej belki
  3. Testy obiektów domenowych

To tyle na dziś, do następnego razu! :)



Marcin Kukliński

Zawodowo backend developer, hobbystycznie pasjonat języka C++. Po godzinach poszerza swoją wiedzę na takie tematy jak teorii kompilacji oraz budowa formatów plików. Jego marzeniem jest stworzyć swój własny język programowania.

Pssst! Używamy Cookies. Poprzez używanie naszego serwisu zgadzasz się na odczytywanie i zapisywanie Cookies w swojej przeglądarce.