Wyszukiwanie ścieżek z ruchem 2D, nie opartym na siatce, na jednolitym terenie

Szukam najlepszego rozwiązania do wyszukiwania ścieżek w mojej grze. Mapa jest ostatecznie oparta na siatce, ale elementy są pozycjonowane za pomocą pływaków i mogą przemieszczać się w dowolnym kierunku do dowolnego punktu na mapie. „Ziemia” w mojej grze ma jednolity koszt ruchu, ale oczywiście mogą istnieć przeszkody, które blokują drogę. Większość przeszkód będą statyczne i choć nie będzie innych podmiotów Animacja w grze, to może uciec z ich nie rozważa - to izometrycznym Theme Hospital strategia styl gry, więc nie ma walki.

Większość artykułów na temat szukania ścieżki dotyczy ruchu w 3D lub 2D. Wszelkie sugestie dotyczące czegoś, co może obejmować mój przypadek użycia? Wielkie dzięki.

Nazywa się to „problemem wyszukiwania ścieżki pod dowolnym kątem”. Zasadniczo masz dwie możliwości:

1. Wygeneruj siatkę nawigacji dla swojej mapy i wyszukaj ją za pomocą A *

   

2. Przeszukuj siatkę za pomocą algorytmu przeznaczonego specjalnie do wyszukiwania ścieżek pod dowolnym kątem. Tradycyjnie sposobem na to było wygładzanie ścieżki A * + (interpolacja liniowa itp.) , Ale obecnie bardziej popularną alternatywą jest Theta * , która jest łatwiejsza do wdrożenia, działa szybciej i daje lepsze wyniki niż wygładzanie ścieżki.

   

Wszystkie powyższe metody generują prawie optymalne wyniki. Jeśli z jakiegoś powodu potrzebujesz optymalnych rezultatów, ten artykuł został wydany kilka tygodni temu. Nie miałem jeszcze okazji go przeczytać, więc nie wiem, jak skuteczny jest i jak trudny do wdrożenia.