js版本A*寻路算法

JS版本A*寻路算法

A（A-Star）算法是一种常用的路径搜索算法，它在寻找从起点到终点的最短路径过程中，会通过改进Dijkstra算法来提高效率。JS版本A寻路算法用于在网页游戏等应用场景下，帮助角色格子图中找到最短路径。

算法流程

1. 创建一个空的开放列表列表(OPEN)和一个空的封闭列表(CLOSED)
2. 把起始点作为当前点加入到OPEN列表中
3. 循环执行以下步骤：
4. 找到OPEN列表中的F值最小的节点作为当前节点P，把P从OPEN列表中移除，加入到CLOSED列表中
5. 如果当前节点P为目标终点，则路径已找到，跳出循环
6. 对P的所有邻居节点，计算它们的 G 和 H 值，其中：
   • G 值是指从起点到当前节点的实际代价
   • H 值是指从当前节点到目标节点的估价代价（即启发式函数）
7. 对于每个邻居节点N：
   • 如果N已经在CLOSED列表中，则跳过该节点，继续下一个节点
   • 如果不在OPEN列表中，则表示之前没有被处理过，将当前节点P设置为它的父节点，计算 F 值，并加入到OPEN列表中
   • 如果当前节点P已经是N的父节点，并且新计算的 G 值比原来的小，那么重新计算 N 的 F、G、H 值，并将其父节点设置为P
8. 如果 OPEN 列表为空，表示无法找到路径，退出循环。否则继续从 1 步重复执行

代码实现

下面是JS版本A*寻路算法的简单实现：

function AStar(startNode, endNode) {
  let openList = []; // 开启列表，存放待访问节点
  let closedList = []; // 关闭列表，存放已经访问过的节点
  startNode.g = 0; // 起始节点的G值为0
  startNode.f = startNode.g + getH(startNode, endNode); // 起始节点的F值为H值
  openList.push(startNode); // 将起始节点加入到开启列表中

  while (openList.length > 0) {
    // 从开启列表中找到F值最小的节点作为当前节点
    let curNode = openList.reduce((prev, cur) =>
      prev.f < cur.f ? prev : cur
    );
    // 从开启列表中删除当前节点
    openList = openList.filter((item) => item !== curNode);
    // 将当前节点添加到关闭列表中
    closedList.push(curNode);

    if (curNode === endNode) {
      // 找到了目标节点，返回路径
      return getPath(startNode, endNode);
    }

    // 获取当前节点的邻居列表
    let neighborList = getNeighborList(curNode);

    // 遍历邻居列表
    for (let i = 0; i < neighborList.length; i++) {
      let neighborNode = neighborList[i];

      if (closedList.includes(neighborNode)) {
        // 当前节点已经在关闭列表中，忽略它
        continue;
      }

      let gScore = curNode.g + 1; // 更新G值

      if (!openList.includes(neighborNode)) {
        // 邻居节点第一次遍历到，加入开启列表
        neighborNode.g = gScore;
        neighborNode.h = getH(neighborNode, endNode);
        neighborNode.f = neighborNode.g + neighborNode.h;
        neighborNode.parent = curNode;
        openList.push(neighborNode);
      } else if (gScore < neighborNode.g) {
        // 当前节点是邻居节点的更优父节点
        neighborNode.g = gScore;
        neighborNode.f = neighborNode.g + neighborNode.h;
        neighborNode.parent = curNode;
      }
    }
  }
  // 开启列表已经用完，仍然没有到达目标节点，则返回空路径
  return [];
}

示例说明

在以下示例中，我们将用一个简单的二维数组来表示地图，其中1表示障碍物，0表示通路。我们将尝试寻找从起点 (0, 0) 到终点 (3, 3) 的最短路径。

let map = [
  [0, 1, 0, 0],
  [0, 0, 1, 0],
  [1, 0, 0, 1],
  [0, 0, 1, 0],
];

// 节点对象
class Node {
  constructor(x, y) {
    this.x = x;
    this.y = y;
    this.g = 0;
    this.h = 0;
    this.f = 0;
    this.parent = null;
  }
}

function getH(node, endNode) {
  // 计算H值（曼哈顿距离）
  return Math.abs(endNode.x - node.x) + Math.abs(endNode.y - node.y);
}

function getNeighborList(node) {
  // 获取相邻节点列表
  let neighborList = [];
  let x = node.x;
  let y = node.y;

  if (x > 0) {
    neighborList.push(new Node(x - 1, y));
  }
  if (x < map[0].length - 1) {
    neighborList.push(new Node(x + 1, y));
  }
  if (y > 0) {
    neighborList.push(new Node(x, y - 1));
  }
  if (y < map.length - 1) {
    neighborList.push(new Node(x, y + 1));
  }

  neighborList = neighborList.filter(
    (item) => map[item.y][item.x] !== 1 // 过滤障碍点
  );
  return neighborList;
}

function getPath(startNode, endNode) {
  // 从终点往回推，返回路径
  let path = [];
  let curNode = endNode;

  while (curNode !== startNode) {
    path.push(curNode);
    curNode = curNode.parent;
  }
  // 把起点加入路径末尾
  path.push(startNode);
  return path.reverse();
}

let startNode = new Node(0, 0);
let endNode = new Node(3, 3);
let path = AStar(startNode, endNode);

console.log(path);
// 输出：[
//   Node { x: 0, y: 0, g: 0, h: 6, f: 6, parent: null },
//   Node { x: 1, y: 1, g: 1, h: 4, f: 5, parent: [Node] },
//   Node { x: 2, y: 1, g: 2, h: 3, f: 5, parent: [Node] },
//   Node { x: 2, y: 2, g: 3, h: 2, f: 5, parent: [Node] },
//   Node { x: 3, y: 3, g: 4, h: 0, f: 4, parent: [Node] }
// ]

在上面的示例中，我们使用了一个Node类来表示节点，其中x和y表示节点坐标，g表示起点到当前节点的实际代价，h表示当前节点到目标节点的估价代价（即启发式函数），f表示当前节点的总代价（f=g+h），parent表示当前节点的父节点。其中的 getH、getNeighborList、getPath 分别是计算 H 值、获取邻居节点列表、从终点往回推导路径的辅助函数。

最终，我们得到了从起点到终点的最短路径：(0,0)->(1,1)->(2,1)->(2,2)->(3,3)。