* Nawigacyjne wyszukiwanie ścieżki siatki

Więc stworzyłem tę odgórną grę 2D Java w tej strukturze o nazwie Greenfoot i pracowałem nad sztuczną inteligencją dla facetów, z którymi będziesz walczył. Chcę, aby mogły one realistycznie przemieszczać się po świecie, więc wkrótce zdałem sobie sprawę, że między innymi potrzebuję jakiegoś rodzaju znalezienia ścieżki.

Zrobiłem dwa prototypy A *. Jeden jest oparty na siatce, a potem stworzyłem taki, który działa z punktami trasy, więc teraz muszę znaleźć sposób, aby przejść z „mapy” przeszkód / budynków na 2D do wykresu węzłów, z którego mogę zrobić ścieżkę. Rzeczywiste wyszukiwanie ścieżek wydaje się być w porządku, tylko moje otwarte i zamknięte listy mogłyby użyć bardziej wydajnej struktury danych, ale przejdę do tego, kiedy i kiedy będę tego potrzebować.

Zamierzam użyć siatki nawigacyjnej ze wszystkich powodów wymienionych w tym poście na ai-blog.net . Jednak problem, z którym się spotkałem, polega na tym, że to, co A * uważa za najkrótszą ścieżkę od centrów / krawędzi wielokąta, niekoniecznie jest najkrótszą ścieżką, jeśli podróżujesz przez dowolną część węzła. Aby uzyskać lepszy pomysł, możesz zobaczyć pytanie, które zadałem na stosie .

Mam dobrą odpowiedź dotyczącą wykresu widoczności. Od tego czasu kupiłem książkę ( Geometria obliczeniowa: algorytmy i aplikacje ) i czytałem dalej w tym temacie, jednak nadal opowiadam się za siatką nawigacyjną (patrz „ Zarządzanie złożonością ” w notatkach Amita na temat znajdowania ścieżek ). (Na marginesie, być może mógłbym użyć Theta * do przekształcenia wielu punktów na jedną linię prostą, jeśli pierwszy i ostatni nie są zasłonięte. Lub za każdym razem, gdy cofam się, sprawdzaj przedtem punkt na drodze, aby sprawdzić, czy mogę przejść prosto z to do tego)

Tak więc w zasadzie to, czego chcę, to siatka nawigacyjna, w której po przejściu przez algorytm lejkowy (np. Ten z Digesting Duck ) uzyskam prawdziwą najkrótszą ścieżkę, zamiast tej, która jest najkrótszą ścieżką prowadzącą tylko od węzła do węzła, ale nie najkrótsza, biorąc pod uwagę, że można przejść przez niektóre wielokąty i pominąć węzły / krawędzie.

Aha i ja też chcę wiedzieć, jak sugerujesz przechowywanie informacji dotyczących wielokątów. Dla przykładu prototypu waypointa, który stworzyłem, miałem po prostu każdy węzeł jako obiekt i zapisałem listę wszystkich innych węzłów, do których możesz podróżować z tego węzła. Zgaduję, że to nie zadziała z wielokątami? i jak powiedzieć, czy wielokąt jest otwarty / można go przechodzić, czy też jest to obiekt stały? Jak przechowywać, które węzły tworzą wielokąt?

Wreszcie, dla przypomnienia: chcę sam to zaprogramować od zera, mimo że są już dostępne inne rozwiązania i nie zamierzam (ponownie) używać tego kodu w niczym innym niż ta gra, więc to nie ma znaczenia nieuchronnie będzie niskiej jakości.

Radzę, że nawet jeśli masz zamiar napisać cały swój kod, pobierz aplikację Przekształć i skompiluj przykładową aplikację, ponieważ ma ona wizualizacje pokazujące wygenerowany navmesh i pozwala przetestować wyszukiwanie ścieżki za pomocą jednego punktu i kliknięcia berło. Możesz się wiele nauczyć, grając z tym.

Jak już zauważyliście, istnieją dwa kroki do stworzenia dobrze wyglądającej ścieżki - znajdowanie ścieżki A *, a następnie kolejne przetwarzanie, które obejmuje prostowanie ścieżki (eliminacja wszelkich zakrętów, które nie są konieczne do uniknięcia przeszkód), a być może także dodawanie krzywych w punktach zwrotnych.

Znalezienie drogi

Masz opanowaną część A *, co jest świetne. Zauważyłeś również, że A * nie zawsze znajdzie najprostszą ścieżkę. Ważne jest, aby zrozumieć, że dzieje się tak, ponieważ A * to algorytm znajdujący najkrótszą ścieżkę przez wykres (ponieważ jest to koncepcja matematyczna, w której węzły są bezwymiarowe), kiedy zastosujesz go do siatki, musisz jakoś odwzorować węzły na elementy siatki.

Najbardziej oczywistą rzeczą jest nawigacja od punktu środkowego wielokąta do punktu środkowego i oparcie kosztów na tej odległości, ale ma to pewne problemy. Po pierwsze, nie zawsze znajdzie najkrótszą geometrycznie ścieżkę, a po drugie, jeśli spróbujesz podążać ścieżką, którą tam obliczyłeś, zauważysz, że linia prosta od jednego środka do drugiego może przecinać wielokąt, który nie jest to część ścieżki (i może w ogóle nie być możliwa do nawigacji). Nie jest to okropny sposób, aby kosztować przejście wykresu podczas wykonywania A *, ale najwyraźniej nie jest odpowiedni do żadnego celu przejścia.

Kolejnym najprostszym rozwiązaniem jest wykonanie A * od krawędzi do krawędzi przez siatkę. Łatwiej jest pomyśleć, jeśli wyobrażasz sobie, że zamiast jednego węzła na wielokąt masz jeden na krawędź na wielokąt. Twoja ścieżka wiedzie od punktu początkowego do najbliższej krawędzi, przecina się do krawędzi sąsiadującego wielokąta, a następnie do następnej krawędzi w tym samym wielokącie i tak dalej. Powoduje to częstsze tworzenie najkrótszej ścieżki, a ponadto ma tę zaletę, że można ją pokonywać, jeśli nie chcesz wykonywać kroku prostowania ścieżki.

Prostowanie ścieżki

Algorytm użyty w Objeździe (biblioteka nawigacyjna dołączona do Recast) jest dość prosta. Powinieneś zauważyć, że to tylko wyprostuje ścieżkę w granicach wielokątów znalezionych podczas wyszukiwania A *. Jako taki, jeśli to nie znajdzie ciasnej ścieżki wokół przeszkody, nie uzyskasz również ciasnej ścieżki po uruchomieniu tego algorytmu. W praktyce siatki nacięcia wytworzone przez przekształcenie mają zwykle jeden wielokąt, przez który można przejść podczas nawigowania punktu dławika (najbliższego punktu między dwiema przeszkodami), dlatego A * zawsze tworzy listę węzłów, które są tak blisko przeszkody, jak możliwy. Jeśli używasz kafelków jako navmesh, tak nie będzie i ten bardzo prosty algorytm wstawi fałszywe zakręty.

Algorytm prostowania ścieżki objazdu nie jest dość złożony (O), ponieważ gdy stwierdza, że ​​musi wstawić zakręt, wstawia go w punkcie, w którym ostatnio dokręcił lejek w lewo (podczas skręcania w lewo i odwrotnie) i następnie ponownie rozpoczyna śledzenie węzłów od tego miejsca.

Jeśli chcesz wyprostować ścieżkę poza wielokątami, które tworzą część trasy A *, sprawy stają się znacznie bardziej złożone. Musisz wdrożyć procedurę rzutowania promieni, która może sprawdzić, czy dwa punkty w twoim navmesh mogą się widzieć (powinieneś to mieć i tak, abyś mógł sprawdzić, czy w ogóle potrzebujesz A *). Robisz to, przecinając segment linii utworzony przez początek-> cel z łączącymi się krawędziami wielokąta zawierającego początek, a następnie testując łączące się krawędzie wielokąta, który cię przenosi i tak dalej. Jeśli przecinasz niepołączoną krawędź (nazywam je krawędziami granicznymi), to trafiłeś w przeszkodę.

Możesz następnie wykonać ten test rzutowy, ilekroć algorytm lejkowy ustali, że musi wstawić zwrot, aby zobaczyć, czy rzeczywiście działa, ale myślę, że będziesz musiał wykonywać ten test w każdym węźle, dopóki nie wstawisz zwrotu (w który punkt możesz przywrócić do algorytmu prostej ścieżki). To będzie drogie, powodując, że ścieżka wyprostuje się w przybliżeniu O (n ^ 2).

Reprezentujący navmesh

Możesz przedstawić siatkę jako tablicę klas wielokątów. Klasa wielokątów może być tak prosta, jak tablica wierzchołków i tablica odniesień do sąsiedniego wielokąta dla każdej krawędzi, jeśli taka istnieje. Oczywiście prawdopodobnie możesz wymyślić sposoby przechowywania tego w bardziej kompaktowy sposób. Ponieważ wierzchołek jest zwykle współużytkowany przez kilka wielokątów, normalne jest posiadanie jednej dużej tablicy wierzchołków, a następnie umieszczenie w tej tablicy indeksów każdego wielokąta. W zależności od właściwości navmesh możesz mieć średnią liczbę krawędzi łączących, która wynosi tylko 50% lub mniej liczby krawędzi. W takim przypadku możesz zapisać link do innego wielokąta i indeks krawędzi zamiast przechowywać link dla każdej krawędzi. Polecam również przechowywanie indeksu wielokąta w tablicy wielokątów navmesh zamiast używania odwołania do klasy.