Когда я узнал о JPS, у меня возникла идея упростить A*. Можно выкинуть волновую рекурсию, которая используется во всех алгоритмах поиска пути. Для этого, берем все узлы, которые являются препятствиями, помечаем соседние свободные узлы и строим путь. Из самого описания выходит, что данный алгоритм подойдет не для всех типов графов, но ботам на регулярной сетке в самый раз.

Проблема данного алгоритма в том, что препятствий может быть очень много, а на пути между стартом и финишем очень мало. Фактически это алгоритм Дейкстры без рекурсии, прямой переход в самое последнее возможное состояние. Потребление памяти меньше чем у Дейкстры и А*, т. к. отмечается только финальный фронт.

Чтобы оптимизировать, будем отмечать только те граничные узлы, которые находятся ближе к стартовой и финишной точке. Получаем JPS, только избыточней, но лучше чем A* по потреблению памяти. Остается построить путь поиском в ширину из доступных оптимальных путей.

Вот сравнение по потреблению памяти при обходе препятствий:

A* хранит данные о свободных клетках, полученных на данной эвристике. В эти данные входят координаты точки, расстояние до цели, количество предыдущих шагов.

Jump Point Search хранит точки перехода на пути от старта к финишу, хранятся только координаты точек и по выбору: координаты соседних переходов или расстояние до финиша.

При удалении рекурсии надо хранить координаты граничных точек, а все вычисления производить только при построении пути.

Если найти способ не хранить все доступные граничные точки, то алгоритм без рекурсии вполне годится для практического применения.

JPS в большинстве применений превосходит A*, он быстрее, потребляет меньше памяти. Но не годится для открытых пространств, если регион поиска искусственно не ограничить, он будет вечно искать оптимальный путь, т. к. его преимущество оборачивается недостатком. Возможно эту проблему уже решили, но никакой информации об этом я не нашел.