Pathfinding on GPU?

[agentx]

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.

[Stan`]

That's nice =D But what will happen on people using Intel Graphics ?

[Ykkrosh]

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