Parallel ripple search - scalable and efficient pathfinding for multi-core architectures

Game developers are often faced with very demanding requirements on huge numbers of agents moving naturally through increasingly large and detailed virtual worlds. With the advent of multi-core architectures, new approaches to accelerate expensive pathfinding operations are worth being investigated. Traditional single-processor pathfinding strategies, such as A* and its derivatives, have been long praised for their flexibility. We implemented several parallel versions of such algorithms to analyze their intrinsic behavior, concluding that they either have a large overhead, yield far from optimal paths, do not scale up to many cores, or are cache unfriendly. In this paper we propose Parallel Ripple Search, a novel parallel pathfinding algorithm that largely solves these limitations. It utilizes a high-level graph to assign local search areas to CPU cores at 'equidistant' intervals. These cores then use A* flooding behavior to expand towards each other, yielding good 'guesstimate points' at border touch on. The process does not rely on expensive parallel programming synchronization locks, but instead relies on the opportunistic use of node collisions among cooperating cores, exploiting the multi-core's shared memory architecture. As a result, all cores effectively run at full speed until enough waypoints are found. We show that this approach is a fast, practical and scalable solution, and that it flexibly handles dynamic obstacles in a natural way.

@InProceedings { BB11a,
  author       = "Brand, Sandy and Bidarra, Rafael",
  title        = "Parallel ripple search - scalable and efficient pathfinding for multi-core architectures",
  booktitle    = "Motion in Games. LNCS 7060, Proceedings of MIG'11 - 3rd International Workshop on Motion in Games",
  pages        = "290-303",
  month        = "nov",
  year         = "2011",
  editor       = "Allbeck, JM and Faloutsos, P",
  publisher    = "Springer",
  address      = "Edinburgh, UK",
  url          = "http://graphics.tudelft.nl/Publications-new/2011/BB11a"
}