Collaborative Diffusion on the GPU for Path-Finding in Games

Research Output

Exploiting the powerful processing power available on the GPU in many machines, we investigate the performance of parallelised versions of pathfinding algorithms in typical game environments. We describe a parallel implementation of a collaborative diffusion algorithm that is shown to find short paths in real-time across a range of graph sizes and provide a comparison to the well known Dijkstra and A* algorithms. Although some trade-off of cost vs path-length is observed under specific environmental conditions, results show that it is a viable contender for pathfinding in typical real-time game scenarios, freeing up CPU computation for other aspects of game AI.

Date:

17 March 2015
Publication Status:

Published
Publisher

Springer
DOI:

10.1007/978-3-319-16549-3_34
Library of Congress:

QA76 Computer software
Dewey Decimal Classification:

006.3 Artificial intelligence

http://researchrepository.napier.ac.uk/output/173858 <p>McMillan, C., Hart, E., & Chalmers, K. (2015). Collaborative Diffusion on the GPU for Path-Finding in Games. In A. M. Mora, & G. Squillero (Eds.), <i>Applications of Evolutionary Computation; Lecture Notes in Computer Science</i>. , (418-429). https://doi.org/10.1007/978-3-319-16549-3_34</p>

Citation

McMillan, C., Hart, E., & Chalmers, K. (2015). Collaborative Diffusion on the GPU for Path-Finding in Games. In A. M. Mora, & G. Squillero (Eds.), Applications of Evolutionary Computation; Lecture Notes in Computer Science. , (418-429). https://doi.org/10.1007/978-3-319-16549-3_34