带坐标无向图中A*算法f cost计算与React实现问题求助

gScore的核心定义是起点到当前节点的实际最短路径代价，属于可确定的实际成本，不是预估数值，具体计算逻辑和完整实现如下：

gScore 计算核心规则 #

• 初始化阶段所有节点gScore默认设为Infinity（无穷大，代表初始状态不可达）
• 仅起点的gScore单独设置为0（起点到自身的路径代价为0）
• 遍历当前节点的邻接节点时，临时g值 = 当前节点的gScore + 当前节点到邻接节点的实际移动代价
• 只有临时g值 < 邻接节点当前存储的gScore时，才更新邻接节点的gScore、parentId、fScore，并将邻接节点加入开放列表

完整可运行实现代码 #

// 工具函数：计算两点欧氏距离（用于移动代价计算）
const calcDistance = (nodeA, nodeB) => {
  const dx = nodeA.x - nodeB.x;
  const dy = nodeA.y - nodeB.y;
  return Math.sqrt(dx * dx + dy * dy);
};

// 工具函数：计算启发值h，可根据需求替换为曼哈顿距离
const calcHeuristic = (currentNode, endNode) => {
  // 曼哈顿距离实现：return Math.abs(currentNode.x - endNode.x) + Math.abs(currentNode.y - endNode.y)
  return calcDistance(currentNode, endNode);
};

// A*主函数，传入起点id、终点id、全节点列表即可调用
const aStar = (originLocationId, destinationLocationId, locations) => {
  // 转成id映射的节点对象，提升查找效率
  const nodeMap = {};
  locations.forEach(node => {
    // 深拷贝避免修改原节点数据
    nodeMap[node.id] = {
      ...node,
      gScore: Infinity,
      hScore: 0,
      fScore: Infinity,
      parentId: null
    };
  });

  const startNode = nodeMap[originLocationId];
  const endNode = nodeMap[destinationLocationId];

  // 初始化起点属性
  startNode.gScore = 0;
  startNode.hScore = calcHeuristic(startNode, endNode);
  startNode.fScore = startNode.gScore + startNode.hScore;

  const openSet = new Set([originLocationId]); // 待探索节点集合
  const closedSet = new Set(); // 已完成探索节点集合

  while (openSet.size > 0) {
    // 取出开放列表中fScore最小的节点作为当前节点
    let currentId = null;
    let lowestF = Infinity;
    openSet.forEach(id => {
      if (nodeMap[id].fScore < lowestF) {
        lowestF = nodeMap[id].fScore;
        currentId = id;
      }
    });
    const currentNode = nodeMap[currentId];

    // 到达终点，回溯生成路径
    if (currentId === destinationLocationId) {
      const path = [];
      let temp = currentNode;
      while (temp) {
        path.unshift(temp);
        temp = nodeMap[temp.parentId];
      }
      return path;
    }

    // 移动当前节点到已探索集合
    openSet.delete(currentId);
    closedSet.add(currentId);

    // 遍历所有邻接节点
    currentNode.neighborIds.forEach(neighborId => {
      // 邻接节点不存在/已探索完成则跳过
      if (!nodeMap[neighborId] || closedSet.has(neighborId)) return;
      const neighborNode = nodeMap[neighborId];
      
      // 计算当前路径下到邻接节点的临时g值
      const tentativeG = currentNode.gScore + calcDistance(currentNode, neighborNode);
      // 临时g值更小，说明找到了到邻接节点的更短路径
      if (tentativeG < neighborNode.gScore) {
        neighborNode.parentId = currentId;
        neighborNode.gScore = tentativeG;
        neighborNode.hScore = calcHeuristic(neighborNode, endNode);
        neighborNode.fScore = neighborNode.gScore + neighborNode.hScore;
        // 邻接节点不在待探索集合则加入
        if (!openSet.has(neighborId)) openSet.add(neighborId);
      }
    });
  }

  // 无可达路径返回空数组
  return [];
};

常见实现误区 #

1. 不要将所有节点gScore初始化为0，仅起点的gScore为0，其他节点初始值必须为无穷大
2. 不要每次遍历邻接节点就直接覆盖gScore，必须判断临时g值小于现有值才更新，保证拿到的是当前最短路径代价
3. 移动代价是相邻两个节点的实际距离，不要用启发值直接代替实际移动成本

内容的提问来源于stack exchange，提问作者AdamA