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

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?

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ść.

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:

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

Wyszukiwanie ścieżek na mapach opartych na kafelkach

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

http://www.gamasutra.com/view/feature/131505/toward_more_realistic_pathfinding.php

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

— Md Mahbubur Rahman
źródło

świetne linki, +1 ode mnie

— lhk

@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

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