Ścieżka „linii wzroku” w poprzek siatki nawigacyjnej


9

Chcę obliczyć linię wzroku w siatce nawigacji.

Rozważmy poniższy obraz, żółta linia jest wynikiem tylko A *, a czerwona linia jest wynikiem algorytmu linii wzroku, który wykorzystuje żółtą linię jako dane wejściowe. Teraz jednostka może poruszać się bezpośrednio bez „zygzakowania”.

Co to jest algorytm obliczający tę „linię wzroku”?

wprowadź opis zdjęcia tutaj

Odpowiedzi:


6

Szukasz algorytmu lejka.

Tutaj jesteś prosty

http://digestingduck.blogspot.com.es/2010/03/simple-stupid-funnel-algorithm.html

Zasadniczo algorytm identyfikuje krawędzie jako portale i buduje lejek, który jest testowany względem wierzchołka krawędzi, aby sprawdzić, czy znajdują się w lejku, czy nie.

W kroku A lejek jest budowany z pozycją początkową, a portal przecina żółta linia.

W kroku B sprawdzany jest następny portal, górny wierzchołek znajduje się wewnątrz lejka, więc teraz przechodzi przez niego górna linia lejka. Ale dolny wierzchołek jest poza lejkiem, ponieważ czerwona linia znajduje się pod zieloną linią, więc dolna linia nie przejdzie przez nią, będzie nadal przechodzić przez dolny wierzchołek poprzedniego portalu.

Jak można sprawdzić, lejek będzie mniejszy i mniejszy, aż do kroku F, w którym nie można zbudować lejka, ponieważ czerwona linia stanowi zły lejek, więc górny wierzchołek jest wybierany jako nowy punkt początkowy, a nowy lejek byłby buduj, jeśli punktu końcowego nie ma w tej siatce.

wprowadź opis zdjęcia tutaj

Zdaj sobie sprawę, że ten rodzaj algorytmu pozwala również na proste rozwiązanie problemu z rozmiarem modelu, ponieważ możesz wziąć pod uwagę, że portale są mniejsze o 2x promień twojego modelu.

wprowadź opis zdjęcia tutaj


6

Istnieje prosta technika, którą można zastosować w przypadku wygenerowanych ścieżek przy użyciu tego pomysłu na linię wzroku. Zasadniczo chcesz przejść ścieżkę i na każdym węźle „spojrzeć wstecz” dwa węzły przed ostatnim, aby zobaczyć, czy jest widoczny. Jeśli węzeł przed ostatnim jest widoczny, możesz usunąć ostatni węzeł (ponieważ masz linię wzroku między bieżącym węzłem a węzłem przed ostatnim, ostatni węzeł będący węzłem pośrednim nie jest wymagany).

wprowadź opis zdjęcia tutaj

Artykuł Gamasutra zawiera następujący przykład pseudokodu:

checkPoint = starting point of path
currentPoint = next point in path
while (currentPoint->next != NULL)
if Walkable(checkPoint, currentPoint->next)
// Make a straight path between those points:
temp = currentPoint
currentPoint = currentPoint->next
delete temp from the path
else
checkPoint = currentPoint
currentPoint = currentPoint->next

Ten algorytm działa tak, jak chcesz, gdzie Walkablefunkcja jest zasadniczo funkcją linii widzenia, ale nieznacznie poprawiona, aby uwzględnić również sytuacje, w których ścieżka jest widoczna, ale nie jest możliwa do przejścia (np. Doły, pułapki, strefy ograniczone).


Rozumiem, co mówisz, ale wciąż nie wiem, jak obliczyć linię wzroku. Czy mógłbyś opisać, co byłoby w funkcji Walkable przy użyciu trójkątnej siatki nawigacyjnej?
Yannick Lange

Ta odpowiedź dotyczy ścieżkowania opartego na siatce i jest bezużyteczna w scenariuszu z siatką nawigacyjną
Blau
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.