Czy CUDA nVidii nadaje się do wykonywania obliczeń szukania ścieżki?

13

Chcę wiedzieć , czy w niektórych sytuacjach warto wykonywać wyszukiwanie ścieżek na GPU (używając CUDA nVidii lub równoważnego), czy też byłby to zmarnowany wysiłek. Wyobrażam sobie, że byłby to bezgłowy serwer dla wielu graczy odpowiedzialny za znajdowanie ścieżek dla botów.

Szczególnie interesuje mnie wyszukiwanie ścieżek A * za pomocą siatek nawigacyjnych, ale jeśli istnieje inny algorytm wyszukiwania ścieżek, który przyniósłby więcej korzyści z wykonania GPU, chciałbym go usłyszeć.

performance path-finding gpu gpgpu Keeblebrox
źródło

Odpowiedzi:

8

Znalezienie ścieżki jest zasadniczo problemem graficznym, w którym zachodzi wiele równoległości. Istnieje wiele artykułów na temat wdrażania i optymalizacji algorytmów graficznych dla CUDA.

Znalazłem kilka dokumentów, które mogą Cię zainteresować (choć są to dość akademickie):
http://cvit.iiit.ac.in/papers/Pawan07accelerating.pdf
http://ppl.stanford.edu/papers/ppopp070a-hong.pdf

Tak krótka odpowiedź: tak :).

Nie wiem jednak, czy kłopot związany z pisaniem implementacji A * CUDA wraz z narzutem wywołań serwera bezgłowego sprawi, że będzie to warte zachodu. Pamiętaj, aby najpierw zrobić mały prototyp! (Byłoby to również interesujący post na blogu, więc pamiętaj, aby napisać, co robisz;)).

Roy T.
źródło
To fantastyczne referencje, dzięki! Potrafię od czasu do czasu obsługiwać niektóre informacje akademickie. Nie mam jeszcze zamiaru używać tej gry, ale podoba mi się pomysł jej prototypowania. Z pewnością udokumentuję moje postępy.
Keeblebrox
Świetnie, jestem bardzo ciekawy, jak to będzie działać.
Roy T.