Le CUDA de nVidia est-il adapté pour effectuer des calculs d'orientation?

13

Je veux savoir si cela vaudrait la peine d'exécuter le pathfinding sur le GPU (en utilisant le CUDA de nVidia , ou un équivalent) dans certaines situations, ou si ce serait un effort inutile. La situation que j'imagine serait un serveur multijoueur sans tête chargé de trouver des chemins pour les bots.

Je suis spécifiquement intéressé par A * pathfinding en utilisant des maillages de navigation, mais s'il existe un autre algorithme de pathfinding qui bénéficierait davantage de l'exécution du GPU, j'aimerais l'entendre.

Keeblebrox
la source

Réponses:

8

La recherche de chemin est essentiellement un problème de graphe, dans lequel beaucoup de parallélisme a lieu. Il existe de nombreux articles sur la façon d'implémenter et d'optimiser des algorithmes basés sur des graphiques pour CUDA.

J'ai trouvé des articles qui pourraient vous intéresser (bien qu'ils soient assez académiques):
http://cvit.iiit.ac.in/papers/Pawan07accelerating.pdf
http://ppl.stanford.edu/papers/ppopp070a-hong.pdf

Donc réponse courte: oui :).

Cependant, je ne sais pas si les tracas de l'écriture d'une implémentation A * CUDA avec les frais généraux des appels vers un serveur sans tête vont rendre cela utile. Assurez-vous de faire d'abord un petit prototype! (Cela rendrait également un article de blog intéressant, alors assurez-vous d'écrire ce que vous faites;)).

Roy T.
la source
Ce sont des références fantastiques, merci! Je peux gérer des informations académiques de temps en temps. Je n'ai pas encore de jeu en tête pour l'utiliser, mais j'aime l'idée de le prototyper. Je serai sûr de documenter mes progrès.
Keeblebrox
Génial, je suis très curieux de savoir comment cela fonctionnera.
Roy T.13