Is nVidia's CUDA suited to performing pathfinding calculations?

Question

I want to know if it would be worth executing pathfinding on the GPU (using nVidia's CUDA, or an equivalent) in certain situations, or whether it would be a wasted effort. The situation I imagine would be a headless multiplayer server responsible for finding paths for bots.

I'm specifically interested in A* pathfinding using navigation meshes, but if there is another pathfinding algorithm that would benefit more from GPU execution I'd love to hear it.

Answer 1

Path finding is essentially a graph problem, in which a lot of parallelism takes place. There are a lot of papers out there on how to implement and optimize graph based algorithms for CUDA.

I found some papers that might interest you (although these are quite academic):
http://cvit.iiit.ac.in/papers/Pawan07accelerating.pdf
http://ppl.stanford.edu/papers/ppopp070a-hong.pdf

So short answer: yes :).

However I don't know if the hassle of writing an A* CUDA implementation together with the overhead of calls to a headless server is going to make this worthwile. Be sure to just make a small prototype first! (Also this would make for an interesting blog post, so be sure to write up what you're doing ;) ).