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

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”?

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.

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.

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).

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).