1. Docs
  2. /
  3. Pathfinding
  4. /
  5. Jump Point Search

Jump Point Search

Jump Point Search pathfinding algorithm — interactive grid visualization, pseudocode in five languages, and complexity reference.

Time O((V + E) log V) typical Unweighted Heuristic Informed

Implementation

function jpsPathfind(grid, start, end, allowDiag = true) {
  const rows = grid.length;
  const cols = grid[0].length;
  const h = allowDiag ? HEURISTICS.octile : HEURISTICS.manhattan;
  const rootDirections = allowDiag ? DIRS_8 : DIRS_4;
  const gScore = Matrix(rows, cols, Infinity);
  const prev = new Map();
  const visited = new Set();
  const open = PriorityQueue("f");
  function blocked(r, c) {
    return !inBounds(rows, cols, r, c) || grid[r][c] === WALL;
  }
  function jump(r, c, dr, dc, gCost) {
    const nr = r + dr;
    const nc = c + dc;
    if (blocked(nr, nc)) return null;
    const step = dr !== 0 && dc !== 0 ? Math.SQRT2 : 1;
    const ng = gCost + step;
    if (nr === end[0] && nc === end[1]) return {
      r: nr,
      c: nc,
      g: ng
    };
    visitNode(nr, nc);
    if (!allowDiag) {
      if (dr !== 0) {
        if (blocked(nr, nc - 1) && !blocked(nr + dr, nc - 1) || blocked(nr, nc + 1) && !blocked(nr + dr, nc + 1)) {
          return {
            r: nr,
            c: nc,
            g: ng
          };
        }
      } else if (blocked(nr - 1, nc) && !blocked(nr - 1, nc + dc) || blocked(nr + 1, nc) && !blocked(nr + 1, nc + dc)) {
        return {
          r: nr,
          c: nc,
          g: ng
        };
      }
      if (blocked(nr + dr, nc + dc)) {
        return {
          r: nr,
          c: nc,
          g: ng
        };
      }
      return jump(nr, nc, dr, dc, ng);
    }
    if (dr !== 0 && dc !== 0) {
      if (!blocked(nr - dr, nc + dc) && blocked(nr - dr, nc) || !blocked(nr + dr, nc - dc) && blocked(nr, nc - dc)) {
        return {
          r: nr,
          c: nc,
          g: ng
        };
      }
      const j1 = jump(nr, nc, dr, 0, ng);
      if (j1) return {
        r: nr,
        c: nc,
        g: ng
      };
      const j2 = jump(nr, nc, 0, dc, ng);
      if (j2) return {
        r: nr,
        c: nc,
        g: ng
      };
    } else if (dr !== 0) {
      if (!blocked(nr + dr, nc + 1) && blocked(nr, nc + 1) || !blocked(nr + dr, nc - 1) && blocked(nr, nc - 1)) {
        return {
          r: nr,
          c: nc,
          g: ng
        };
      }
    } else if (!blocked(nr + 1, nc + dc) && blocked(nr + 1, nc) || !blocked(nr - 1, nc + dc) && blocked(nr - 1, nc)) {
      return {
        r: nr,
        c: nc,
        g: ng
      };
    }
    return jump(nr, nc, dr, dc, ng);
  }
  function neighborsWithPruning(r, c, parent) {
    if (!parent) return rootDirections;
    const dirs = [];
    const __pattern1 = parent;
    const pr = __pattern1[0];
    const pc = __pattern1[1];
    const dr = Math.sign(r - pr);
    const dc = Math.sign(c - pc);
    if (!allowDiag) {
      return DIRS_4;
    }
    if (dr !== 0 && dc !== 0) {
      dirs.push([dr, dc], [dr, 0], [0, dc]);
      if (!blocked(r - dr, c + dc)) dirs.push([-dr, dc]);
      if (!blocked(r + dr, c - dc)) dirs.push([dr, -dc]);
    } else if (dr !== 0) {
      dirs.push([dr, 0], [dr, 1], [dr, -1]);
    } else {
      dirs.push([0, dc], [1, dc], [-1, dc]);
    }
    return dirs;
  }
  gScore[start[0]][start[1]] = 0;
  priorityQueuePush(open, {
    f: h(start[0], start[1], end[0], end[1]),
    r: start[0],
    c: start[1],
    parent: null
  });
  while (priorityQueueSize(open)) {
    const __pattern2 = priorityQueuePop(open);
    const r = __pattern2.r;
    const c = __pattern2.c;
    const parent = __pattern2.parent;
    const currentKey = key(r, c);
    if (visited.has(currentKey)) continue;
    visited.add(currentKey);
    visitNode(r, c);
    if (r === end[0] && c === end[1]) {
      reconstructPath(prev, start, end);
      return;
    }
    for (const [dr, dc] of neighborsWithPruning(r, c, parent)) {
      const jp = jump(r, c, dr, dc, gScore[r][c]);
      if (!jp) continue;
      const jumpKey = key(jp.r, jp.c);
      const tentative = gScore[r][c] + Math.hypot(jp.r - r, jp.c - c);
      if (tentative < gScore[jp.r][jp.c]) {
        gScore[jp.r][jp.c] = tentative;
        prev.set(jumpKey, [r, c]);
        priorityQueuePush(open, {
          f: tentative + h(jp.r, jp.c, end[0], end[1]),
          r: jp.r,
          c: jp.c,
          parent: [r, c]
        });
        pushFrontier(jp.r, jp.c);
      }
    }
  }
  reportNoPath();
}