Autor Wątek: Pathfinding + dynamiczne obiekty  (Przeczytany 3518 razy)

Offline Rogus

  • Użytkownik

# Maj 15, 2013, 18:55:36
Witam.
Szukam już jakiś czas odpowiedzi na pytanie co zrobić z pathfindingiem gdy mamy dynamiczne obiekty i niespecjalnie mogę znaleźć na to odpowiedź. Mam sobie wygenerowanego pathmesha dla obiektów statycznych i moje boty ładnie poruszają się po świecie natomiast problem pojawia się gdy mam parę botów i się spotkają ponieważ wchodzą na siebie (pathfinding tego nie uwzględnia).  Próbowałem przebudować pathmesha z każdą klatką na osobnym wątku, ale tak jak myślałem... nie wymyślono jeszcze takiego kompa który mógłby to uciągnąć ;) W necie dużo jest o raycastowaniu lecz nie znalazłem odpowiedzi jak to połączyć z pathfindingiem opartym na pathmeshu.  Ok, wyznaczam sobie ścieżkę z A do B lecz na mojej drodze stoi bot. Co teraz? Ray wykrywa przeszkodę i muszę jakoś znaleźć alternatywną ścieżkę. Jakieś podpowiedzi? 

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Meic

  • Użytkownik

# Maj 15, 2013, 20:09:31
Obawiam się, że musisz trochę bardziej pokombinować. Pathfinding ma to do siebie, iż zwraca wynik dopiero po wygenerowaniu całej ścieżki - co za tym idzie, jak sam się przekonałeś, liczenie drogi co klatkę nie wchodzi w grę. Rozwiązanie które osobiście bym sugerował to pomieszanie Pathfindingu z tzw. Movement - poruszaniem się "na żywo", poprzez analizę najbliższego otoczenia i podejmowanie na tej podstawie decyzji. Mam na myśli używanie w ogólnym ujęciu ścieżek, które zostały wygenerowane dla poszczególnych jednostek, a dopiero w szczególnych przypadkach, gdy w pobliżu pojawi się jakiś obiekt mobilny, przerzucanie się na to drugie podejście. Od ciebie już będzie zależeć, czy kolidujące obiekty po wykryciu sąsiada "dogadają się", kto kogo puści, czy np. pójdą na azymut równocześnie próbując ominąć zator (dynamicznie analizując otoczenie). Po wyjściu ze strefy kolizji możesz odszukać najbliższy dla danej jednostki punkt na ścieżce i od tego punktu poruszać się dalej zgodnie z nią.

Offline blejd123

  • Użytkownik

# Maj 15, 2013, 20:17:19
Jest całkiem sporo możliwości:
1. Korzystanie ze ścieżki wygenerowanej normalnie, ale podążanie nią za pomocą steering behaviors (można od razu zrobić to na boidach): http://www.red3d.com/cwr/steer/PathFollow.html
2. Algorytmy:
 - RVO/RVO2 - http://gamma.cs.unc.edu/RVO2/
 - ORCA - podobne do powyższego
3. Możesz wykorzystać mapy wpływów, żeby polepszyć jakoś scieżek, ale i tak będziesz musiał je dosyć często aktualizować.
4. Continuum Crowds/Flowfield Pathfinding - ostatnio zdobywają popularność i na nich oparłem pathfinding w mojej strategii.

Offline Radomiej

  • Użytkownik
    • Blog

# Maj 15, 2013, 20:19:49
Nie możesz to nałożyć na mapę pathfindingu? to może chociaż zapisuj wektor kierunku i potem staraj się jak kol wiek ruszyć w stronę celu/ kolejnego punktu pathfindingu

Offline Rogus

  • Użytkownik

# Maj 15, 2013, 20:33:43
Dzięki za odpowiedzi. Zaraz zaczynam research ;)

Radomiej chyba nie rozumiesz. Pathfinding jest na pathmeshu dla obiektów statycznych i to już jest zrobione. Mnie chodzi o kolidowanie z graczami a aktualizacja pathmesha jest po prostu strasznie kosztowna. Chodzi właśnie o wyznaczenie kolejnego punktu pathfindingu tak by pomiędzy aktualną pozycją gracza a tym punktem nic nie było. A jeśli jest... to co? Postawić punkt nie wiem... 2m obok "kolidowanego agenta", znowu trzeba sprawdzić czy gracz może dojść do nowego punktu, a nie wyznaczony jest np na skale. Co jeśli tam też coś jest? Znów trzeba byłoby przesunąć punkt, ale pytanie gdzie ? :P Jakiś sprytny, mało kosztowny algorytm by się przydał. 

Offline blejd123

  • Użytkownik

# Maj 15, 2013, 20:48:20
Ile obiektów masz na scenie, że wydajność aż tak bardzo spada?

Offline Rogus

  • Użytkownik

# Maj 15, 2013, 20:56:10
Testowałem na sandboxie. Przy 5 obiektach dynamicznych + ok 7 statycznych z 1300 fps spadło 460. To było na pc (i3) natomiast na laptopie to już w ogóle tragedia była...

Z wagami ścieżek będzie problem bo pathfinding wbudowany w silnik chyba tego nie udostępnia.

Edit: Dla 12 obiektów dynamicznych już były ścięcia.
« Ostatnia zmiana: Maj 15, 2013, 20:58:07 wysłana przez Rogus »

Offline Xirdus

  • Redaktor

  • +1
# Maj 15, 2013, 21:11:37
z 1300 fps spadło 460.
Każda wartość powyżej 60FPS jest tak samo dobra.

Offline blejd123

  • Użytkownik

# Maj 15, 2013, 21:29:26
Swoją drogą jakaś niska wydajność tego pathfindingu w tym silniku. W ogóle co to za silnik?

Offline koirat

  • Użytkownik

# Maj 15, 2013, 22:29:33
Pytanie jeszcze czy ten pathfinding działa współbierznie.
Oraz czy punkty testowe były osiągalne czy nie.
Również wielkość przeszukiwanego grafu będzie miała znacznie.
« Ostatnia zmiana: Maj 15, 2013, 22:31:14 wysłana przez koirat »

Offline Rogus

  • Użytkownik

# Maj 15, 2013, 22:41:07
Tu chodzi tylko o generacje pathmesha. Do samego wyszukiwania ścieżek na pregenerowanym pathmeshu nie mam żadnego zastrzeżenia, ale tak jak twórca pisał, nie zaleca regeneracji pathmesha dla worlda w każdej klatce gry. To było tylko dla testu sprawdzenie jak bardzo to obciąży procesor. W esenthelu piszę.

Co do mojego problemu, chyba posłużę się tym http://www.red3d.com/cwr/steer/CrowdPath.html. Zobaczymy co mi z tego wyjdzie.

Offline blejd123

  • Użytkownik

# Maj 15, 2013, 22:48:57
To zdecydowanie pozostaje tylko lokalne unikanie kolizji, inaczej nie będzie się dało tego zrealizować, jeśli wymogiem jest rekalkulacja navmesha.

Offline kamykadze

  • Użytkownik

# Czerwiec 19, 2013, 18:45:10
Sorki, że tak późno odświeżam temat, ale są jeszcze tzw. "algorytmy inkrementacyjne", które szybciej wyszukują ścieżkę w zmieniającym się grafie. Z najbardziej popularnych przykładów przychodzą mi do głowy LPA* oraz D*-Lite.  Gdyby je jeszcze połączyć z jakąś hierarchią wyszukiwania, może efekt byłby zadowalający.