Hierarchical pathfinding in computer games

Jana Harvanová

Supervisor: RNDr. Jozef Šiška, PhD.

Introduction:
Maps in computer games are often too large to allow simple use of A* because of performance issues. This led to development of hierarchical approaches which try to find paths using an abstraction of the original map, but in doing so, can introduce errors. Various approaches (such as HPA* or Contraction hierarchies) have different properties and are applicable on different problems. Furthermore, the problem is harder in games with non-grid maps, where different approaches to map pre-processing nad graph generation further influence the properties of the selected algorithms(i.e Delaunay Triangulation).

Aim:

Mail: janka.harvanova@gmail.com

Work structure

Sources

  • [1] Bobby Anguelov. Video Game Pathfinding and Improvements to Discrete Search on Grid-based Maps(2011)
  • [2] Amitha Arun. Pathfinding Algorithms in Multi-Agent Systems(2014).
  • [3] Adi Botea, Martin Muller, and Jonathan Schaeffer. Near Optimal Hierarchical Path-Finding, Journal of Game Development, Volume 1(2004).
  • [4] Adi Botea et al. Pathfinding in Games(2013).
  • [5] K. Chen. “Robust Dynamic Constrained Delaunay Triangulation for Pathfinding.” In: (2009).
  • [6] Xiao Cui and Hao Shi. A*-based Pathfinding in Modern Computer Games, IJCSNS International Journal of Computer Science and Network Security,VOL.11 No.1 (2011).
  • [7] Alex Kring, Alex J. Champandard, and Nick Samarin. DHPA* and SHPA*: Efficient Hierarchical Pathfinding in Dynamic and Static Game Worlds (2010).
  • [8] Marc Lanctot, Nicolas Ng Man Sun, and Clark Verbrugge. Path-finding for Large Scale Multiplayer Computer Games(2006).
  • [9] William Lee and Ramon Lawrence. Fast Grid-based Path Finding for Video Games(2013).
  • [10] Parth Mehta et al. A Review on Algorithms for Pathfinding in Computer Games(2016).
  • [11] Steve Rabin and Nathan R. Sturtevant. Pathfinding Architecture Optimizations. (2013).
  • [12] Nathan Sturtevant and Michael Buro. Partial Pathfinding Using Map Abstrac- tion and Refinement(2005)
  • [13] Nathan R. Sturtevant. Benchmarks for Grid-Based Pathfinding. In: (2012).
  • [14] Nathan R. Sturtevant. Choosing a Search Space Representation.(2013). url:
  • [15] Nathan R. Sturtevant. Memory-Efficient Abstractions for Pathfinding“”.(2007).
  • Prototype

    Download a Ful Prototype including thesis and source code here