Jump to content

Pathfinding on GPU?

Recommended Posts

Just came across this article of a guy doing pathfinding with WebGL, which is slow because getting the texture back is only supported pixel by pixel. However, his Game of Live using same architecture is freaking fast, so OpenGL might support a faster way. If I understand it correctly the algorithm resolves multiple paths requests per call and time only depends on size of map.

Probably the expertise of writing a shader to do pathfinding is quite rare within single mind, but 0AD has shown quite some prolific synergy effects, so I wanted to check if this solution rattles some nerves.

  • Like 1
Link to comment
Share on other sites

There might be ways to use a GPU to implement certain kinds of pathfinding efficiently, but that article is not one - it looks like about the worst possible way you could use a GPU :P. If the maximum path length is N (with maybe N=1000 on our maps), it has to execute N iterations serially, and GPUs are very bad at doing things serially; and each iteration is a separate OpenGL draw call, and draw calls are very expensive. And it's only finding paths to a single destination at once, so you'd need to repeat the whole thing for every independent unit. It would probably be much quicker to just do the computation directly on the CPU (assuming you're not running a poorly-optimised version written in JS on the CPU).

AMD's old Froblins demo used a similar (but more advanced) technique ("Beyond Programmable Shading Slides" on that page gives an overview). So it can work enough for a demo, but the demo has much simpler constraints than a real game (e.g. every unit in the demo has to react exactly the same way to its environment, it can't cope with dozens of different groups all wanting to move towards different destinations) and I doubt it can really scale up in complexity. (Nowadays you'd probably want to use OpenCL instead, so you have more control over memory and looping, which should allow more complex algorithms to be implemented efficiently. But OpenCL introduces a whole new set of problems of its own.)

And performance on Intel GPUs would be terrible anyway, so it's not an option for a game that wants to reach more than just the high-end gamer market.

  • Like 3
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


  • Create New...