An Optimal Any-Angle Pathfinding Algorithm

Abstract

Any-angle pathfinding is a common problem from robotics and computer games: it requires finding a Euclidean shortest path between a pair of points in a grid map. Prior research has focused on approximate online solutions. A number of exact methods exist but they all require supra-linear space and preprocessing time. In this paper we describe Anya: a new optimal any-angle pathfinding algorithm which searches over sets of states represented as intervals. Each interval is identified online. From each we select a representative point to derive a corresponding f-value for the set. Anya always returns an optimal path. Moreover it does so entirely online, without any preprocessing or memory overheads. This result answers an open question from the areas of Artificial Intelligence and Game Development: is there an any-angle pathfinding algorithm which is online and optimal? The answer is yes.