Studia/eri/cwiczenia/projekt/main.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 {
    public:
        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;

        // 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].wartosc << " ";
        cout << endl;
    }
    cout << endl;
}

Kratka *fCostMinimalKratka() {
    Kratka *min = listaOtwarta[0];
    for (auto elem: listaOtwarta)
        if (elem->f <= min->f) 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->y + 1 < height){
        printf("Dół   [%i,%i]\n", poz->x, poz->y+1);
        /* referencja zwraca adres */
        /* wskaznik somsiedzi[0] teraz nosi wartość adresu kratki gridu */
        somsiedzi[0] = &grid[poz->x][poz->y + 1];
    }
    /* lewy sąsiad */
    if (poz->x - 1 >= 0){
        printf("Lewo  [%i,%i]\n", poz->x-1, poz->y);
        somsiedzi[1] = &grid[poz->x - 1][poz->y];
    }
    /* górny sąsiad */
    if (poz->y - 1 >= 0){
        printf("Góra  [%i,%i]\n", poz->x, poz->y-1);
        somsiedzi[2] = &grid[poz->x][poz->y - 1];
    }
    /* prawy sąsiad */
    if (poz->x + 1 < width){
        printf("Prawo [%i,%i]\n", poz->x+1, poz->y);
        somsiedzi[3] = &grid[poz->x + 1][poz->y];
    }
    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->wartosc = 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->wartosc == 5 || elem->czyNaLiscie(listaZamknieta))
                continue;

            /* gcost +=1 ponieważ jest sąsiadem czyli oddalone o jedną kratkę */
            if (rozwazanaKratka->g + 1 < elem->g || elem->czyNaLiscie(listaOtwarta) == false) {
                elem->rodzic = 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].wartosc = temp - '0';
            grid[x][y].x = x;
            grid[x][y].y = y;
        }
    }
    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;
    /* a > b ? a : b; */

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

    return 0;
}