Using GPU to accelrate pathfinding/AI in games? ... wondering...

I’m wondering if anyone out there can give me info on this, supreme commander for instance spawns lots of threads and bogs down supremely with many AI’s. had an idea that it’d be interesting to see if the GPU could make unit pathfinding a lot faster and cleaner then core 2 duo’s and quads. Since with the rate video cards are speeding along. It would may be pretty soon that they can ‘just do it better’.

I think this would be worth looking into @ nvidia because if so it could speed up certain games and other semi-related disciplines dealing with the same problem domains tremendously.

If anyone has any info let me know…

As you probably know, path finding requires checking for collision between the object in question and the rest of the scene (other moveable objects and the static scenery).

In order to find a collision free path from a start point to your desired location, you (depending on the scene complexity and path planning algorithm) end up doing a lot of queries to your collision detection system.

For the applications I’m involved in (automatic motion planning for industrial robots), the collision detection takes a lot of time due to the many degrees of freedom for the robot, the complexities of the scene geometries and the precision required.

Games are usually less complicated to do collision detection on due to reduced accuracy, simplified bounding volumes for geometries and so on, but with many concurrently moving objects and hard constraints on the running time (The need to keep 60+ FPS) it’s still a challenge.

I’m currently working on parallelizing a commonly used scheme in collision detection (OBBTree) on CUDA. If you want to know more about this, let me know.

The path planning algorithm used for the game you mention is probably based on the PRM method (see…/overmars.html) and some real-time queries for the objects. Try to search more and this and see what you can find on parallelism