13
\$\begingroup\$

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.

\$\endgroup\$

1 Answer 1

8
\$\begingroup\$

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 ;) ).

\$\endgroup\$
2
  • \$\begingroup\$ Those are fantastic references, thanks! I can handle some academic information now and again. I don't have a game in mind for using this yet, but I like the idea of prototyping it. I'll be sure to document my progress. \$\endgroup\$
    – Keeblebrox
    Commented Jun 13, 2011 at 17:30
  • \$\begingroup\$ Awesome, I'm very curious to how it will work. \$\endgroup\$
    – Roy T.
    Commented Jun 13, 2011 at 18:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .