O CUDA da nVidia é adequado para executar cálculos de busca de caminhos?

13

Quero saber se valeria a pena executar a busca de caminho na GPU (usando o CUDA da nVidia , ou equivalente) em determinadas situações, ou se seria um esforço desperdiçado. A situação que imagino seria um servidor multiplayer sem cabeça responsável por encontrar caminhos para bots.

Estou especificamente interessado em encontrar arquivos A * usando malhas de navegação, mas se houver outro algoritmo que possa se beneficiar mais da execução da GPU, eu adoraria ouvi-lo.

Keeblebrox
fonte

Respostas:

8

A localização de caminhos é essencialmente um problema gráfico, no qual ocorre muito paralelismo. Existem muitos artigos sobre como implementar e otimizar algoritmos baseados em gráficos para o CUDA.

Encontrei alguns artigos que podem interessar a você (embora sejam bastante acadêmicos):
http://cvit.iiit.ac.in/papers/Pawan07accelerating.pdf
http://ppl.stanford.edu/papers/ppopp070a-hong.pdf

Resposta tão curta: sim :).

No entanto, não sei se o incômodo de escrever uma implementação A * CUDA juntamente com a sobrecarga de chamadas para um servidor sem cabeçalho fará com que isso valha a pena. Certifique-se de fazer um pequeno protótipo primeiro! (Além disso, isso tornaria uma postagem interessante no blog, portanto, não deixe de escrever o que você está fazendo;)).

Roy T.
fonte
Essas são referências fantásticas, obrigado! Eu posso lidar com algumas informações acadêmicas de vez em quando. Ainda não tenho um jogo em mente para usá-lo, mas gosto da ideia de criar um protótipo. Certificarei de documentar meu progresso.
Keeblebrox 13/06
Incrível, estou muito curioso para saber como vai funcionar.
Roy T.