Wyszukiwanie ścieżek 2D - znajdowanie gładkich ścieżek

10

Próbowałem wdrożyć proste wyszukiwanie ścieżek, ale wynik jest mniej zadowalający niż to, co zamierzałem osiągnąć. Chodzi o to, że jednostki w grach takich jak Starcraft 2 poruszają się we wszystkich kierunkach, podczas gdy jednostki w moim przypadku poruszają się tylko w maksymalnie 8 kierunkach (styl Warcraft 1), ponieważ te 8 kierunków prowadzą do następnych dostępnych węzłów (przemieszczają się z kafelka na następny sąsiadujący kafelek) . Co powinienem zrobić, aby osiągnąć wynik jak w Starcraft 2? Zmniejszyć rozmiar płytki?

http://i.stack.imgur.com/lr19c.jpg

Na zdjęciu widać poziomą linię kamiennych kafelków będących przeszkodami, a znalezioną ścieżkę oznaczoną jako zielone kafelki. Czerwona linia to ścieżka, którą chcę osiągnąć.

game-design game-mechanics path-finding Kooi Nam Ng
źródło
Jestem wielkim fanem poszukiwania punktu skoku, chociaż nie znalazłem jeszcze czasu na jego wdrożenie. Ale dokumentacja była interesująca i ma dobrą wydajność.
2
Czy jesteś pewien, że to jest twoja pożądana ścieżka? Jednostki, które z niego korzystają, częściowo przechodzą przez ściany. Uczyniłem to bardziej widocznym w innym przykładzie: i.imgur.com/eh4ZR.png A oto, co prawdopodobnie naprawdę chcesz osiągnąć: i.imgur.com/vFQg4.png
Markus von Broady,
Masz rację. Moja ścieżka była wadliwa, ale służyła raczej celom ilustracyjnym. Dzięki za wskazanie lepszego sposobu patrzenia.
Kooi Nam Ng
Musisz mieć współrzędne ułamkowe w kafelku, aby uzyskać to, czego chcesz. Żadna możliwa ścieżka bez tego nie działałaby - przenoszenie ułamków, ale ich nie wyświetlanie sprawiłoby, że jednostka poruszała się prosto / ukośnie / prosto / ukośnie.
Loren Pechtel,
@LorenPechtel się mylisz, możesz wygładzić ścieżkę po znalezieniu jednego. Jest to dość łatwe, ponieważ tworzysz dwie linie na podstawie wymiarów jednostki i sprawdzasz, czy przecinają się one z kafelkami między kafelkiem0 a kafelkiem N, gdzie kafelek1-kafelek (N-1) to kafelki, które chcesz usunąć ze ścieżki.
Markus von Broady,

Odpowiedzi:

8

Jednak dla dobrego algorytmu znajdowania ścieżki użycie A * byłoby prawdopodobnie dobrym pomysłem w przypadku prostej gry, która nie wymaga zaawansowanego, wydajnego ani efektywnego wyszukiwania ścieżki, po prostu każąc postaciom zbliżyć się do celu poprzez ustalenie kierunku cel powinien być wystarczający.

Możesz zrobić to wygenerować „wykres widoczności” (jakie inne punkty są widoczne z każdego punktu) z wierzchołków, a następnie wykonać A * na wykresie. Działa to, ponieważ najkrótsza ścieżka zawsze będzie znajdować się na wykresie widoczności.

Pomniejsz rozmiar płytki.

Zasoby

Dalsza lektura

EDYCJA: Podoba mi się komentarz @ MarkusvonBroady.

„w rzeczywistości chodzi o wygładzanie ścieżki, a nie znajdowanie. Ścieżka znaleziona na zdjęciu wygląda OK.”

Zasoby

Od @ MarkusvonBroady

Przeprowadziłem wyszukiwanie, znajdź następujące (mogą ci pomóc)

Md Mahbubur Rahman
źródło
1
świetne linki, +1 ode mnie
lhk
2
@MarkusvonBroady, dzięki za -1. Nauczyłem się od ciebie. Nie chcę punktu, raczej jestem gotów uczyć się i dzielić właściwą. Wierzę, że dyskutując, możemy znaleźć właściwy. :)
Md Mahbubur Rahman,
@MarkusvonBroady, czy mógłbyś udostępnić kilka zasobów algorytmu wygładzania ścieżki?
Md Mahbubur Rahman
Właściwie myślę, że ta odpowiedź pomaga OP. Nie sądzę, żeby OP żądał faktycznego wygładzenia (interpolacja splajnu lub tym podobne), ale raczej to, że jego algorytm znajduje obecnie strasznie nieoptymalną ścieżkę i musi zostać „wygładzony” do linii prostszej. Który A * naturalnie znalazłby dla niego bez dodatkowego wygładzania.
Sean Middleditch
Korzystałem z A * i myślę, że znalazłem optymalną ścieżkę.
Kooi Nam Ng
0

Zaczynając od jednego końca surowej ścieżki, powiedzmy path[0], możesz usunąć, path[1]jeśli segment utworzony przez połączenie punktów path[0]i path[2]NIE przecina żadnej ściany. Idąc dalej, aż ostatni segment zapewni prostszą ścieżkę.

To nie tylko wygładzi ścieżkę, ale także usunie niektóre bezużyteczne punkty, takie jak przykład ognia, 3 kolejne segmenty linii prostej.

arainone
źródło