优化Unity中C# A*寻路算法——解决大/复杂地图崩溃问题

崩溃原因分析 #

• 核心性能瓶颈：原代码每次从pool（开放列表）选取最优节点时，使用OrderBy(...).First()做全量排序，时间复杂度为O(n log n)。大型地图中开放列表会快速膨胀至数千甚至数万个节点，持续的高计算量会直接拖垮主线程，导致Unity因超时无响应崩溃。
• 内存占用失控：HashSet无法处理重复入队的节点，同一个格子可能被多次加入开放列表，导致pool和parents字典内存占用持续飙升，最终触发内存溢出。
• 启发式函数效率低：使用平方欧几里得距离作为启发值，计算量大于曼哈顿距离；且四方向移动场景下，曼哈顿距离是更合适的可采纳启发式，能让寻路更快收敛。

针对性优化方案 #

1. 替换开放列表为优先队列 #

用**优先队列（Priority Queue）**替代HashSet作为开放列表，优先队列能在O(log n)时间内完成插入和取出最优节点的操作，彻底解决全量排序的性能问题。Unity 2021+支持.NET 6的System.Collections.Generic.PriorityQueue，也可自行实现轻量版本。

2. 优化启发式函数 #

四方向移动场景下，使用曼哈顿距离作为启发值（h），计算更快且符合可采纳性（不会高估实际代价），能让寻路过程更快收敛，减少需要处理的节点数量。
曼哈顿距离公式：Mathf.Abs(c.x - end.x) + Mathf.Abs(c.y - end.y)

3. 记录节点实际代价（g值），避免重复无效入队 #

新增字典记录每个节点的实际移动代价（从起点到当前节点的步数），当发现已有更优路径到达某节点时，直接跳过入队操作，减少开放列表冗余节点。

4. 调整访问标记逻辑 #

将visited集合改为记录已处理的节点，从优先队列取出节点时先检查是否已处理，若已处理则直接跳过，避免重复计算。

优化后的完整代码 #

using System.Collections.Generic;
using UnityEngine;

public static class Pathfinder
{
    public static List<Vector2Int> FindRoute(Vector2Int start, Vector2Int end)
    {
        // 终点不可达直接返回
        if (!GameState.IsFree(end))
            return null;

        // 优先队列：存储(节点, 总代价f=g+h)，按f值升序排列
        var openQueue = new PriorityQueue<Vector2Int, int>();
        // 记录每个节点的实际代价g（从起点到该节点的步数）
        Dictionary<Vector2Int, int> gCosts = new();
        // 记录节点的父节点，用于回溯路径
        Dictionary<Vector2Int, Vector2Int> parents = new();
        // 已处理完成的节点集合
        HashSet<Vector2Int> closedSet = new();

        // 初始化起点
        openQueue.Enqueue(start, 0);
        gCosts[start] = 0;

        while (openQueue.Count > 0)
        {
            // 取出当前f值最小的节点
            openQueue.TryDequeue(out var current, out _);

            // 该节点已处理过，直接跳过
            if (closedSet.Contains(current))
                continue;

            // 到达终点，提前终止循环
            if (current == end)
                break;

            closedSet.Add(current);

            // 生成四方向候选节点
            var candidates = new List<Vector2Int>
            {
                current + Vector2Int.right,
                current + Vector2Int.left,
                current + Vector2Int.up,
                current + Vector2Int.down
            };

            foreach (var neighbor in candidates)
            {
                // 节点不可走或已处理，跳过
                if (closedSet.Contains(neighbor) || !GameState.IsFree(neighbor))
                    continue;

                // 计算当前路径到邻居的g值（四方向每步代价为1）
                int newGCost = gCosts[current] + 1;

                // 如果邻居不在gCosts中，或者新路径更优
                if (!gCosts.ContainsKey(neighbor) || newGCost < gCosts[neighbor])
                {
                    // 更新g值和父节点
                    gCosts[neighbor] = newGCost;
                    parents[neighbor] = current;

                    // 计算f值：g + h（曼哈顿距离）
                    int hCost = Mathf.Abs(neighbor.x - end.x) + Mathf.Abs(neighbor.y - end.y);
                    int fCost = newGCost + hCost;

                    // 加入优先队列
                    openQueue.Enqueue(neighbor, fCost);
                }
            }
        }

        // 回溯生成路径
        if (!parents.ContainsKey(end))
            return null;

        var route = new List<Vector2Int>();
        var currentCell = end;

        while (currentCell != start)
        {
            route.Add(currentCell);
            currentCell = parents[currentCell];
        }

        // 反转路径，从起点到终点
        route.Reverse();
        return route;
    }
}

优化效果说明 #

• 性能提升：优先队列将每次取最优节点的时间从O(n log n)降到O(log n)，大型地图中寻路耗时从秒级降至毫秒级，避免主线程阻塞。
• 内存控制：通过g值检查避免重复入队，开放列表节点数量大幅减少，内存占用更稳定。
• 收敛速度：曼哈顿距离启发式让寻路过程更贴近最优路径，减少不必要的节点探索。

额外优化建议 #

• 异步寻路：地图特别巨大时，将寻路逻辑放到后台线程执行，避免阻塞主线程。注意GameState.IsFree需确保线程安全，或提前将地图数据复制到线程安全结构中。
• 地图分块：将大型地图分成多个小块，仅在角色附近的块内执行寻路，进一步减少计算量。
• 缓存常用路径：对经常走的路径缓存结果，避免重复计算。

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