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ć.
Odpowiedzi:
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;)).