Real-Time Heuristic Search for Pathfinding in Video Games

Game pathfinding is a challenging problem due to a limited amount of per-frame CPU time commonly shared among many simultaneously pathfinding agents. The challenge is rising with each new generation of games due to progressively larger and more complex environments and larger numbers of agents pathfinding in them. Algorithms based on A* tend to scale poorly as they must compute a complete, possibly abstract, path for each agent before the agent can move. Real-time heuristic search algorithms satisfy a constant bound on the amount of planning per move, independent of problem size. These algorithms are thus a promising approach to large scale multi-agent pathfinding in video games. However, until recently, real-time heuristic search algorithms universally exhibited a visually unappealing “scrubbing” behavior by repeatedly revisiting map locations. This had prevented their adoption by video game developers. In this chapter, we review three modern search algorithms which address the “scrubbing” problem in different ways. Each algorithm presentation is complete with an empirical evaluation on game maps.