React.js实现A*算法出现崩溃、路径错误及新增节点后路径消失问题

问题根因总结 #

• 初始版本崩溃核心问题：死循环+原始数据污染
  1. 找到终点后没有break跳出while循环，程序持续遍历节点，碰到环就触发无限循环直接卡死网页
  2. 遍历邻居节点时错误修改了currentNode.gcost，每次迭代都累加当前节点的gcost，导致数值逻辑完全失效，进一步加剧无限循环
  3. 直接修改props传入的原始locations数组内的节点对象，gcost、parentId等A*计算属性会残留上次计算的数值，不会自动重置
• 修复崩溃后路径消失的问题：
  1. 每次计算路径前没有重置所有节点的gcost、heuristic、parentId属性，上次计算的残留值会导致本次gcost < (neighbourNode.gcost ?? Infinity)判断不生效，路径计算失败
  2. 拼写错误：path = [getNodeById(originLocationId).namne]; 中name被误写为namne，导致初始路径值错误
  3. 未处理节点不可达场景，新增节点后暂时没有连通路径时，path会被赋值为空，表现为路径消失

修复方案 #

1. 每次计算路径前重置所有节点的A*相关属性 #

在初始化openList前新增重置逻辑，避免历史残留值干扰：

// 重置所有节点的A*属性
locations.forEach(node => {
  node.gcost = Infinity;
  node.heuristic = 0;
  node.fcost = 0;
  node.parentId = null;
});

2. 补全A*标准实现逻辑，规避环带来的问题 #

新增closedList存储已经处理完成的节点，避免重复遍历环上节点：

// 初始化时新增closedList
var openList = [];
var closedList = [];

// 处理完当前节点后加入closedList
deleteCurrentFromOpenList(currentNode, openList);
closedList.push(currentNode);

// 遍历邻居时先判断是否已处理过
for (let neighbourId of currentNode.connectedToIds) {
  var neighbourNode = getNodeById(neighbourId);
  if (closedList.includes(neighbourNode)) continue;
  // 后续计算逻辑保持不变
}

3. 修复拼写错误 #

将代码中的.namne修正为.name

4. 增加路径兜底展示逻辑 #

当没有连通路径时展示提示，避免出现空内容：

path = path.length > 0 ? path.reverse().join("->") : "暂无连通路径";

核心逻辑完整修复参考 #

if (destinationLocationId != null && originLocationId != null) {
  // 第一步：重置所有节点属性
  locations.forEach(node => {
    node.gcost = Infinity;
    node.heuristic = 0;
    node.fcost = 0;
    node.parentId = null;
  });
  let startNode = getNodeById(originLocationId);
  let destinationNode = getNodeById(destinationLocationId);
  let path = [startNode.name];
  if (originLocationId === destinationLocationId) {
    path = [startNode.name];
  } else {
    if (startNode.connectedToIds.length > 0 && destinationNode.connectedToIds.length > 0) {
      var openList = [];
      var closedList = [];
      startNode.gcost = 0;
      startNode.heuristic = manhattanDistance(startNode, destinationNode);
      startNode.fcost = startNode.gcost + startNode.heuristic;
      openList.push(startNode);
      while (openList.length > 0) {
        var currentNode = getNodeOfMinFscore(openList);
        if (currentNode.id === destinationLocationId) {
          path = getPath(currentNode);
          break;
        }
        deleteCurrentFromOpenList(currentNode, openList);
        closedList.push(currentNode);
        for (let neighbourId of currentNode.connectedToIds) {
          var neighbourNode = getNodeById(neighbourId);
          if (closedList.includes(neighbourNode)) continue;
          let gcost = currentNode.gcost + manhattanDistance(currentNode, neighbourNode);
          if (gcost < neighbourNode.gcost) {
            neighbourNode.parentId = currentNode.id;
            neighbourNode.gcost = gcost;
            neighbourNode.heuristic = manhattanDistance(neighbourNode, destinationNode);
            neighbourNode.fcost = neighbourNode.gcost + neighbourNode.heuristic;
            addNeighbourNodeToOpenList(neighbourNode, openList);
          }
        }
      }
    }
  }
  path = path.length > 0 ? path.reverse().join("->") : "暂无连通路径";
}

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