Studia/eri/cwiczenia/projekt/main2.cpp

#include <iostream>
#include <fstream> // do wczytywania pliku
#include <algorithm> // do usuwania ostatniego wyszukanego elementu z listy otwartej (erase)
#include <vector> // do dynamicznych list (lista w które możemy zmieniać, dodawać/usuwać elementy)
#include <math.h> // do sqrt i pow



using namespace std;




class Punkt {
private:
    int sciezka; // do wyznaczenia ścieżki
    float funkcjaG = 0; //
    float funkcjaF = 0; //
    int x; //współrzędna x na mapie
    int y; //współrzędna y na mapie
    Punkt* rodzic = NULL; // rodzic punktu, na początku null ponieważ nie wiemy jaki jest rodzic
public:
    void setX(int x) { //ustawia wartość x
        this->x = x;
    }
    void setY(int y) { //ustawia wartość y
        this->y = y;
    }
    void setSciezka(int sciezka) { //ustawia wartosc ścieżki
        this->sciezka = sciezka;
    }
    void setFunkcjaF(int funkcjaF) { //ustawia wartość funkcji F
        this->funkcjaF = funkcjaF;
    }
    void setRodzic(Punkt* rodzic) { //ustawia wartość rodzica
        this->rodzic = rodzic;
    }

    int getX() { //zwraca wartość x
        return this->x;
    }
    int getY() { //zwraca wartość y
        return this->y;
    }
    int getSciezka() { //zwraca wartość ścieżki
        return this->sciezka;
    }
    float getFunkcjaF() { //zwraca wartość funkcji F
        return this->funkcjaF;
    }
    float getFunkcjaG() { //zwraca wartość funkcji G
        return this->funkcjaG;
    }
    Punkt* getRodzic() { //zwraca wartość rodzica
        return this->rodzic;
    }

    //oblicza koszt dotarcia i przypisuje go do obiektu, wykorzystana przy wysuzkiwaniu sąsiednich punktów
    //ustawia wartość funkcji f i g, oblicza wartość funkcji h (heurystyki)
    void ObliczanieFunkcji(Punkt* celPunkt) {
        float funkcjaH = sqrt(pow((this->x - celPunkt->x), 2) + pow((this->y - celPunkt->y), 2));
        this->funkcjaG = this->rodzic->funkcjaG + 1;
        this->funkcjaF = funkcjaH + this -> funkcjaG;
    }
      //sprawdza czy dotarto do końca (destination)
    bool dotarcieDoCelu(Punkt* destination) {
        if (this == destination) { //jeśli obecny punkt jest taki sam jak końcowy
            // zaznacza ściężkę mapie za pomocą jedynek, dopóki rodzic nie jest pusty (null)
            while (destination->getRodzic()) { //dopóki mamy rodzica while wywołuje się
                destination->setSciezka(7); //ustawia ścieżkę na 1
                destination = destination->getRodzic(); //pobiera rodzica końca //rodzic punktu końcowego staje się punktem końcowym, wraca po rodzicach ustawiając na 1 wartość punktów, wyznaczając tym samym ścieżkę
            }
            return true;
        }
        return false;
    }

    //sprawdza czy obiekt znajduje się w liście (wektorze) do sprawdzania listy otwartej i zamkniętej
    bool sprawdzenieListy(vector<Punkt*> lista) {
        for (auto elementListy : lista) //auto przeiterowuje się przez listę, typ iteratora ustawia się sam
            if (elementListy == this) return true;
        return false;
    }




};

int wys = 20, szer = 20;
//wektor rozmiaru szerokości, zawiera elementy wartości vector<Punkt>(wys)
vector<vector<Punkt>> siatka(szer, vector<Punkt>(wys));
// wektor przechowujący wskaźniki na klasę Punkt
vector<Punkt*> Lista_Otwarta; //lista otwarta
vector<Punkt*> Lista_Zamknieta; //lista zamknięta



//funckja porównuje wartości funkcji F i jeśli znajdzie namniejszy to zamienia go, jeśli mamy kilka takich samych wartości funkcji F to  brany jest ostatni element (ponieważ jako ostatni "przeszedł" przez pętle for)
Punkt* najmniejszaFunkcjaF() {
    Punkt* wartoscMinimum = Lista_Otwarta[0];
    for (auto elementListy : Lista_Otwarta)
        if (elementListy->getFunkcjaF() <= wartoscMinimum->getFunkcjaF()) wartoscMinimum = elementListy;
    return wartoscMinimum;
}



vector<Punkt*> znajdzSasiednie(Punkt* sprawdzanyPunkt) { //Wyznacza sąsiadów sprawdzanego punktu //sprawdzanyPunkt - punkt w którym aktualnie się znajdujemy
    // wektor wskaznikow na klasę Punkt o wielkości 4 z default wartościami null
    vector<Punkt*> sasiednie(4, NULL);

    cout << "sasiednie do  [" << sprawdzanyPunkt->getX() << "," << sprawdzanyPunkt->getY() << "]:" << endl;

    // znajduje sasiednie punktu jeżeli ich współrzędne nie są większe niż mapa
    ///////////////////////////////////////////////////////////////////////////
    /// kolejność indeksów w sasiednie[] odpowiada hierarchii ruchu
    // dół
    if (sprawdzanyPunkt->getY() + 1 < wys) { // sprawdza czy sąsiad nie wypada poza mapę na dole
        cout << "z dolu [" << sprawdzanyPunkt->getX() << "," << sprawdzanyPunkt->getY() + 1 << "]" << endl;
        sasiednie[0] = &siatka[sprawdzanyPunkt->getX()][sprawdzanyPunkt->getY() + 1]; //nadpisujemy wartość NULL adresem punktu na siatce o współrzędnych x i y
    }
    // lewo
    if (sprawdzanyPunkt->getX() - 1 >= 0){ // sprawdza czy sąsiad nie wypada poza mapę na lewo
        cout << "z lewej [" << sprawdzanyPunkt->getX() - 1 << "," << sprawdzanyPunkt->getY() << "]" << endl;
        sasiednie[1] = &siatka[sprawdzanyPunkt->getX() - 1][sprawdzanyPunkt->getY()];
    }
    // góra
    if (sprawdzanyPunkt->getY() - 1 >= 0){ // sprawdza czy sąsiad nie wypada poza mapę na górze
        cout << "z gory [" << sprawdzanyPunkt->getX() << "," << sprawdzanyPunkt->getY() -1 << "]" << endl;
        sasiednie[2] = &siatka[sprawdzanyPunkt->getX()][sprawdzanyPunkt->getY() - 1];
    }
    // prawo
    if (sprawdzanyPunkt->getX() + 1 < szer){ // sprawdza czy sąsiad nie wypada poza mapę na prawo
        cout << "z prawej [" << sprawdzanyPunkt->getX() + 1 << "," << sprawdzanyPunkt->getY() << "]" << endl;
        sasiednie[3] = &siatka[sprawdzanyPunkt->getX() + 1][sprawdzanyPunkt->getY()];
    }

    return sasiednie;
}
bool a_star(int xPoczatek, int yPoczatek, int xKoniec, int yKoniec) {
    Punkt* poczatek = &siatka[xPoczatek][yPoczatek];
    Punkt* koniec = &siatka[xKoniec][yKoniec];

    Lista_Otwarta.push_back(poczatek); //punkt początkowy trafia na listę otwartą
    while (Lista_Otwarta.size() > 0) { //dopóki lista otwarta zawiera choć jeden element //jeśli np. punkt cel będzie odgrodzony scianami, wszystkie możliwe punkty będą trafiać systematycznie do list otwartych, 1 element z najmniejszą wartością funkcji f zostanie usunięty z listy otwartej i trafi na listę zamkniętą //powtarzając ten proces aż do wyczerpania punktów z wartością scieżki równą zero, lista otwarta się wyczerpie, algorytm zwróci false

        Punkt* sprawdzanyPunkt = najmniejszaFunkcjaF(); //zmienna wskazuję na wartość punktu z najmniejszą wartością funkcji F
        cout << "sprawdzamy [" << sprawdzanyPunkt->getX() << "," << sprawdzanyPunkt->getY() << "]" << endl;
        //czy sprawdzany Punkt jest końcem trasy
        if (sprawdzanyPunkt->dotarcieDoCelu(koniec)) {
            poczatek->setSciezka(7);
            return true;
        }


        cout << "[" << sprawdzanyPunkt->getX() << "," << sprawdzanyPunkt->getY() << "] wpisujemy na liste zamknieta" << endl;
        Lista_Otwarta.erase(std::remove(Lista_Otwarta.begin(), Lista_Otwarta.end(), sprawdzanyPunkt), Lista_Otwarta.end()); //listaOtwarta.begin() poczaek listy, listaOtwarta.end() koniec listy, rozwana Punkt to element który chcemy usunąć //erase wyszkuje między podanym zakresem, podaną wartośc i usuwa ją
        Lista_Zamknieta.push_back(sprawdzanyPunkt); //dopisuje element na końcu listy


        // wektor przechowujący wskazniki na klasę Punkt
        vector<Punkt*> sasiedniPunkt = znajdzSasiednie(sprawdzanyPunkt);
        for (auto elementListy : sasiedniPunkt) {
            //jeśli element jest nullem, lub 5 (ściąną) lub jest na liście zamkniętęj to: akutalana "iteracja" for'a jest pomijana
            if (elementListy->sprawdzenieListy(Lista_Zamknieta) || elementListy == NULL || elementListy->getSciezka() == 5) //elkement lsty jest w tym przypadku sąsiadem
                continue;


            if (sprawdzanyPunkt->getFunkcjaG()+1 < elementListy->getFunkcjaG() || !elementListy->sprawdzenieListy(Lista_Otwarta)) { //if spełnia się jeżeli wartosc funkcji g sąsiada jest większa od wartości funkcji g sprawdzanego punktu lub gdy sąsiad nie znajduje się na liście otwartej
                elementListy->setRodzic(sprawdzanyPunkt); //rodzicem zostaje sprawdzony Punkt
                elementListy->ObliczanieFunkcji(koniec); //oblicznie funkcji dla punkty końcowego (meta)

                cout << "[" << sprawdzanyPunkt->getX() << "," << sprawdzanyPunkt->getY() << "] zostaje rodzicem [" << elementListy->getX() << "," << elementListy->getY() << "]" << endl;
                if (!elementListy->sprawdzenieListy(Lista_Otwarta)) { //ponownie sprawdzamy czy sąsiedni punkt nie jest na liście otwartej, ponieważ poprzedni if mógł zostać spełniony innym warunkiem //wykrzyknik oznacza negację warunku

                    cout << "[" << elementListy->getX() << "," << elementListy->getY() << "] wpisujemy na liste otwarta" << endl;
                    Lista_Otwarta.push_back(elementListy); //wpisujemy na listę otwartą

                }
            }
        }
    }
    return false;
}
void wyswietlMape() { //wyswietla mapę
    for (int x = 0; x < wys; x++) {
        for (int y = 0; y < szer; y++)
            cout << siatka[y][x].getSciezka() << " ";
        cout << endl;
    }
}

void loadFile(string name) {
    ifstream file(name);
    char temp;
    for (int y = 0; y < wys; y++) {
        for (int x = 0; x < szer; x++) {
            file >> temp;
            siatka[x][y].setX(x);
            siatka[x][y].setY(y);
            siatka[x][y].setSciezka(temp - '0');
        }
    }
    file.close();
}



int main() {
    loadFile("grid.txt");
    // funkcja aGwiazdka zwraca wartość bool, jeśli true
    a_star(0, 19, 19, 0) ? cout << "sciezka wyznaczona :)" << endl : cout << "scieżka nie wyznaczona :(" << endl; //skrócony  if else, za pytajnikiem zostanie zwrócowny w przypadku true, za dwukropkiem w przypadku false

    wyswietlMape();
    return 0;
}


//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    /////////////////////////////////////////////////////////////////////////// KOLEJNOŚĆ KROKÓW ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////