class Kratka():

    def __init__(self, rodzic=None, pozycja=None):
        self.rodzic = rodzic
        self.pozycja = pozycja

        self.g = 0
        self.h = 0
        self.f = 0

    def __eq__(self, other):
        return self.pozycja == other.pozycja


listaOtwarta = []
listaZamknieta = []
listaDzieci = []
sasiedzi = [(0, 1), (-1, 0), (1, 0), (-1, 1), (1, 1), (0, -1), (-1, -1), (1, -1)];


def wyznaczSciezke():
    print("Definiuje grida ... \nPostać grida:")
    grid = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 5, 5, 5, 5, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0],
            [0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0],
            [0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 5, 5, 5, 5, 5],
            [0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
    for g in grid:
        print(g)
    start = Kratka(None, (0, 0))
    koniec = Kratka(None, (19, 19))
    # start - dodanie na liste otwarta pierwszego elementu
    listaOtwarta.append(start)

    # dopoki istenieje lista owarta
    while len(listaOtwarta) > 0:

        # ustawienie elementu na ktorym operuje
        aktualnyWezel = listaOtwarta[0]
        aktualnyIndex = 0
        for index, wezel in enumerate(listaOtwarta):
            if wezel.f < aktualnyWezel.f:
                aktualnyWezel = wezel
                aktualnyIndex = index

        # usuniecie z listy otwartej iterowanego wezla
        listaOtwarta.pop(aktualnyIndex)
        # wrzucenie go do listy zamknietej
        listaZamknieta.append(aktualnyWezel)

        if aktualnyWezel == koniec:
            sciezka = []
            aktualny = aktualnyWezel
            while aktualny is not None:
                sciezka.append(aktualny.pozycja)
                aktualny = aktualny.rodzic
            return sciezka
        # iteracja po tablicy sasiadow wezla
        for sasiad in sasiedzi:
            pw = (aktualnyWezel.pozycja[0] + sasiad[0], aktualnyWezel.pozycja[1] + sasiad[1])
            if pw[0] > (len(grid) - 1) or pw[0] < 0 or pw[1] > (len(grid[len(grid) - 1]) - 1) or pw[1] < 0:
                continue
            if grid[pw[0]][pw[1]] != 0:
                continue
            nastepny = Kratka(aktualnyWezel, pw)
            listaDzieci.append(nastepny)

        # iteracja po pomocniczej liscie wezlow
        for dziecko in listaDzieci:
            for z in listaZamknieta:
                # sprawdzenie czy iterowany element nalezy do listy zamknietej
                if czyWZamknietej(dziecko, z):
                    continue
            # wyliczenie kosztu, drogi i heurestykil;
            wyliczWartosci(dziecko, aktualnyWezel, koniec)

            # sprawdzenie czy iterowany element nalezy do listy owartej
            for o in listaOtwarta:
                if czyWOtwartej(o, dziecko):
                    continue
            listaOtwarta.append(dziecko)


def wyliczWartosci(dziecko, aktualnyWezel, koniec):
    dziecko.g = dajG(aktualnyWezel)
    dziecko.h = dajH(dziecko, koniec)
    dziecko.f = dajF(dziecko)


def czyWZamknietej(d, z):
    if d == z:
        return True
    else:
        return False


def czyWOtwartej(o, d):
    if d == o and d.g > o.g:
        return True
    else:
        return False


def dajG(wezel):
    return wezel.g + 1;


def dajH(dziecko, koncowyWezel):
    return ((dziecko.pozycja[0] - koncowyWezel.pozycja[0]) ** 2) + (
            (dziecko.pozycja[1] - koncowyWezel.pozycja[1]) ** 2)


def dajF(dziecko):
    return dziecko.g + dziecko.h;


def main():
    sciezka = wyznaczSciezke()
    print('------------------------------------------------------------')
    print('Wyznaczona sciezka:')
    print(*sciezka[::-1], sep="\n")


if __name__ == '__main__':
    main()