Na studiach spotkasz się z wieloma typami zajęć. Są laboratoria, są ćwiczenia i wiele innych. Spośród wszystkich najbardziej lubię projekty. Mam wyznaczone zadanie, które muszę wykonać do określonego dnia. I nikt mnie nie zmusza do tego aby użyć konkretnego sposobu rozwiązania problemu. Kłopotem nie jest także czas. Co prawda istnieją odgórnie wyznaczone terminy mówiące o tym, do kiedy należy wykonać projekt (np.: za miesiąc). Lecz to jak rozłożę sobie pracę na poszczególne dni zależy całkowicie ode mnie. Uwielbiam wolność tkwiącą w tego typu zajęciach.

W tym semestrze mam jeden projekt natury stricte programistycznej. Przedmiot nazywa się „Programowanie w języku C2” (czyli C++). Zadanie jest następujące: stworzyć program, który zasymuluje pożar (lasu). Symulacja ma zostać przeprowadzona przy pomocy algorytmu automatu komórkowego.

Założenia projektowe

zalozenia_projektowe

Temat jest postawiony dość ogólnie. W moim projekcie będę chciał zasymulować pożar lasu. Zanim zabrałem się za pracę, musiałem ustalić, z jakich bibliotek będę korzystał.

W kwestii biblioteki graficznej istnieje wiele opcji do wyboru. Jest Allegro, SFML, SDL2 i wiele, naprawdę wiele innych. Allegro odrzuciłem na starcie, gdyż nieco zraziłem się do dziwnych rozwiązań zastosowanych w tej bibliotece. Na placu boju pozostały SFML i SDL2. SFML bardziej nadaje się pod C++, gdyż jest obiektowy. Jednakże wybór padł na SDL, gdyż osoba, z którą pracuję nad projektem (zespoły są dwuosobowe) zna właśnie SDL.

logo sdl

Jestem miłośnikiem Linuksa. Sam używam go na co dzień, Windowsa odpalając tylko do jednej gry (Gwint, Wiedźmińska Gra Karciana). Z tego też powodu chcę, aby aplikacja była wieloplatformowa, czyli aby działała bez problemu zarówno pod Linuksem jak i pod Windowsem. SDL załatwia ten problem z punktu widzenia kodu aplikacji.

Chciałbym, aby aplikacja posiadała okienkowy interfejs użytkownika (GUI). Służyłby by on do konfigurowania wielu różnych parametrów symulacji. Interfejs okienkowy będzie pozwalał na:

  • Wybór konkretnego narzędzia i rodzaju „obiektu”, które będzie rysował. (Narzędzia: Spray/ołówek/gumka. Dostępne rodzaje obiektów: drzewo/pożar/spalone drzewo).
  • uruchomienie i zatrzymanie symulacji w dowolnym momencie.
  • wpływanie na szybkość symulacji (suwak).
  • zmianę obszaru symulacji, zarówno fizycznego (zmiana rozmiaru okna) jak i logicznego (mniejsze/większe piksele).
  • (Opcjonalne) odczyt/zapis stanu symulacji do pliku

Interfejs okienkowy będzie wykonany w WxWidgets. W pierwszym etapie GUI będzie oddzielną aplikacją. W kolejnym kroku zostanie ono zintegrowane w jedną aplikację z programem głównym napisanym w SDL-u.

Dlaczego nie zrobię GUI od razu w SDL? Powodów jest wiele. Po pierwsze, bardziej zaawansowane kontrolki, takie jak slidery, będzie ciężko oprogramować w bibliotece SDL. Po drugie, dzięki WxWidgets aplikacja będzie dostosowana do motywu systemu, gdyż ten framework korzysta z natywnych kontrolek systemowych.

Projekt szablonu klas

Pora przejść do następnego etapu. Założenia zostały już ustanowione. Teraz wspólnie z tobą, czytelniku zajmiemy się ich analizą i realizacją. Zastanowimy się nad wstępnym szablonem klas. Postaramy się tak je zaplanować, aby maksymalnie ułatwiły nam zaimplementowanie finalnego algorytmu automatu komórkowego. Ponadto, dodatkowym celem jest ukrycie „wstrętnego SDL-owego C” za przyjemną dla oka składnią C++.

Drzewo

Co będzie najbardziej podstawowym, najmniejszym obiektem w naszej symulacji? Oczywiście drzewo. Można także powiedzieć ogólniej – obiekt, który może się palić. Jakie właściwości będą z nim powiązane? Przede wszystkim – stan. Istnieją trzy możliwości:

  • Obiekt po prostu istnieje. Lasek sobie rośnie w złotych promieniach Słońca i nic specjalnego się nie dzieje.  (EXIST).
  • Pożar trawi drzewo.(FIRE)
  • Żywioł pokonał obiekt. (BURN)

Stan będzie zapisany w formie enuma. Jego definicja znajduje się poniżej.

12
13
14
15
16
enum PType {
    EXIST,
    FIRE,
    BURN
};

Natomiast definicja drzewa wygląda tak:

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
class Tree {
    public:
    Tree() {
        type = EXIST;
    }
    Tree(PType status) {
        this->type = status;
    }
    PType getType() {return this->type;}
    Tree operator++(int) {
        Tree temp = *this;
        switch(this->type) {
            case EXIST:
                this->type = FIRE;
            break;
            case FIRE:
                this->type = BURN;
            break;
            case BURN:
            break;
        }
        return temp;
    }
    private:
    PType type;
};

Skoro w drzewie przechowujemy tylko typ, to skąd będzie wiadomo na jakich współrzędnych się ono znajduje? To jest dobry temat do dalszych rozważań. Jak rozwiążemy ten problem?

Pozycją obiektów na mapie będzie zajmowała się specjalna klasa – ForestMap. Współrzędne moglibyśmy przechowywać w tablicy dwuwymiarowej. To podejście niesie ze sobą pewne wady. Po pierwsze – musielibyśmy poświęcić dużo czasu na zabawę z alokowaniem pamięci dla dwuwymiarowej tablicy. Po drugie – sporą część akcji musielibyśmy przeciążać sami. Istnieje prostsze rozwiązanie tego problemu – kontener domyślnie obecny w C++ – std::map.

Ale zaraz zaraz, nie będzie nam pasowała jedna rzecz. Kontener std::map przechowuje pary klucz‑wartość. W naszym wypadku kluczem będą współrzędne, a tych jest dwie: x i y. Nie możemy stworzyć mapy, która będzie miała dwa klucze. Jakie sobie z tym poradzić? Stworzymy kolejną klasę – Coordinates.

Coordinates

17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Coordinates {
    public:
    Coordinates(unsigned int x,unsigned int y) {
        this->x = x;
        this->y = y;
    }
    Coordinates(unsigned int x) {
        this->x = x;
        this->y = 0;
    }
    unsigned int x;
    unsigned int y;
    bool operator< (const Coordinates& rhs) const {
    return (this->x<rhs.x) || ((this->x==rhs.x) && (this->y < rhs.y));
    }
};

Powyżej znajduje się definicja klasy Coordinates. Nie ma w niej nic niezwykłego. Mamy dwa konstruktory. Jeden, który przyjmuje wartości x i y, oraz drugi, który przyjmuje jedynie x’a. O ile obecność pierwszego z nich jest oczywista, o tyle może nas zastanawiać potrzeba stosowania drugiego konstruktora. Po co nam to? Niedługo się dowiesz. W tej chwili mogę uchylić rąbek tajemnicy mówiący o tym, że ma to związek z przeciążaniem operatora [].

Intrygująca jest także obecność przeciążenia operatora mniejszości. Nie będziemy używali tego jawnie. Musieliśmy stworzyć takie przeciążenie, gdyż tego wymagał kontener std::map. Elementy w kontenerze są układane tak, aby wartości były posortowane wg kluczy. Aby std::map mógł wykonać tę operację, musi wiedzieć jak wykonać algorytm sortowania, który element jest mniejszy, a który większy. Dla prostych typów, takich jak int jest to oczywiste. Dla samodzielnie stworzonej klasy taki operator musimy przeciążyć samodzielnie.

ForestMap

Klasa ForestMap będzie jedną z najbardziej skomplikowanych klas na tym etapie projektu. Będzie zawierała najwięcej metod. Podstawowym zadaniem będzie oczywiście przechowywanie współrzędnych wszystkich obiektów. Ale nie tylko. Klasa musi udostępnić metodę drawAll, dzięki której SDL będzie mógł narysować wszystkie punkty. Musimy udostępnić metody add i del, które będą służyły do dodawania i usuwania punktów. No i najważniejsze – wykonamy przeciążenie operatora [][]. Po co nam to potrzebne? Abyśmy mogli łatwo sprawdzić stan punktu np.: w ten sposób:

Tree* drzewo = map[4][3]; // pobierze obiekt drzewa znajdujący się na współrzędnych (4,3)

Spójrz na kod źródłowy klasy ForestMap w obecnej postaci.

75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
class ForestMap {
    public:
    ForestMap() {
        fullMap = make_shared<map<Coordinates,Tree>>();
    }
    SingleCell operator[](int x) {
        return SingleCell(x,fullMap);
    }
    void add(int x,int y,PType status) {
        Tree new_tree(status);
        (*fullMap)[Coordinates(x,y)] = new_tree;
    }
    void drawAll(function<void(int,int,PType)> func) {
        map<Coordinates,Tree>& mp = *fullMap.get();
        map<Coordinates,Tree>::iterator it;
        for(it = mp.begin();it!=mp.end();it++) {
            func(it->first.x,it->first.y,it->second.getType());
        }
    }
    private:
    shared_ptr<map<Coordinates,Tree>> fullMap;
};

Zaczniemy nieco od końca. W linijce 95 deklarujemy kontener map, w którym będziemy przechowywać obiekty Tree wg klucza Coordinates. Powstaje pytanie, dlaczego jest to wskaźnik typu shared_ptr, a nie zwykła właściwość klasy? Zrobiliśmy tak, ponieważ mapa będzie często przekazywana do innych funkcji/metod, które będą wyciągały z niej pewne wartości. Przekazywanie mapy zawierającej kilka tysięcy punktów przez wartość będzie mocno nieefektywne. Nie chcemy bawić się staromodnymi „raw pointerami” z C. Jedynym rozwiązaniem pozostaje użycie inteligentnych wskaźników.

Omówmy teraz metodę drawAll, której definicja zaczyna się w linijce 87. Wydaje się ona dosyć skomplikowana, gdyż przekazujemy jej wskaźnik na funkcję. Pełna definicja funkcji, której wskaźnik przekazujemy mogłaby wyglądać tak:

void draw(int x,int y,Ptype d)

W tej chwili wystarczy abyśmy wiedzieli, że draw rysuje punkt o danym typie na ekranie. Zadanie drawAll w takim wypadku sprowadza się do wywołania funkcji draw dla każdego punktu znajdującego się w mapie.

Spójrzmy na metodę add. Jako argumenty przyjmuje ona współrzędne oraz status drzewa. A jak działa? Bardzo prosto. W linijce 84 tworzymy zwykłą zmienną Tree. Natomiast w kolejnej dodajemy ją do mapy.

SingleCell

Zajmijmy się przeciążeniem operatora []. Jak pamiętamy, operator[] ForestMap zwraca obiekt SingleCell, a jako argument przyjmuje jedynie jedną współrzędną – x. SingleCell jest „nadmiarową” klasą, która umożliwi nam przeciążenie operatora tablicy dwuwymiarowej [][] dla całego ForestMap. SingleCell będzie zwracał obiekt konkretnego drzewa. Aby to zrobić, musi otrzymać wskaźnik na całą mapę. Przeanalizujmy to.

Klasa pomocnicza SingleCell wygląda następująco:

60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class SingleCell {
    public:
    SingleCell(int x,shared_ptr<map<Coordinates,Tree>> mp) {
        fullmap = mp;
        this->x = x;
    }
    Tree* operator[](int y) {
        if((*fullmap).find(Coordinates(x,y))==(*fullmap).end()) return nullptr;
        Tree* toReturn = &(*fullmap)[Coordinates(x,y)];
        return toReturn;
    }
    private:
    int x;
    shared_ptr<map<Coordinates,Tree>> fullmap;
};

Konstruktor omówiliśmy wcześniej. W kolejnych linijkach zauważamy przeciążenie operatora []. Zwraca ono obiekt który chcieliśmy uzyskać. Jeśli na danych współrzędnych nie istnieje drzewo ani pożar ani spalone drzewo, to zwracamy nullptr. W przeciwnym razie zwracamy wskaźnik na Tree.

 

To wszystko

Ujawniłem wszystko, co planowałem w dzisiejszym wpisie. Nie mamy jeszcze programu, który by się uruchamiał. Posiadamy natomiast zaczątek – coś, co może wyewoluować w pełnoprawną aplikację. Ten kod może się oczywiście zmieniać, gdyż wpisy tworzę równolegle do prac nad projektem.

Co byś zmienił? Może masz lepszy pomysł na rozwiązanie problemów z którymi się borykałem? Jeśli tak, podziel się nim w komentarzu.

Kod źródłowy projektu znajduje się w tym miejscu. (GitHub).

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *