Parallel Ripple Search – Scalable and Efficient Pathfinding for Multi-core Architectures

Abstract. 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 ap-proaches to accelerate expensive pathfinding operations are worth being inves-tigated. Traditional single-processor pathfinding strategies, such as A * and its derivatives, have been long praised for their flexibility. We implemented sever-al parallel versions of such algorithms to analyze their intrinsic behavior, con-cluding 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 nod