Studia/eri/cwiczenia/projekt/copy.cpp

#include <iostream>
#include <fstream>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;

/* int const height = 6, width = 6; */
/* int const height = 6, width = 11; */
int const height = 20, width = 20;
class Kratka {
    private:
        int wartosc; // zmienna na zaznaczenie scieżki
        double g = 0; // odleglosc rozwazanej kratki od punktu startKratkaowego
        double f = 0; // odleglosc rozwazanej kratki od punktu koncowego
        int x; //położenie na mapie
        int y; //położenie na mapie
        Kratka *rodzic = nullptr;

    public:
        void setter(int x, int y, int wartosc){
            this -> x = x;
            this -> y = y;
            this -> wartosc = wartosc;
        }
        void setX(int x){
            this -> x = x;
        }
        void setY(int y){
            this -> y = y;
        }
        void setWartosc(int wartosc){
            this -> wartosc = wartosc;
        }
        void setF(int f){
            this -> f = f;
        }
        void setRodzic(Kratka* rodzic){
            this -> rodzic = rodzic;
        }

        int getX(){
            return this->x;
        }
        int getY(){
            return this->y;
        }
        int getWartosc(){
            return this->wartosc;
        }
        int getF(){
            return this->f;
        }
        int getG(){
            return this->g;
        }
        Kratka* getRodzic(){
            return this->rodzic;
        }



        // funkcja sprawdzająca czy wywołujący obiekt jest w wektorze
        bool czyNaLiscie(vector<Kratka*> lista) {
            for (auto elem: lista)
                if (elem == this) return true;
            return false;
        }
        // funkcja obliczająca fCost i osadzający tę wartość w wywołującym obiekcie
        void fCost(Kratka *celKratka) {
            double h_cost = sqrt(pow((this->x - celKratka->x), 2) + pow((this->y - celKratka->y), 2));
            this->g = this->rodzic->g + 1;
            this->f = h_cost + this->g;
        }

        bool czyOsiagnieto(Kratka *cel){
            if(this == cel){
                // kontynuuj dopóki rodzic nie jest NULLEM (wraca spowrotem po sciezce i przypisuje wartosci 1)
                while (cel->rodzic) {
                    cel->wartosc = 1;
                    cel = cel->rodzic;
                }
                return true;
            }
            return false;
        }
};
/* wektor o wielkości width, przechowujący elementy o wartości vector<Kratka>(height)*/
vector<vector<Kratka>> grid(width, vector<Kratka>(height));
// wektor wskaźników na instancje klasy Kratka
vector<Kratka*> listaOtwarta;
vector<Kratka*> listaZamknieta;
vector<Kratka> listaOtwartaTest;
vector<Kratka> listaZamknietaTest;

void display() { //wyswietla mapę
    cout << endl;
    for (int i = 0; i < height; i++) {
        for (int j = 0; j < width; j++)
            cout << grid[j][i].getWartosc() << " ";
        cout << endl;
    }
    cout << endl;
}

Kratka *fCostMinimalKratka() {
    Kratka *min = listaOtwarta[0];
    for (auto elem: listaOtwarta)
        if (elem->getF() <= min->getF()) min = elem;
    return min;
}

vector<Kratka*> wyznaczSomsiadow(Kratka *poz){
    /* wektor wskaznikow o domyślych wartościach null */
    vector<Kratka*> somsiedzi(4, nullptr);
    /* printf("Kratka [%i,%i] ma sąsiadów:\n", poz->x, poz->y); */
    /* wyznaczamy potencjalnych sąsiadów o ile nie wypadają poza grid */
    if (poz->getY() + 1 < height){
        /* printf("Dół   [%i,%i]\n", poz->getX(), poz->getY()+1); */
        /* referencja zwraca adres */
        /* wskaznik somsiedzi[0] teraz nosi wartość adresu kratki gridu */
        somsiedzi[0] = &grid[poz->getX()][poz->getY() + 1];
    }
    /* lewgetY() sąsiad */
    if (poz->getX() - 1 >= 0){
        printf("Lewo  [%i,%i]\n", poz->getX()-1, poz->getY());
        somsiedzi[1] = &grid[poz->getX() - 1][poz->getY()];
    }
    /* górngetY() sąsiad */
    if (poz->getY() - 1 >= 0){
        printf("Góra  [%i,%i]\n", poz->getX(), poz->getY()-1);
        somsiedzi[2] = &grid[poz->getX()][poz->getY() - 1];
    }
    /* prawgetY() sąsiad */
    if (poz->getX() + 1 < width){
        printf("Prawo [%i,%i]\n", poz->getX()+1, poz->getY());
        somsiedzi[3] = &grid[poz->getX() + 1][poz->getY()];
    }
    return somsiedzi;
}
bool aGwiazdka(int sx, int sy, int cx, int cy) {
    Kratka *startKratka = &grid[sx][sy];
    Kratka *celKratka = &grid[cx][cy];

    listaOtwarta.push_back(startKratka);
    listaOtwartaTest.push_back(*startKratka);
    while (listaOtwarta.size() > 0) {
        Kratka *rozwazanaKratka = fCostMinimalKratka();
        /* printf("Kratka [%i,%i] jest obecnie rozważana\n", rozwazanaKratka->x, rozwazanaKratka->y); */

        if(rozwazanaKratka->czyOsiagnieto(celKratka)){
            startKratka->setWartosc(1);
            return true;
        }

        /* printf("Kratka [%i,%i] zostaje usunięta z listy otwartej i trafia do listy zamknietej\n", rozwazanaKratka->x, rozwazanaKratka->y); */
        listaOtwarta.erase(std::remove(listaOtwarta.begin(), listaOtwarta.end(), rozwazanaKratka), listaOtwarta.end());
        listaZamknieta.push_back(rozwazanaKratka);
        listaZamknietaTest.push_back(*rozwazanaKratka);

        /* wektor wskaznikow na obiekty Kratka */
        vector<Kratka*> somsiadKratka = wyznaczSomsiadow(rozwazanaKratka);
        for (auto elem: somsiadKratka) {
            /* jezeli sasiad ma wartosc null (poza mapą) */
            if (elem == nullptr || elem->getWartosc() == 5 || elem->czyNaLiscie(listaZamknieta))
                continue;

            /* gcost +=1 ponieważ jest sąsiadem czyli oddalone o jedną kratkę */
            if (rozwazanaKratka->getG() + 1 < elem->getG() || elem->czyNaLiscie(listaOtwarta) == false) {
                elem->setRodzic(rozwazanaKratka);
                elem->fCost(celKratka);
                /* printf("Rodzicem kratki[%i,%i] staje się kratka [%i,%i]\n", elem->x, elem->y, rozwazanaKratka->x, rozwazanaKratka->y); */
                if(elem->czyNaLiscie(listaOtwarta) == false){
                    /* printf("Kratka [%i,%i] trafia do listy otwartej\n", elem->x, elem->y); */
                    listaOtwarta.push_back(elem);
                    listaOtwartaTest.push_back(*elem);
                }
            }
        }
    }
    return false;
}

void loadFile(string name) {
    ifstream file(name);
    char temp;
    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            file >> temp;
            grid[x][y].setter(x,y, temp - '0');
        }
    }
    file.close();
}
/* void zaznaczOdwiedzone(){ */
/*     int o = 2, z = 3; */
/*     for(auto elem: listaOtwartaTest) */
/*         if(grid[elem.x][elem.y].wartosc != 1) */
/*             grid[elem.x][elem.y].wartosc = o; */
/*     for(auto elem: listaZamknietaTest) */
/*         if(grid[elem.x][elem.y].wartosc != 1) */
/*             grid[elem.x][elem.y].wartosc = z; */
/* } */

int main() {
    bool wynik;

    /* loadFile("grid_video.txt"); */
    /* wynik = aGwiazdka(7,4,4,1); */

    /* loadFile("grid_small.txt"); */
    /* wynik = aGwiazdka(1,2,5,1); */

    loadFile("grid.txt");
    wynik=aGwiazdka(0,19,19,0);
    wynik ? cout << "SCIEŻKA ZNALEZIONA" << endl : cout << "SCIEŻKA NIE ZNALEZIONA" << endl;

    /* zaznaczOdwiedzone(); */
    display();

    return 0;
}