# Reducing Redundant Work in Jump Point Search

arXiv: https://arxiv.org/abs/2306.15928 · HTML: https://mlsanity.com/paper/2306.15928/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 0 of its 15 references that are in the map.
- First posted on arXiv 28 Jun 2023.

## Abstract (arXiv)

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.