Research Output

Collaborative diffusion on the GPU for path-finding in games.

  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.

  • Publication Status:


  • Publisher


  • DOI:


  • Library of Congress:

    QA76 Computer software

  • Dewey Decimal Classification:

    006.3 Artificial intelligence


McMillan, C., Hart, E. & Chalmers, K. (2014). Collaborative diffusion on the GPU for path-finding in games. In Mora, A. M. & Squillero, G. (Eds.). Applications of Evolutionary Computation, 418-429. doi:10.1007/978-3-319-16549-3_34. ISBN 978-3-319-16548-6



GPU; Collaborative diffusion; Path-finding; Parallel; Games

Monthly Views:

Available Documents