Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 7 down vote accepted

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

share|improve this answer
    
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. –  Keeblebrox Jun 13 '11 at 17:30
    
Awesome, I'm very curious to how it will work. –  Roy T. Jun 13 '11 at 18:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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