Skip to main content

Research Repository

Advanced Search

Collaborative Diffusion on the GPU for Path-Finding in Games

McMillan, Craig; Hart, Emma; Chalmers, Kevin


Craig McMillan

Kevin Chalmers


Antonio M Mora

Giovanni Squillero


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
Keywords GPU; Collaborative diffusion; Path-finding; Parallel; Games
Public URL
Publisher URL
Contract Date May 15, 2017


You might also like

Downloadable Citations