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

03.02.2010 - Marcin Milewski
TrudnośćTrudność

Wczytywanie jednostek z pliku

W artykule o tworzeniu przewijanej mapy zaimplementowaliśmy mapę wczytywaną z pliku. Oczywiste jest zatem, że również położenie jednostek powinno być wczytywane z pliku. Oto informacje dotyczące naszego formatu:

  • W jednej linii może znajdować się: informacja o jednostce, komentarz, nic (pusta linia).
  • Komentarz to linia zaczynająca się od znaku $ # $.
  • Informacja o jednostce składa się z trzech elementów: typ jednostki, położenie na osi OX, położenie na osi OY.
  • Plik zawiera informację o początkowym położeniu gracza.
  • Dowolna permutacja linii w pliku nie zmienia znaczenia pliku - to znaczy, że kolejność linii nie ma znaczenia.
  • Jeżeli pozycja początkowa jednostki (w szczególności gracza) nie jest na polu typu FT::None, to zachowanie gry jest niezdefiniowane.
  • Dane w pliku powinny być poprawne - dla niepoprawnych danych zachowanie jest niezdefiniowane.

Patrząc na powyższy opis zadajemy sobie pytanie: dlaczego wprowadzać zachowanie niezdefiniowane, jeżeli można taką sytuację obsłużyć? Odpowiedź: tak jest prościej! Pamiętajmy, że naszym celem jest stworzenie gry, więc należy tworzyć kod, który jest potrzebny do osiągnięcia celu.

Przyjrzyjmy się przykładowemu plikowi z opisem rozmieszczenia jednostek na mapie:

1
2
3
4
5
6
7
8
9
10
# położenie początkowe bohatera
player 9 5
 
# pozostałe obiekty
mush 5 1
mush 2 1
mush 4 1
 
floret 8 12
  

Dzięki wspomnianym założeniom, kod wczytujący dane z takiego pliku jest bardzo przejrzysty. Dane dotyczące każdej jednostki będziemy przechowywać w strukturze LevelEntityData. Jej deklarację umieszczamy w pliku Level.h. Oto ona:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct LevelEntityData {
    LevelEntityData()
        :  name("[unknown]"), x(-1), y(-1) {   }
 
    LevelEntityData(const std::string& name, double x, double y)
        :  name(name), x(x), y(y) {   }
 
    bool operator() (const LevelEntityData& a, 
                     const LevelEntityData& b) {
        return a.x < b.x;
    }
 
    std::string name;  // nazwa jednostki
    double x;          // położenie na osi odciętych
    double y;          // położenie na osi rzędnych
};
  

Wczytywaniem pliku z opisem jednostek zajmie się metoda LoadEntitiesFromFile klasy Level. Zauważmy sortowanie występujące w przedostatniej linijce. Dzięki niemu mamy pewność, że obiekty w m_entities_to_create (typu std::list<LevelEntityData>) będą uporządkowane rosnąco po współrzędnej x. Własność tę będziemy wykorzystywać dodając kolejne jednostki do rozgrywki. Do sortowania został wykorzystany obiekt funkcyjny. Jest to typowa metoda wykorzystywana m.in. do sortowania zawartości kontenerów w języku C++. Istnieje jednak sposób, który powinien zainteresować osoby chcące poznać zaawansowane możliwości tego języka - boost::lambda.

Pokaż/ukryj kod
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
26
27
28
29
30
31
32
33
34
35
36
void Level::LoadEntitiesFromFile(const std::string& filename) {
    std::ifstream file(filename.c_str());
    if (!file) {
        std::cerr << "Nie udało się załadować pliku " 
                  << filename << "\n";
        return;
    }
 
    // wczytaj linia po linii
    const int buffer_size = 1024;
    char buffer[buffer_size];
    while (file) {
        file.getline(buffer, buffer_size);
        std::string line(buffer);
        if (line.length() < 5 || line.at(0) == '#')
            continue;
        std::istringstream iss(line);
        LevelEntityData data;
        iss >> data.name;
        iss >> data.x;
        iss >> data.y;
        if (data.name == "player") {
            m_player_data = data;
        } else {
            m_entities_to_create.push_back(data);
        }
 
        std::cout << "[LoadEntityFromFile] " << data.name 
                  << ", " << data.x << ", " << data.y 
                  << std::endl;
    }
 
    // posortuj wczytane rekordy
    m_entities_to_create.sort(LevelEntityData());
}
  

Do klasy Level dodajemy również metody, które pozwolą wydobyć wczytane rekordu oraz jedną dodatkową, która dla wskazanego pola zwróci prostokąt go otaczający (czyli jego AABB). Oto definicja tej metody (plik Level.cpp):

1
2
3
4
5
6
7
8
9
10
Aabb Level::GetFieldAabb(size_t x, size_t y) const {
    RendererPtr renderer = Engine::Get().Renderer();
    const size_t v_tiles_count 
                 = renderer->GetVerticalTilesOnScreenCount();
    // odbij y w pionie (y=0 będzie na dole)
    y = v_tiles_count - y;  
    Aabb box = Aabb(x, y-1, x + 1, y);
    return box;
}
  

Po wykonaniu wszystkich powyższych kroków otrzymujemy następujący plik Level.h:

Pokaż/ukryj kod
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#ifndef __LEVEL_H__
#define __LEVEL_H__
 
#include <boost/shared_ptr.hpp>
#include <string>
#include <vector>
#include <list>
#include "Aabb.h"
#include "Types.h"
 
// Dane dotyczące jednostki wczytane np. z pliku. Na ich podstawie
// zostanie w grze stworzona odpowiednia jednostka
struct LevelEntityData {
    LevelEntityData()
        :  name("[unknown]"), x(-1), y(-1) {   }
 
    LevelEntityData(const std::string& name, 
                    double x, double y)
        :  name(name), x(x), y(y) {   }
 
    bool operator() (const LevelEntityData& a, 
                    const LevelEntityData& b) {
        return a.x < b.x;
    }
 
    std::string name;  // nazwa jednostki
    double x;          // położenie na osi odciętych
    double y;          // położenie na osi rzędnych
};
 
 
class Level {
public:
    explicit Level();
 
    void LoadFromFile(const std::string& filename);
    void LoadEntitiesFromFile(const std::string& filename);
 
    std::list<LevelEntityData> 
        GetAllEntitiesToCreate() const  { 
            return m_entities_to_create; 
        }
    LevelEntityData GetPlayerData() const { 
        return m_player_data; 
    }
 
    FT::FieldType Field(size_t x, size_t y) const;
    size_t GetWidth() const   { return m_width; }
    size_t GetHeight() const  { return m_height; }
    Aabb GetFieldAabb(size_t x, size_t y) const;
    
private:
    size_t m_width;
    size_t m_height;
    std::vector<std::vector<FT::FieldType> > m_data;
    std::list<LevelEntityData> m_entities_to_create;
    LevelEntityData m_player_data;
 
};
typedef boost::shared_ptr<Level> LevelPtr;
 
#endif
  

Tworzenie jednostek - fabryka obiektów

Do tworzenia obiektów wykorzystamy tzw. fabrykę obiektów. Jest to jeden ze wzorców projektowych, o którym można znaleźć sporo informacji w Sieci. W kodzie występuje typ EntityPtr, którego jeszcze nie zdefiniowaliśmy, ale możemy łatwo się domyślić, za co jest odpowiedzialny. Nasza fabryka zwiera dwie podstawowe metody. Pierwsza z nich tworzy jednostkę na podstawie ciągu znaków (np. tego wczytanego z pliku), a druga na podstawie typu. Oto implementacja klasy EntityFactory:

Pokaż/ukryj kod
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include "Engine.h"
#include "MushEntity.h"
#include "PlayerBulletEntity.h"
#include "EntityFactory.h"
 
EntityFactory::EntityFactory() {
}
 
SpritePtr GetSpriteByName(const std::string& name) {
    return SpritePtr(new Sprite(
                Engine::Get().SpriteConfig()->Get(name)));
}
 
EntityPtr EntityFactory::CreateEntity(const std::string& name, 
                                      double x, double y) {
    if (name == "mush") {
        return CreateEntity(ET::Mush, x, y);
    } else if (name == "player_bullet") {
        return CreateEntity(ET::PlayerBullet, x, y);
    }
    std::cerr << "fabryka nie umie stworzyć żądanej jednostki: "
              << name << std::endl;
    return EntityPtr();
}
 
EntityPtr EntityFactory::CreateEntity(ET::EntityType type, 
                                      double x, double y) {
    const double eps = 0.0001;
    x += eps;  y += eps;
 
    EntityPtr ptr;
    if(type==ET::Mush) {
        ptr.reset(new MushEntity(x, y));
        ptr->SetSprites(GetSpriteByName("mush_left"), 
                        GetSpriteByName("mush_right"), 
                        GetSpriteByName("mush_stop") );
    } else if (type == ET::PlayerBullet) {
        ptr.reset(new PlayerBulletEntity(x, y));
        SpritePtr bullet = GetSpriteByName("player_bullet"); 
        ptr->SetSprites(bullet, bullet, bullet);
    }
 
    if (!ptr) {
        std::cerr << "fabryka nie umie stworzyć żądanej jednostki: " 
                  << type << ", " << x << ", " << y << std::endl;
    }
    return ptr;
}
  

Zauważmy, że do pozycji, na której powinna pojawić się jednostka dodajemy małą wartość dodatnią (epsilon). Dzieje się tak dlatego, że obiekt stworzony na pozycji (x, y) może od razu kolidować z jakimś fragmentem mapy. Jest niedopuszczalne położenie początkowe, gdyż nie ma możliwości cofnięcia obiektu na ostatnią "dobrą" (bez kolizji) pozycję. Należy zatem odrobinę przesunąć obiekt. Warto zauważyć, że dodając do gry obiekt, który ma AABB o rozmiarach 1x1 (lub większych) można spodziewać się kłopotów w postaci niezdefiniowanego zachowania się gry. Dlatego należy unikać takich obiektów lub tworzyć je w takim miejscu na planszy, aby początkowo nie kolidowały z mapą.

Aby mieć dostęp do fabryki z każdego miejsca, dodajemy ją do klasy Engine. Kod pliku Engine.h przedstawia się teraz następująco:

Pokaż/ukryj kod
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
26
27
28
29
30
31
32
33
34
#ifndef ENGINE_H_
#define ENGINE_H_
#include "SpriteConfig.h"
#include "Renderer.h"
#include "EntityFactory.h"
#include "Sound.h"
 
class Engine {
public:
   static Engine& Get() {
      static Engine engine;
      return engine;
   }
 
   void Load() {
      m_sprite_config.reset(new SpriteConfig::SpriteConfig());
      m_renderer.reset(new Renderer::Renderer());
      m_entity_factory.reset(new EntityFactory::EntityFactory());
      m_sound.reset(new Sound::Sound());
   }
 
   EntityFactoryPtr EntityFactory() { return m_entity_factory; }
   SpriteConfigPtr SpriteConfig()   { return m_sprite_config; }
   RendererPtr Renderer()           { return m_renderer; }
   SoundPtr Sound() { return m_sound; }
 
private:
   EntityFactoryPtr m_entity_factory;
   SpriteConfigPtr m_sprite_config;
   RendererPtr m_renderer;
   SoundPtr m_sound;
};
#endif
  

Dodawanie i usuwanie jednostek z gry

Wiemy już jak wczytywać opisy jednostek z pliku oraz jak stworzyć żądaną jednostkę. W tym punkcie pokażemy jak należy dodawać jednostki do gry. Najbardziej oczywisty sposób to dodać wszystkie jednostki przy wczytywaniu poziomu i więcej się tym nie zajmować. Oczywiście jest to proste rozwiązanie i prędkość jego działania dla rozsądnych co do wielkości map byłaby zadowalająca. Jeżeli jednak założymy, że gracz co jakiś czas ginie i zaczyna poziom od początku, to nasuwa się pytanie, czy nie byłoby warto tworzyć tylko tych jednostek, które są faktycznie potrzebne?

Podzielmy więc grę na kawałki o pewnej ustalonej szerokości. Gdy gracz dojdzie do kolejnego elementu, to dodamy wszystkie jednostki, które do niego należą. Jeżeli jednak w którymś kawałku będzie bardzo dużo jednostek, to gra na moment się , a tego zdecydowanie nie chcemy. Jednym ze sposobów na uratowanie sytuacji jest dodawnie oraz usuwanie obiektów w sposób ciągły, tzn. na bieżąco. Uznamy, że jednostkę należy dodać, jeżeli będzie po prawej stronie gracza w odległości mniejszej niż jeden ekran. Analogicznie, jeżeli będzie po lewej stronie gracza dalej niż jeden ekran, to należy ją usunąć (przypomnijmy, że gracz nie może przesuwać planszy w lewo). Dodając obiekty wykorzystujemy fakt, że lista jednostek do stworzenia jest posortowana po współrzędnej x jednostek oraz, że obiekty są dostatecznie małe - inaczej moment, w którym przestajemy tworzyć obiekty miałby duże znaczenie.

Czuwaniem nad tymi zmianami będzie zajmowała się klasa Game. Jednostki będziemy przechowywać w wektorze m_entities (std::vector). Natomiast w metodzie Init pobieramy z obiektu m_level opisy jednostek, które będziemy dodawać w odpowiednim momencie do gry.

1
2
3
4
5
    // ładowanie poziomu i sprite'ów planszy
    m_level.reset(new Level());
    m_level->LoadFromFile("data/1.lvl");
    m_level->LoadEntitiesFromFile("data/1.ents");
    m_entities_to_create = m_level->GetAllEntitiesToCreate();

Dodawaniem i usuwanie jednostek zajmuje się metoda SeepAndAddEntities, która działa według opisanego schematu.

Pokaż/ukryj kod
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
void Game::SeepAndAddEntities(double dt) {
    // oznacz jednostki, które są sporo za lewą krawędzią ekranu jako martwe
    const double distance_of_deletion = Engine::Get().Renderer()->GetHorizontalTilesOnScreenCount();
    for (std::vector<EntityPtr>::iterator it = m_entities.begin(); 
         it != m_entities.end(); 
         ++it) {
        EntityPtr e = *it;
        if (e->GetX() + distance_of_deletion < m_player->GetX()) {
            e->SetIsDead(true);
        }
    }
 
    // usuń martwe jednostki - O(n^2). Można je usunąć w O(n), ale trzeba napisać 
    // funktor - google(erase remove idiom).
    for (size_t i = 0; i < m_entities.size(); ++i) {
        if (m_entities.at(i)->IsDead()) {
            for (size_t c = i; c < m_entities.size() - 1; ++c) {
                m_entities.at(c) = m_entities.at(c + 1);
            }
            m_entities.resize(m_entities.size() - 1);
        }
    }
 
    // dodaj kolejne jednostki z listy do gry
    const double distance_of_creation = 
                      Engine::Get().Renderer()->
                            GetHorizontalTilesOnScreenCount();
    while (m_entities_to_create.empty() == false) {
        if (m_entities_to_create.front().x 
            - m_player->GetX() 
            < distance_of_creation) {
            LevelEntityData data = m_entities_to_create.front();
            m_entities_to_create.pop_front();
            EntityPtr e = Engine::Get().EntityFactory()->
                     CreateEntity(data.name, data.x, data.y);
            m_entities.push_back(e);
        } else {
            break;
        }
    }
}
  

Wykorzystana technika dodawania i usuwania elementów do gry jest warta zapamiętania z co najmniej trzech powodów:

  1. Można ją wyczerpująco opisać w kilku zdaniach - jest łatwa do zrozumienia.
  2. Jest prosta w implementacji - istnieje wiele ogólnych technik rozwiązujących podobne problemy, które sprawdziłyby się i w tym przypadku. Tylko kto zaimplementowałby je w 15 minut? Kto byłby przekonanych o poprawności tej implementacji?
  3. Jest dostosowana do potrzeb - zauważmy, że nasze rozwiązanie w ogóle nie rozważa osi OY - nie jest to potrzebne, gdyż plansza może przewijać się wyłącznie w poziomie.

Pamiętajmy, aby na każdy problem spojrzeć najpierw ogólnie ("czy coś podobnego już rozwiązywałem?"), a następnie przyjrzeć mu się z bliska - czy zachodzą jakieś szczególne warunki (np. obiektów będzie mało, będą to jednostki tylko kilku typów, itp.) i można zastosować algorytm gorszej klasy, ale prostszy w implementacji (np. zamiast implementować skomplikowane struktury drzewiaste, można skorzystać ze zwykłego wektora czy listy).

0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com