A星算法的实现

1. A* 算法是什么？

A* 算法是一种启发式搜索（Heuristic Search），它结合了 Dijkstra 的最短路径思想和 贪心搜索 的目标导向，既能保证路径的最优，又能提升搜索效率。

其核心是公式：

f(n) = g(n) + h(n)

• g(n)：从起点到当前节点的实际代价。

• h(n)：从当前节点到目标节点的预估代价（启发函数，常用曼哈顿距离或欧几里得距离）。

• f(n)：总代价，A* 每次选择 f 最小的节点进行扩展。

2. 基本流程

1. 初始化：将起点加入 openList（待探索节点）。

2. 循环：

• 如果不可走（障碍），跳过。

• 如果在 closeList，跳过。

• 如果不在 openList，加入并计算 f、g、h。

• 如果已经在 openList，检查是否有更优的 g 值，有则更新父节点。

• 从 openList 里取出 f 值最小的节点 N。

• 如果 N 是终点，结束，回溯得到路径。

• 否则，将 N 放入 closeList（已探索节点）。

• 检查 N 的相邻节点，对每个邻居：

3. 失败条件：openList 为空时，说明无路可走。

3. Unity 简单实现

3.1 节点定义

public enum E_Node_Type { Walk, Stop }

public class AStartNode
{
    public int x, y;
    public E_Node_Type type;
    public AStartNode father;
    public float g, h, f;

    public AStartNode(int x, int y, E_Node_Type type)
    {
        this.x = x;
        this.y = y;
        this.type = type;
    }
}

3.2 核心管理器

public class AStartMgr
{
    private static AStartMgr instance;
    public static AStartMgr Instance => instance ?? (instance = new AStartMgr());

    private int mapW, mapH;
    public AStartNode[,] nodes;

    private List<AStartNode> openList = new List<AStartNode>();
    private List<AStartNode> closeList = new List<AStartNode>();

    private AStartMgr() { }

    public void InitMapInfo(int w, int h)
    {
        mapW = w;
        mapH = h;
        nodes = new AStartNode[w, h];
        for (int i = 0; i < w; i++)
        {
            for (int j = 0; j < h; j++)
            {
                nodes[i, j] = new AStartNode(i, j, Random.Range(0, 100) < 20 ? E_Node_Type.Stop : E_Node_Type.Walk);
            }
        }
    }

    public List<AStartNode> FindPath(Vector2 startPos, Vector2 endPos)
    {
        openList.Clear();
        closeList.Clear();

        AStartNode start = nodes[(int)startPos.x, (int)startPos.y];
        AStartNode end = nodes[(int)endPos.x, (int)endPos.y];

        openList.Add(start);

        while (openList.Count > 0)
        {
            // 取 f 最小的节点
            openList.Sort((a, b) => a.f.CompareTo(b.f));
            AStartNode cur = openList[0];
            openList.RemoveAt(0);
            closeList.Add(cur);

            if (cur == end) return BuildPath(end);

            // 遍历邻居
            foreach (var nb in GetNeighbors(cur))
            {
                if (nb.type == E_Node_Type.Stop || closeList.Contains(nb)) continue;

                float g = cur.g + 1; // 简化，直邻代价 1
                if (!openList.Contains(nb) || g < nb.g)
                {
                    nb.father = cur;
                    nb.g = g;
                    nb.h = Mathf.Abs(end.x - nb.x) + Mathf.Abs(end.y - nb.y);
                    nb.f = nb.g + nb.h;
                    if (!openList.Contains(nb)) openList.Add(nb);
                }
            }
        }
        return null;
    }

    private IEnumerable<AStartNode> GetNeighbors(AStartNode node)
    {
        int[,] dirs = { {1,0}, {-1,0}, {0,1}, {0,-1} };
        for (int i = 0; i < 4; i++)
        {
            int nx = node.x + dirs[i,0];
            int ny = node.y + dirs[i,1];
            if (nx >= 0 && nx < mapW && ny >= 0 && ny < mapH)
                yield return nodes[nx, ny];
        }
    }

    private List<AStartNode> BuildPath(AStartNode end)
    {
        List<AStartNode> path = new List<AStartNode>();
        while (end != null)
        {
            path.Add(end);
            end = end.father;
        }
        path.Reverse();
        return path;
    }
}

4. 常见坑点

1. 比较器必须自反

• a.f.CompareTo(b.f) 才合法，不要偷懒写成只返回 1/-1。

• 否则大地图（如 100x100）会直接报错。

2. openList 的性能瓶颈

• 用 List.Sort 每次都全量排序，复杂度是 O(n log n)。

• 优化：改用 小顶堆（优先队列），插入和取最小值都是 O(log n)。

3. h 的选择影响性能

• 曼哈顿距离（|dx|+|dy|）：适合只能直走上下左右。

• 欧几里得距离：适合斜线可走。

• 对角距离：max(|dx|, |dy|)，效率高，常用于方格地图。

4. 障碍点恢复材质

• 记得每次寻路前清理旧路径颜色。

5. 总结

A* 算法在二维网格地图中非常常用，优点是能在保证最优解的同时高效搜索。实现时要注意：

• 正确的比较器写法。

• openList 的优化（用堆）。

如果需要 实时寻路 + 大地图，需要学习 导航网格（NavMesh） 或 分区寻路（Hierarchical Pathfinding, HPA*）。