Algorytm astar

0

Witam, mam problem z algorytmem a gwiazdką, oto kod
https://ntpd.eu/l48AJ

Problem jest w tym, ze plik nie generuje trasy do mapy, ktora wczytujemy z pliku grid.txt
Jedynie meta jest oznaczoną cyfrą 3.
Czy mógłby ktoś naprowadzić mnie, jest jest błąd, czego brakuje?

grid.txt

3

Tak na pierwszy rzut oka - czy to jest prawidłowe?

bool operator<(const Node& other) const {
return f > other.f;
}

Oprócz tego, pls sformatuj kod (poszukaj informacji pod kątem cpp style formatter), ponieważ niestety w takiej formie nie da się go czytać (czytasięgotaksamociężkojaktozdanieczyliaiiaiiouchouchbolipowoli).

0 
/tmp $ clang++ aa.cc -Weverything -fsanitize=memory,undefined -g
aa.cc:28:8: warning: no previous prototype for function 'euclidean' [-Wmissing-prototypes]
double euclidean(int x1, int y1, int x2, int y2) {
       ^
aa.cc:28:1: note: declare 'static' if the function is not intended to be used outside of this translation unit
double euclidean(int x1, int y1, int x2, int y2) {
^
static 
aa.cc:91:82: warning: 'nullptr' is incompatible with C++98 [-Wc++98-compat]
    Node start = {START_X, START_Y, h[START_X][START_Y], 0, h[START_X][START_Y], nullptr};
                                                                                 ^
aa.cc:111:42: warning: 'nullptr' is incompatible with C++98 [-Wc++98-compat]
                while (current.parent != nullptr) {
                                         ^
aa.cc:119:41: warning: implicit conversion changes signedness: 'int' to 'std::vector::size_type' (aka 'unsigned long') [-Wsign-conversion]
                    map[path[i].x][path[i].y] = PATH;
                                   ~~~~ ^
aa.cc:119:30: warning: implicit conversion changes signedness: 'int' to 'std::vector::size_type' (aka 'unsigned long') [-Wsign-conversion]
                    map[path[i].x][path[i].y] = PATH;
                        ~~~~ ^
aa.cc:144:45: warning: missing field 'parent' initializer [-Wmissing-field-initializers]
            Node next = {x, y, f, g, h[x][y]};
                                            ^
aa.cc:118:42: warning: implicit conversion loses integer precision: 'unsigned long' to 'int' [-Wshorten-64-to-32]
                for (int i = path.size() - 1; i >= 0; i--) {
                         ~   ~~~~~~~~~~~~^~~
7 warnings generated.
/tmp $ ./a.out
==135440==WARNING: MemorySanitizer: use-of-uninitialized-value
    #0 0x4b33ed in main /tmp/aa.cc:56:139
    #1 0x7fd12901750f in __libc_start_call_main (/lib64/libc.so.6+0x2750f) (BuildId: 81daba31ee66dbd63efdc4252a872949d874d136)
    #2 0x7fd1290175c8 in __libc_start_main@GLIBC_2.2.5 (/lib64/libc.so.6+0x275c8) (BuildId: 81daba31ee66dbd63efdc4252a872949d874d136)
    #3 0x421494 in _start (/tmp/a.out+0x421494) (BuildId: d3988a381bff7b98645ad3140891f8b03093f051)

SUMMARY: MemorySanitizer: use-of-uninitialized-value /tmp/aa.cc:56:139 in main
Exiting

Ogólnie zdaje się, że nigdzie sensownie nie ustawiasz pola parent z którego potem próbujesz korzystać. Gdybyś chociaż ustawiał na nulla, to by nie było UB w programie.

0

https://godbolt.org/z/Ezhna4Waq (zmieniłem tylko, żeby używało std::cin zamiast pliku)

Radziłbym podzielić kod na mniejsze fragmenty, które będą bardziej zrozumiałe dla normalnego programisty.

if (START_X == OBSTACLE || START_Y == OBSTACLE || GOAL_X == OBSTACLE || GOAL_Y == OBSTACLE)

WAT? Czy ja dobrze rozumiem? Porównujesz przeszkodę do indeksu?

1 użytkowników online, w tym zalogowanych: 0, gości: 1