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.


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):

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

  • \$\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 Jun 13 '11 at 17:30
  • \$\begingroup\$ Awesome, I'm very curious to how it will work. \$\endgroup\$ – Roy T. Jun 13 '11 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.