Reducing Redundant Work in Jump Point Search
This addresses inefficiencies in JPS for online navigation in games and dynamic environments, representing an incremental improvement.
The paper tackled the problem of redundant work and suboptimal node expansion in Jump Point Search (JPS), a grid-based pathfinding algorithm, by proposing Constrained JPS (CJPS), which reduced runtime by up to 7x in large maps and 14x in pathological cases.
JPS (Jump Point Search) is a state-of-the-art optimal algorithm for online grid-based pathfinding. Widely used in games and other navigation scenarios, JPS nevertheless can exhibit pathological behaviours which are not well studied: (i) it may repeatedly scan the same area of the map to find successors; (ii) it may generate and expand suboptimal search nodes. In this work, we examine the source of these pathological behaviours, show how they can occur in practice, and propose a purely online approach, called Constrained JPS (CJPS), to tackle them efficiently. Experimental results show that CJPS has low overheads and is often faster than JPS in dynamically changing grid environments: by up to 7x in large game maps and up to 14x in pathological scenarios.