Unity3D中A*寻路脚本调用时崩溃问题求助

我在Unity中实现A算法用于NPC场景导航：寻路节点是挂载了WaypointController类的Vector3对象，每个路点包含相邻节点列表；A函数从NPC视线范围内的最近节点出发，寻路到目标点视线范围内的最近节点。确认A*核心逻辑（开放集合取最低F值节点、移至关闭集合、遍历邻节点更新值）无误，但调用GetPath函数时Unity崩溃，代码如下：

public List GetPath(WaypointController start, WaypointController end)
{
List path = new List();

    //Don't interrupt other GetPath calls
    if (findingPath == false)
    {
        findingPath = true;

        //nodes to evaluate
        List<WaypointController> openNodes = new List<WaypointController>();
        //evaluated nodes
        List<WaypointController> closedNodes = new List<WaypointController>();

        //Setup start & end
        start.pathLengthToA = 0;
        start.distanceToZ = Vector3.Distance(start.transform.position, end.transform.position);
        end.distanceToZ = 0;

        //node being evaluated
        WaypointController currentNode = start;

        //Add start node  to open
        openNodes.Add(currentNode);

        //Evaluate nodes in the open set until currentNode = end
        do {
            //currentNode = lowest F cost node in openNodes
            foreach(WaypointController openWPC in openNodes)
            {
                if(openWPC.pathLengthToA + openWPC.distanceToZ < currentNode.pathLengthToA + currentNode.distanceToZ)
                {
                    Debug.Log("A* using: " + openWPC);
                    currentNode = openWPC;
                }
            }

            //Move currentNode from openNodes to closedNodes
            openNodes.Remove(currentNode);
            closedNodes.Add(currentNode);

            //Break if path complete
            if(currentNode == end)
                break;

            //For each adjacent node to currentNode
            float tempEdgeLength;
            foreach(WaypointController adjWPC in currentNode.adjacentNodes)
            {
                //Skip closed nodes
                if(closedNodes.Contains(adjWPC))
                    continue;

                //If new path to adjacent node is shorter, or adjacent node is not in open (set it up)
                graph.TryGetEdge(currentNode, adjWPC, out tempEdgeLength);
                if(currentNode.pathLengthToA + tempEdgeLength < adjWPC.pathLengthToA || openNodes.Contains(adjWPC) == false)
                {
                    Debug.Log("A* is evaluating node: " + adjWPC.name);

                    //set f cost of neighbor
                    adjWPC.pathLengthToA = currentNode.pathLengthToA + tempEdgeLength;
                    adjWPC.distanceToZ = Vector3.Distance(adjWPC.transform.position, end.transform.position);

                    //set nodeBeforeThisInPath in neighbor to currentNode
                    adjWPC.nodeBeforeThisInPath = currentNode;

                    //add neighbor to openNodes
                    if(openNodes.Contains(adjWPC) == false)
                        openNodes.Add(adjWPC);
                }
            }

        } while (currentNode != end);

        //Output it
        path.Add(start.transform.position);
        while (currentNode.nodeBeforeThisInPath != start)
        {
            path.Add(currentNode.nodeBeforeThisInPath.transform.position);
        }
        path.Add(end.transform.position);

        //free up the function
        findingPath = false;
    }
    else
    {
        path.Add(Vector3.zero);
    }

    //Return the path or an empty path if findingPath was already true (& handle retry in the other script
    return path;
}

崩溃原因排查及修复建议 #

1. 无限循环（最可能导致崩溃的原因）

• 问题：do-while循环仅以currentNode != end为终止条件，如果场景中不存在可行路径，openNodes会被耗尽，但循环会持续执行，直接卡死Unity主线程。此外，若openNodes中所有节点F值都不小于初始currentNode的F值，currentNode不会更新，会重复处理同一节点，陷入循环。
• 修复：添加openNodes.Count > 0的判断，避免无路径时无限循环：

  do {
      // 原有逻辑
  } while (currentNode != end && openNodes.Count > 0);
  

2. 节点属性未初始化

• 问题：非起点节点的pathLengthToA可能默认值为0，导致currentNode.pathLengthToA + tempEdgeLength < adjWPC.pathLengthToA判断逻辑错误，节点被反复加入开放集，引发异常或循环。
• 修复：寻路前重置所有涉及节点的pathLengthToA为极大值，仅将起点设为0：

  // 假设你能获取所有路点列表
  foreach(var node in allWaypoints) {
      node.pathLengthToA = float.MaxValue;
      node.nodeBeforeThisInPath = null;
  }
  start.pathLengthToA = 0;
  

3. 集合操作性能瓶颈

• 问题：使用List作为开放/关闭集合，Contains和Remove操作均为O(n)复杂度，节点数量较多时会导致性能急剧下降，最终引发超时崩溃。
• 修复：
  • 关闭集合改用HashSet<WaypointController>，Contains操作变为O(1)
  • 开放集合改用PriorityQueue<WaypointController, float>，可直接取出最低F值节点，无需遍历整个列表

4. 路径回溯逻辑错误

• 问题：回溯路径的while循环条件currentNode.nodeBeforeThisInPath != start，若路径仅包含起点和终点（直接相邻），循环不会执行；若出现节点循环引用，会导致无限循环。
• 修复：改为从终点反向遍历到起点，再反转路径：

  path.Clear();
  if(currentNode == end) {
      while(currentNode != null) {
          path.Add(currentNode.transform.position);
          currentNode = currentNode.nodeBeforeThisInPath;
      }
      path.Reverse(); // 反转得到从起点到终点的路径
  }
  

5. 重入逻辑风险

• 问题：findingPath布尔标记未做线程安全处理，若被快速重复调用，可能出现竞态条件，导致多个线程同时修改集合，引发崩溃。
• 修复：改用协程异步处理寻路逻辑，避免阻塞主线程；或添加锁机制确保findingPath的线程安全。

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