Jump point search
Оптимизация A* на равномерных сетках: алгоритм перепрыгивает неинтересные клетки и останавливается только там, где путь действительно может повернуть.
На открытой сетке A* впустую тратит массу времени на тысячи равноценных клеток — между двумя точками много путей одинаковой длины. Jump point search отсекает эту симметрию: из клетки он «прыгает» в заданном направлении, пока не упрётся в цель, край или так называемую точку прыжка, где препятствие вынуждает выбирать. В очередь попадают только точки прыжка, а не каждый промежуточный шаг.
Метод опубликовали Дэниел Харабор и Албан Грасьен в 2011 году. Он не требует предобработки, возвращает тот же оптимальный путь, что и A*, и на открытой местности часто быстрее на порядок. Ограничение очевидно: нужна сетка с равной стоимостью клеток, а к навигационной сетке или взвешенному графу метод напрямую не применим.