Skip to main content

Research Repository

Advanced Search

Collaborative Diffusion on the GPU for Path-Finding in Games

McMillan, Craig; Hart, Emma; Chalmers, Kevin

Authors

Craig McMillan

Kevin Chalmers



Contributors

Antonio M Mora
Editor

Giovanni Squillero
Editor

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.

Presentation Conference Type Conference Paper (Published)
Conference Name EvoApplications 2015 European Conference on the Applications of Evolutionary Computation
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
Contract Date May 15, 2017

Files







You might also like



Downloadable Citations