Dynamiczne wyszukiwanie ścieżek w czasie rzeczywistym?

Obecnie prowadzę badania w celu znalezienia ścieżki, a moja symulacja jest następująca: mam scenę 3D z reprezentowanym punktem początkowym i końcowym, jestem w stanie tworzyć siatki nawigacyjne, punkty i wielokąty, aby pomóc w znalezieniu ścieżki.

Wypróbowałem algorytm A * i niektóre jego warianty i działają one doskonale. Jednak teraz bardziej interesuje mnie „dynamiczne” wyszukiwanie ścieżek. Na przykład, znajdując ścieżkę od punktu A do punktu B, jeśli nagle pojawi się nowa przeszkoda, chcę, aby mój algorytm mógł natychmiast ponownie zaplanować ścieżkę i nie zaczął ponownie szukać od zera.

Przeczytałem trochę algorytmu D * i zastanawiam się, czy byłoby to odpowiednie do tego, czego potrzebuję, czy też byłoby to przesadą.

Więc moje pytania są w zasadzie: Jaki algorytm byłby najlepszy do dynamicznego wyszukiwania ścieżek w czasie rzeczywistym? LUB jakiej kombinacji technik mógłbym zamiast tego użyć?

algorithm path-finding

— Andrei
źródło

Nie jestem pewien, jakiego algorytmu używają, więc to nie jest odpowiedź, ale wyobrażam sobie, że właśnie to próbujesz naśladować: wideo na youtube

— MichaelHouse

Co z przedłużeniem A *? Rozszerzanie tego, co jest przechowywane w węzłach jego zestawów otwartych / zamkniętych o to, czego chcesz i rozszerzanie A *, aby to rozważyć.

— user712092,

Szukałem odpowiedzi tak samo jak ty i znalazłem artykuł o HPA *, który jest związany z grą wideo. Nadal szukam artykułu i prawdopodobnie zamierzam go wdrożyć. Jak dotąd poprawa wydajności ma dla mnie sens i może być używana zarówno w środowisku statycznym, jak i dynamicznym. Oto artykuł

— NelsonPunch

Odpowiedzi:

D * jest dość zaangażowany - nie polecam próbować go wdrożyć. Nawet gdy projekty, które są dobrze finansowane i są opracowywane przez inteligentnych / doświadczonych ludzi, używa się D * lite, ponieważ D * jest takim bólem, gdy trzeba się dobrze.

Być może zainteresuje Cię ta prezentacja, która obejmuje omówienie ścieżki Left 4 Dead:

http://www.valvesoftware.com/publications/2009/ai_systems_of_l4d_mike_booth.pdf

Jednym z podejść jest użycie wyszukiwania zgrubnego na poziomie A * w celu uzyskania ogólnej ścieżki dla agenta, a następnie wyszukanie dokładnego poziomu A * dla lokalnego środowiska agenta. W ten sposób możesz szybko ponownie obliczyć wyszukiwanie szczegółów A * w przypadku zmiany terenu, a następnie szybko ponownie obliczyć wyszukiwanie drobnych szczegółów A * dla małego segmentu środowiska. To nie jest idealne. Działa tak długo, jak przeszkody nie są w stanie zablokować wielu węzłów szczegółowych wykresów, co jest dobre w większości gier. Jest to metoda zalecana, jeśli masz mniej niż 100 agentów.

Jeśli chcesz obsługiwać setki lub tysiące agentów, możesz wdrożyć coś takiego jak tłumy Continuum. Zobacz to badanie: http://grail.cs.washington.edu/projects/crowd-flows/ Omówienie metody opartej wyłącznie na procesorze, która może obsługiwać tysiące aktorów w środowisku dynamicznym.

Jeśli chcesz obsługiwać dziesiątki tysięcy lub setki tysięcy agentów, możesz zaimplementować coś takiego, jak tłumy Continuum, z pomocą GPU. Zobacz tutaj odpowiednie badania: https://a248.e.akamai.net/f/674/9206/0/www2.ati.com/misc/siggraph_asia_08/GPUCrowdSimulation_SLIDES.pdf

Oto wideo pokazujące ciągłe tłumy w akcji: http://www.youtube.com/watch?v=lGOvYyJ6r1c (Przejdź do 4:10, aby zobaczyć duże dynamiczne przeszkody, takie jak samochody i światła stop, które dotykają setek ludzi spacerujących po mieście).

— Olhovsky
źródło

Dzięki za linki. D * Lite wydaje się być zgodny z tym, co czytałem

— Andrei

Czy spojrzałeś na proste zachowania kierownicze?

http://www.red3d.com/cwr/steer/

Możesz użyć ich do zejścia ze ścieżki A * w celu uniknięcia lokalnych przeszkód, a następnie po powrocie na swoją drogę.

Całkiem łatwo jest łączyć wiele zachowań.

— BigSandwich
źródło

+1. Nie jestem pewien, dlaczego to zostało odrzucone. Chociaż jest to prosta i być może nie odpowiedź, której szukał

— pytający

Przeczytałem i wdrożyłem to zachowanie w sterowaniu w naszej najnowszej grze. Teraz zamierzamy go ponownie zastąpić innymi metodami. Myślę, że to nie działa dobrze z założonymi optymalnymi ścieżkami. „Połączenie” wielu zachowań zwykle daje złe wyniki. Jeśli nadal zamierzasz go używać, nie próbuj jednocześnie kierować i podążać swoją ścieżką. Zamiast tego przełącz się na sterowanie 100% i przełącz 100% wstecz, gdy miniesz przeszkodę.

— Imi

Ponieważ Twój post jest w „Game Development” część wymiany stosu, tutaj jest to, co większość programista gier odpowie wam: Tu nie chodzi o Real Time Dynamiczny Pathfinding, chodzi o Real Time Dynamiczny Path * następującym *!

Niektóre przypadki krawędzi, w których krawędź na twoim wykresie nawigacyjnym jest całkowicie zasłonięta, wymagałyby od pathfinder ponownego obliczenia innej ścieżki, ale przez większość czasu możesz po prostu kierować swoje istoty wokół przeszkód, przewidywać pozycję i unikać we właściwym kierunku. W przypadku większości gier byłoby zbyt ciężkie, aby z czasem przewidzieć pozycję agentów dynamicznych, zwłaszcza że nie można dokładnie przewidzieć działań gracza ani decyzji agenta.

Radzę więc zacząć od wdrożenia zachowań sterujących (http://red3d.com/cwr/steer/), obsłużyć przypadki, w których ścieżka staje się niemożliwa, a następnie dodać warstwę nad nią, aby obsłużyć przypadki krawędzi, które nie są obsługiwane przez dwa poprzednie rozwiązania.

Mam nadzieję że to pomoże

— emartel
źródło

O nie. „Ścieżka podążająca” to to samo, co wyszukiwanie ścieżki. Istnieje wiele podejść, które umożliwiają śledzenie w czasie rzeczywistym tysięcy agentów, gdy zmieniają się przeszkody, na komputerze stacjonarnym. Z pewnością znalezienie drogi dla jednego agenta nie jest zbyt drogie , gdy poruszają się przeszkody. Oto jeden z takich podejść, z wielu: grail.cs.washington.edu/projects/crowd-flows GPU accellerated wersje ciągłych tłumów istnieje.

— Olhovsky

Musiałbym się z tym nie zgodzić. Każdy silnik traktuje wyszukiwanie i podążanie ścieżką jako dwa odrębne problemy, przy czym pierwszy z nich polega na przeszukiwaniu wykresu obszaru żeglownego, a drugi na poszukiwaniu optymalnego wektora ruchu w przestrzeni lokalnej. Pracowałem nad taką symulacją tłumu, produkującą oprogramowanie pośrednie używane w grach AAA, bez konieczności polegania na GPU. Większość implementacji wykorzystuje pole przepływu (pathfinder) i sterowanie, aby podążać za przepływem i unikać innych agentów (pathfollower). Jak stwierdziła moja odpowiedź, jest to odpowiedź „programisty gier”, a nie odpowiedź akademicka.

— emartel

Wiem, że nie potrzebujesz procesora graficznego dla tłumów, dlatego połączyłem wersję opartą na procesorze. Twój opis podążania ścieżką jest wciąż wyszukiwaniem ścieżki, jest to po prostu wyszukiwanie ścieżki na innym poziomie szczegółowości, na innym zbiorze danych. Tak naprawdę to, co naprawdę masz, to ścieżka do detalu ścieżki i drobna ścieżka do detalu. W końcu próbujesz znaleźć ścieżkę, którą powinien podążać aktor. Wymyślanie nowych terminów po prostu myli rzeczy.

— Olhovsky

Przykro mi, ale „ścieżka podążania” nie jest wymysłem wymyślonym. Przeczytaj dokumenty wyprodukowane w branży, a zobaczysz, że są one używane w kółko: połącz lub połącz tylko kilka. Niestety nie mogę połączyć Cię z dokumentacją chronioną przez NDA silników / pośredników szeroko stosowanych w branży.

— emartel

Twój pierwszy link to link, który podałem w odpowiedzi btw. W porządku, może być sprawiedliwe opisanie tego rodzaju znalezienia ścieżki jako ścieżki podążającej. Ostatecznie oboje próbują znaleźć ścieżkę, którą należy podążać, ale myślę, że w tym przypadku się mylę i powinniśmy nazwać to, co widzimy w twoim drugim łączu, ścieżką podążającą. Np. Czynność łączenia gruboziarnistych punktów ścieżki z sześciennymi splies / krzywymi biezera / insert-your-method-tutaj. To powiedziawszy, nadal zdecydowanie nie zgadzam się z tym, że nie jest możliwe wdrożenie wyszukiwania ścieżek wokół dynamicznych przeszkód, jak sugeruje twoja odpowiedź.

— Olhovsky