Pathfinder w JS

pytanie zadane 20 lipca 2015 w JavaScript przez Magicone Nałogowiec (45,100 p.)

Hej, ostatnio natknąłem się na challange, polegający na znalezieniu w dwuwymiarowym układzie współrzędnych najkrótszej drogi od punktu A do punktu B. Oczywiście na mapie są kolizje, zapisane w postaci #, na które nie można wchodzić. Algorytm, który napisałem(link na dole) dziwnie radzi sobie z podaną w skrypcie, przykładową trasą. Czy znalazłby się ktoś, kto mógłby stwierdzić, co w nim nie tak? Do wyboru został jeszcze floodfill, ale mega trapi mnie, dlaczego to nie chce działać. Tak, na większą skalę takie coś nie ma sensu, ale do jakiegoś prostego RPG mogłoby być może przydatne :P

Kod zamieszczam tutaj, nie chcę przypadkowo uszkodzić "struktury" forum: http://pastebin.com/TdFEyvHR

1 odpowiedź

odpowiedź 20 lipca 2015 przez Comandeer Guru (601,590 p.)
wybrane 24 lipca 2015 przez Magicone

Najlepsza

Hmm… Jakąś trasę zwraca. Pytanie jaką powinno zwracać ;) Masz przewidywany output?

komentarz 20 lipca 2015 przez Magicone Nałogowiec (45,100 p.)

Generalnie cały pathfinder polega na określeniu jak najkrótszej trasy, myślałem, żeby dodawać dobre tasy do zmiennej truePaths, a następnie wybierać najkrótszą z nich i zwracać, coś jednak nie chce mnie słuchać. :D

komentarz 21 lipca 2015 przez Comandeer Guru (601,590 p.)

Jak na razie to chyba 1 trasę znajduje? Prawdę mówiąc na chwilę obecną nie bardzo wiem jak to poprawić

komentarz 21 lipca 2015 przez Magicone Nałogowiec (45,100 p.)

Tak, cośtam daje. Ale rezultaty są.. no głupie po prostu. :D Przykładowo: 1,1; 2,1; 1,1; -> idąc na pozycję 2,1 z 1,1 ponownie wraca na 1,1. Algorytm powinien działać tak, że z każdej pozycji próbuje się poruszyć w górę/dół/prawo/lewo, rekurencyjnie porusza się na daną pozycję, jeśli nie ma kolizji, nie przekracza wymiarów mapy oraz nie był jeszcze na danej pozycji(1,1; 2,1; 1,1; trochę zaskakuje). Zakładam, że jest gdzieś błąd założenia, albo w składni się machnąłem jakoś - mimo tego, że przepisywałem go już 3 razy. :D

komentarz 24 lipca 2015 przez Magicone Nałogowiec (45,100 p.)
edycja 24 lipca 2015 przez Magicone

Znalazłem jeden błąd. Na starcie, gdy szukało kolizji i dodawało je do zmiennej received należało uwzględnić punkt A :) Teraz działa nieco normalniej(?), ale dalej nie zgodnie z tym, co chciałem osiągnąć. Ze względu na to, jaki cel miała pierwsza trasa( spójrz podpunkt a) na obrazku(kolejność) ) - received było zajęte i inne trasy nie mogły tędy biegnąć. Zatem błędem założenia było stworzenie jednego, globalnego received! :) Mimo, że odpowiedź uzyskałem sam daje Ci najlepszą, bo jedyny mi odpisałeś :P Co do samego algorytmu, w tym wypadku najoptymalniejsza trasa to b) lub c) :)

obrazek: