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ć?
źródło
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).
źródło
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ń.
źródło
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
źródło