Ist die CUDA von nVidia für die Durchführung von Pfadfindungsberechnungen geeignet?

13

Ich möchte wissen, ob es sich lohnen würde, in bestimmten Situationen eine Pfadfindung auf der GPU durchzuführen (mit nVidias CUDA oder einem vergleichbaren Programm), oder ob dies eine Verschwendung wäre. Die Situation, die ich mir vorstelle, wäre ein kopfloser Multiplayer-Server, der dafür verantwortlich ist, Pfade für Bots zu finden.

Ich interessiere mich speziell für die A * -Pfadfindung mithilfe von Navigationsnetzen, aber wenn es einen anderen Pfadfindungsalgorithmus gibt, der mehr von der GPU-Ausführung profitiert, würde ich es gerne hören.

Keeblebrox
quelle

Antworten:

8

Das Auffinden von Pfaden ist im Wesentlichen ein Graphproblem, bei dem viel Parallelität stattfindet. Es gibt viele Artikel darüber, wie grafische Algorithmen für CUDA implementiert und optimiert werden können.

Ich habe einige Artikel gefunden, die Sie interessieren könnten (obwohl diese sehr akademisch sind):
http://cvit.iiit.ac.in/papers/Pawan07accelerating.pdf
http://ppl.stanford.edu/papers/ppopp070a-hong.pdf

Also kurze Antwort: ja :).

Ich weiß jedoch nicht, ob sich die Mühe, eine A * CUDA-Implementierung zusammen mit dem Overhead der Aufrufe eines Headless-Servers zu schreiben, lohnen wird. Stellen Sie sicher, dass Sie zuerst einen kleinen Prototyp erstellen! (Auch dies würde zu einem interessanten Blog-Beitrag führen, schreiben Sie also auf jeden Fall auf, was Sie tun;)).

Roy T.
quelle
Das sind fantastische Referenzen, danke! Ab und zu kann ich mit akademischen Informationen umgehen. Ich habe noch kein Spiel dafür im Sinn, aber ich mag die Idee, es als Prototyp zu entwickeln. Ich werde sicher meine Fortschritte dokumentieren.
Keeblebrox
Super, ich bin sehr gespannt, wie es funktionieren wird.
Roy T.