Collaborative Diffusion on the GPU for Path-Finding in Games

McMillan, C., Hart, E., Chalmers, K. (2015). Collaborative Diffusion on the GPU for Path-Finding in Games. In: (Ed.) 18th European Conference, EvoApplications 2015, Copenhagen, Denmark, April 8-10, 2015, Proceedings, , () ( ed.). (pp. ). : . .


ISBN: 978-3-319-16548-6
ISSN: 0302-9743

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.
[Read More]

Authors

Kevin Chalmers
Senior Lecturer
k.chalmers@napier.ac.uk
+44 131 455 2484
Craig McMillan
Resarch Student
c.mcmillan@napier.ac.uk
+44 131 455
Emma Hart
Director of CEC
e.hart@napier.ac.uk
+44 131 455 2783

Areas of Expertise

Bio-inspired Computing
The Bio-Inspired Algorithms group within the Centre for Algorithms, Visualisation and Evolving Systems is a large and thriving group with interests in nature-inspired computing that include Evolutionary Computing, Hyper-Heuristics, Artificial Immune Systems and Swarm Intelligence.

Associated Projects