js写一个jps算法

JPS算法（Jump Point Search）是一种基于A*算法的优化算法，用于解决地图路径规划问题。它的主要优势在于通过对地图进行预处理，可以有效减少搜索空间，提高搜索效率。

以下是使用JavaScript实现的JPS算法：

// 定义节点类
class Node {
  constructor(x, y, parent = null) {
    this.x = x;
    this.y = y;
    this.parent = parent;
    this.g = 0;
    this.h = 0;
  }

  // 计算节点的f值
  get f() {
    return this.g + this.h;
  }

  // 估算从当前节点到终点的距离
  estimateDistance(goal) {
    return Math.abs(this.x - goal.x) + Math.abs(this.y - goal.y);
  }

  // 判断当前节点是否为起点
  isStart() {
    return this.parent === null;
  }

  // 判断当前节点是否与父节点在同一直线上
  isStraight(parent) {
    return this.x === parent.x || this.y === parent.y;
  }

  // 判断当前节点是否为障碍物
  isObstacle(grid) {
    return grid[this.y][this.x] === 1;
  }

  // 获取当前节点的邻居节点
  getNeighbors(grid) {
    const neighbors = [];

    // 8个方向
    const directions = [
      [-1, -1],
      [0, -1],
      [1, -1],
      [-1, 0],
      [1, 0],
      [-1, 1],
      [0, 1],
      [1, 1],
    ];

    for (const direction of directions) {
      const [dx, dy] = direction;
      const x = this.x + dx;
      const y = this.y + dy;

      // 判断邻居节点是否越界或为障碍物
      if (
        x < 0 ||
        x >= grid[0].length ||
        y < 0 ||
        y >= grid.length ||
        new Node(x, y).isObstacle(grid)
      ) {
        continue;
      }

      const neighbor = new Node(x, y, this);

      // 对于直线上的邻居节点，跳跃到下一个关键节点
      if (this.isStraight(neighbor.parent)) {
        const dx = x - neighbor.parent.x;
        const dy = y - neighbor.parent.y;
        const nx = x + dx;
        const ny = y + dy;

        if (
          nx >= 0 &&
          nx < grid[0].length &&
          ny >= 0 &&
          ny < grid.length &&
          !new Node(nx, ny).isObstacle(grid)
        ) {
          neighbors.push(new Node(nx, ny, this));
        }
      } else {
        neighbors.push(neighbor);
      }
    }

    return neighbors;
  }

  // 获取从起点到当前节点的路径
  getPath() {
    const path = [];
    let node = this;

    while (node) {
      path.unshift([node.x, node.y]);
      node = node.parent;
    }

    return path;
  }
}

// 定义JPS算法类
class JPS {
  constructor(grid) {
    this.grid = grid;
    this.openList = [];
    this.closedSet = new Set();
  }

  // 寻找路径
  findPath(start, goal) {
    const startNode = new Node(start[0], start[1]);
    const goalNode = new Node(goal[0], goal[1]);
    this.openList.push(startNode);

    while (this.openList.length > 0) {
      // 从openList中选择f值最小的节点
      const currentNode = this.openList.sort((a, b) => a.f - b.f)[0];

      // 到达终点，返回路径
      if (currentNode.x === goalNode.x && currentNode.y === goalNode.y) {
        return currentNode.getPath();
      }

      this.openList = this.openList.filter(
        (node) => node !== currentNode
      );
      this.closedSet.add(currentNode);

      // 扩展邻居节点
      for (const neighbor of currentNode.getNeighbors(this.grid)) {
        if (this.closedSet.has(neighbor)) {
          continue;
        }

        const gScore = currentNode.g + 1;

        if (!this.openList.includes(neighbor)) {
          this.openList.push(neighbor);
        } else if (gScore >= neighbor.g) {
          continue;
        }

        // 更新节点信息
        neighbor.g = gScore;
        neighbor.h = neighbor.estimateDistance(goalNode);
      }
    }

    return null;
  }
}

使用示例：

const grid = [
  [0, 1, 0, 0, 0],
  [0, 1, 0, 1, 0],
  [0, 0, 0, 1, 0],
  [0, 1, 0, 1, 0],
  [0, 0, 0, 1, 0],
];

const jps = new JPS(grid);
const path = jps.findPath([0, 0], [4, 4]);
console.log(path); // [[0, 0], [1, 1], [2, 2], [3, 3], [4, 4]]