¿El CUDA de nVidia es adecuado para realizar cálculos de búsqueda de ruta?

13

Quiero saber si valdría la pena ejecutar pathfinding en la GPU (usando CUDA de nVidia , o un equivalente) en ciertas situaciones, o si sería un esfuerzo inútil. La situación que imagino sería un servidor multijugador sin cabeza responsable de encontrar rutas para bots.

Estoy específicamente interesado en la búsqueda de rutas A * utilizando mallas de navegación, pero si hay otro algoritmo de búsqueda de rutas que se beneficiaría más de la ejecución de la GPU, me encantaría escucharlo.

performance path-finding gpu gpgpu Keeblebrox
fuente

Respuestas:

8

La búsqueda de rutas es esencialmente un problema gráfico, en el que se produce un gran paralelismo. Existen muchos documentos sobre cómo implementar y optimizar algoritmos basados ​​en gráficos para CUDA.

Encontré algunos documentos que podrían interesarle (aunque estos son bastante académicos):
http://cvit.iiit.ac.in/papers/Pawan07accelerating.pdf
http://ppl.stanford.edu/papers/ppopp070a-hong.pdf

Tan breve respuesta: sí :).

Sin embargo, no sé si la molestia de escribir una implementación A * CUDA junto con la sobrecarga de llamadas a un servidor sin cabeza va a hacer que esto valga la pena. ¡Asegúrate de hacer primero un pequeño prototipo! (Además, esto sería una publicación de blog interesante, así que asegúrese de escribir lo que está haciendo;)).

Roy T.
fuente
Esas son referencias fantásticas, gracias! Puedo manejar alguna información académica de vez en cuando. Todavía no tengo un juego en mente para usar esto, pero me gusta la idea de crear un prototipo. Me aseguraré de documentar mi progreso.
Keeblebrox
Impresionante, tengo mucha curiosidad sobre cómo funcionará.
Roy T.