Comparison of Pathfinding Algorithms Using the GPGPU

McMillan, C. (2014). Comparison of Pathfinding Algorithms Using the GPGPU (BEng (Hons) Games Development Dissertation). Edinburgh Napier University (Hart, E., Urquhart, N.).


ISBN:
ISSN:

Abstract

AI algorithms are one of the last areas within a typical game engine to exploit
the relatively new and emerging hardware of the GPGPU, with pathfinding algorithms being a core aspect within many games, developers need to harness
the power of this extremely powerful parallel processor to create better experiences for their players.

This dissertation documents the research, design, implementation and evaluation
of two pathfinding algorithms running on the GPGPU using the CUDA platform. We aim to identify which algorithms are suitable for a GPGPU implementation and attempt to identify what factors effect the parallelization of these algorithms.

We look at a number of parallel systems and GPGPU frameworks along with a number of pathfinding algorithms which have been used within games. We investigate previous attempts at parallelizing these algorithms using the
GPGPU and identify that collaborative diffusion and Dijkstra may be suitable
for a GPGPU implementation based upon this work.

A detailed analysis of the CUDA architecture is provided outlining the execution
and syntax of CUDA kernel functions and the advantages of using the current Kepler architecture with the introduction of dynamic parallelism. We also discuss the maps that each algorithm will be tested against and the metrics which will be recorded.

The implementation provides a detailed description of the sequential and parallel implementations of the algorithms and highlights the challenges encountered when parallelizing the algorithms.

Analysing the results we were able to draw a number of conclusions; We found that both collaborative diffusion and Dijkstra can be parallelized using the GPGPU resulting in speed ups over their sequential versions and that the degree to which terrain costs vary within the map can increase the time taken to find a path within the parallel versions of both algorithms.
[Read More]

Authors

Craig McMillan
Resarch Student
c.mcmillan@napier.ac.uk
+44 131 455

Areas of Expertise

Associated Projects