Unity3D实现A*路径寻路算法出现路径冗余、死循环崩溃问题求助

崩溃（死循环）问题原因 #

1. 开放/关闭列表的重复节点判断逻辑完全失效：你写的foreach遍历里的continue仅能跳出当前遍历循环，并不会终止后续将节点重新加入开放列表的逻辑，导致同一个节点被无限次重复添加到开放列表，循环永远无法终止。
2. 坐标体系混乱：你同时混用了偏移后的actualVector/finalVector（坐标减1）和原始传入的actualPosi/finalPosi（无偏移）做终点判断，大部分场景下永远无法命中终点判断条件，循环会一直执行到资源耗尽崩溃。

路径过长问题原因 #

1. 没有更新已有节点的权重：当你找到某个已存在于开放/关闭列表的节点的更短G值时，既没有更新原有节点的G、F值，也没有更新该节点的父节点映射，算法只会沿用第一次找到的更长路径，不会切换到更短的最优路径。
2. 路径返回逻辑错误：你直接返回了全量的cameFrom字典，里面包含了所有遍历过的节点的父节点映射，没有从终点倒推筛选出唯一的最优路径链，角色寻路时很容易走到非最优的分支上。

具体修复步骤 #

1. 统一坐标体系：整个函数逻辑全程使用偏移后的Vector3Int类型坐标，不要和原始Vector3坐标混用，终点判断仅对比qNode.Key == finalVector即可。
2. 优化开放/关闭列表的存储结构：放弃用List存储节点，改用Dictionary<Vector3Int, List<float>>存储开放和关闭列表，节点存在性判断的时间复杂度从O(n)降到O(1)，同时修改判断逻辑：
   • 若相邻节点已在关闭列表，且新G值 >= 原有G值，直接跳过该节点；若新G值更小，将该节点从关闭列表移到开放列表，更新权重和父节点
   • 若相邻节点已在开放列表，且新G值 >= 原有G值，直接跳过该节点；若新G值更小，更新开放列表中该节点的权重和父节点
   • 仅当节点不在两个列表中时，才新增到开放列表
3. 补充路径回溯逻辑：命中终点判断后，不要直接返回cameFrom，从终点节点开始，反向遍历cameFrom字典，依次取出父节点，直到走到起点，将节点反转后就是从起点到终点的最优路径。
4. 增加循环保护：给while循环加最大迭代次数限制（比如最大遍历1000个节点），超过限制直接返回空路径，避免路径不存在时卡死。

核心修改后的代码示例 #

// 统一用Vector3Int做坐标，返回值改为路径列表，你也可以根据需求调整返回格式
public List<Vector3Int> FindPath(Vector3 actualPosi, Vector3 finalPosi, int maxIteration = 1000)
{
    Dictionary<Vector3Int, List<float>> openDict = new Dictionary<Vector3Int, List<float>>();
    Dictionary<Vector3Int, List<float>> closedDict = new Dictionary<Vector3Int, List<float>>();
    Dictionary<Vector3Int, Vector3Int> cameFrom = new Dictionary<Vector3Int, Vector3Int>();

    Vector3Int start = new Vector3Int((int)actualPosi.x - 1, (int)actualPosi.y - 1, 0);
    Vector3Int end = new Vector3Int((int)finalPosi.x - 1, (int)finalPosi.y - 1, 0);
    
    // 起点就是终点直接返回
    if (start == end) return new List<Vector3Int> { start };

    openDict.Add(start, new List<float> { ManhattanDistance(start, end), 0, ManhattanDistance(start, end) });
    int iterationCount = 0;

    while (openDict.Count > 0 && iterationCount < maxIteration)
    {
        iterationCount++;
        // 找F值最小的节点
        KeyValuePair<Vector3Int, List<float>> qNode = openDict.First();
        foreach (var kvp in openDict)
        {
            if (kvp.Value[0] < qNode.Value[0])
                qNode = kvp;
        }
        openDict.Remove(qNode.Key);
        closedDict.Add(qNode.Key, qNode.Value);

        // 到达终点，回溯路径
        if (qNode.Key == end)
        {
            List<Vector3Int> path = new List<Vector3Int>();
            Vector3Int current = end;
            while (cameFrom.ContainsKey(current))
            {
                path.Add(current);
                current = cameFrom[current];
            }
            path.Add(start);
            path.Reverse();
            return path;
        }

        // 生成四方向邻居
        List<Vector3Int> neighbors = new List<Vector3Int>
        {
            new Vector3Int(qNode.Key.x - 1, qNode.Key.y, 0),
            new Vector3Int(qNode.Key.x, qNode.Key.y - 1, 0),
            new Vector3Int(qNode.Key.x + 1, qNode.Key.y, 0),
            new Vector3Int(qNode.Key.x, qNode.Key.y + 1, 0)
        };

        foreach (var neighbor in neighbors)
        {
            // 无效节点跳过
            if (!tlmp.HasTile(neighbor) || invalidTile.Contains(neighbor))
                continue;

            float newG = qNode.Value[1] + 1; // 四方向移动每步成本都是1，不用算距离
            float newH = ManhattanDistance(neighbor, end);
            float newF = newG + newH;

            // 检查关闭列表
            if (closedDict.TryGetValue(neighbor, out var closedNode))
            {
                if (newG >= closedNode[1])
                    continue;
                closedDict.Remove(neighbor);
            }

            // 检查开放列表
            if (openDict.TryGetValue(neighbor, out var openNode))
            {
                if (newG >= openNode[1])
                    continue;
                // 更新已有节点的权重
                openNode[0] = newF;
                openNode[1] = newG;
                openNode[2] = newH;
                cameFrom[neighbor] = qNode.Key;
            }
            else
            {
                // 新增节点到开放列表
                openDict.Add(neighbor, new List<float> { newF, newG, newH });
                cameFrom[neighbor] = qNode.Key;
            }
        }
    }

    // 没找到路径返回空
    return new List<Vector3Int>();
}

小提示：如果你的Unity版本 >= 2021.2，可以用内置的PriorityQueue替代字典遍历找最小F值的逻辑，寻路性能会提升数倍，适合大地图场景使用。

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