Apakah CUDA nVidia cocok untuk melakukan perhitungan pathfinding?

13

Saya ingin tahu apakah akan layak melakukan pathfinding pada GPU (menggunakan CUDA nVidia , atau yang setara) dalam situasi tertentu, atau apakah itu akan menjadi usaha yang sia-sia. Situasi yang saya bayangkan adalah server multiplayer tanpa kepala yang bertanggung jawab untuk menemukan jalur bot.

Saya secara khusus tertarik pada pathfinding A * menggunakan mesh navigasi, tetapi jika ada algoritma pathfinding lain yang akan mendapat manfaat lebih dari eksekusi GPU saya ingin mendengarnya.

performance path-finding gpu gpgpu Keeblebrox
sumber

Jawaban:

8

Menemukan jalan pada dasarnya adalah masalah grafik, di mana banyak paralelisme terjadi. Ada banyak makalah di luar sana tentang bagaimana menerapkan dan mengoptimalkan algoritma berbasis grafik untuk CUDA.

Saya menemukan beberapa makalah yang mungkin menarik bagi Anda (meskipun ini cukup akademis):
http://cvit.iiit.ac.in/papers/Pawan07accelerating.pdf
http://ppl.stanford.edu/papers/ppopp070a-hong.pdf

Jadi jawaban singkatnya: ya :).

Namun saya tidak tahu apakah kerumitan menulis implementasi A * CUDA bersama dengan overhead panggilan ke server tanpa kepala akan membuat ini sia-sia. Pastikan untuk membuat prototipe kecil terlebih dahulu! (Juga ini akan membuat posting blog yang menarik, jadi pastikan untuk menulis apa yang Anda lakukan;)).

Roy T.
sumber
Itu referensi yang fantastis, terima kasih! Saya dapat menangani beberapa informasi akademik sekarang dan lagi. Saya belum memiliki game dalam pikiran untuk menggunakan ini, tapi saya suka ide membuat prototipe itu. Saya pasti akan mendokumentasikan kemajuan saya.
Keeblebrox
Luar biasa, saya sangat ingin tahu bagaimana cara kerjanya.
Roy T.