Collaborative Diffusion on the GPU for Path-Finding in Games

McMillan, Craig; Hart, Emma; Chalmers, Kevin

Abstract

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.

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

• Conference Name: EvoApplications 2015 European Conference on the Applications of Evolutionary Computation
• Conference Location: Copenhagen
• Start Date: Apr 8, 2015
• End Date: Apr 10, 2015
• Online Publication Date: Mar 17, 2015
• Publication Date: 2015
• Deposit Date: Mar 23, 2015
• Publicly Available Date: May 15, 2017
• Electronic ISSN: 1611-3349
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Pages: 418-429
• Series Title: Lecture Notes in Computer Science
• Series Number: 9028
• Series ISSN: 0302-9743
• Book Title: Applications of Evolutionary Computation; Lecture Notes in Computer Science
• ISBN: 9783319165486; 9783319165493
• DOI: https://doi.org/10.1007/978-3-319-16549-3_34
• Keywords: GPU; Collaborative diffusion; Path-finding; Parallel; Games
• Public URL: http://researchrepository.napier.ac.uk/id/eprint/7684
• Publisher URL: http://dx.doi.org/10.1007/978-3-319-16549-3_34