Unity A星寻路算法

一、概念

1、解决什么问题

A * 是通用网格最短路径算法，不限于 2D，3D 导航网格、瓦片地图、塔防、RPG 角色移动都能用；核心：在存在障碍物的网格中，找出代价最低的最优路径。

2、基本原理

遍历九宫格中周围的八个点，舍弃阻挡点和边界点，选取最优路径点

3、详细原理

代价公式：
1
F = G + H
- G：从起点走到当前节点的实际行走代价（已走过的路，固定真实值）
- H：当前节点到终点的预估启发代价（没走的路，估算值）
- F：总代价，A * 每次永远选 OpenList 中 F 最小的节点拓展
OpenList（开启列表）：待检查、待拓展的候选节点池
CloseList（关闭列表）：已经处理完毕、不再二次访问的节点；取出最优节点后立刻移入 Close
Parent 父节点：记录路径前驱，寻路结束后从终点反向回溯，反转得到正向行走路径
终止条件：取出的最优节点 == 终点节点，算法结束

4. 关键约束：启发函数可采纳性

H 不能高估真实距离，否则 A * 无法保证最短路径：

四向移动：曼哈顿距离（可采纳）
八向移动：切比雪夫代价 10/14（可采纳）

二、具体代码实现

1. 格子类

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// 是否可以行走
public bool isWalkable;
// 格子的绝对位置（网格坐标）
public Vector2Int gridPos;
// 起点 -> 当前格子（准确值）
public float gCost;
// 当前格子 -> 终点（预测值）
public float hCost;
// 总代价，寻路消耗公式：f（寻路消耗）=g（距离起点的距离）+h（距离终点的距离）
public float FCost => gCost + hCost;
// 格子对象的父对象
public Node parent;

字段	含义
`gCost`	从起点到当前格子的实际代价
`hCost`	从当前格子到终点的启发式估计代价
`FCost`	`gCost + hCost`，A* 排序依据
`parent`	格子对象的父对象

2. 寻路管理

2.1 生成网格地图

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
public void CreateMap()
{
    Map = new Node[mapX, mapY];

    for (int x = 0; x < mapX; x++)
    {
        for (int y = 0; y < mapY; y++)
        {
            // 确定地图原点（第一象限）
            Vector2Int pos = new Vector2Int(mapOrigin.x + x, mapOrigin.y + y);
            GameObject obj = Instantiate(nodePrefab, new Vector3(pos.x, pos.y, 0), Quaternion.identity, mapRoot);

            Node node = obj.GetComponent<Node>();
            node.gridPos = new Vector2Int(x, y); // 世界坐标 -> 网格虚拟坐标
            node.isWalkable = true;

            Map[x, y] = node;
        }
    }
}

2.2 获取节点周围邻居（八方向）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
public List<Node> GetNeighbors(Node node)
{
    List<Node> neighbors = new List<Node>();
    for (int x = -1; x <= 1; x++)
    {
        for (int y = -1; y <= 1; y++)
        {
            if (x == 0 && y == 0)
                continue; // 跳过中心节点

            int nodeX = node.gridPos.x + x;
            int nodeY = node.gridPos.y + y;

            if (nodeX >= 0 && nodeX < mapX && nodeY >= 0 && nodeY < mapY)
                neighbors.Add(Map[nodeX, nodeY]);
        }
    }
    return neighbors;
}

3. 算法核心

3.1 初始化 open / close 列表

1
2
3
4
List<Node> openList = new List<Node>();       // 待探索
HashSet<Node> closeList = new HashSet<Node>(); // 已探索

openList.Add(startNode);

3.2 主循环（openList 非空时）

① 选出 FCost 最小的节点

若 FCost 相同，则比较 hCost（gCost 为确定值，此处不参与 tie-break）。

1
2
3
4
5
6
7
8
9
Node currentNode = openList[0];
for (int i = 1; i < openList.Count; i++)
{
    if (openList[i].FCost < currentNode.FCost ||
        openList[i].FCost == currentNode.FCost && openList[i].hCost < currentNode.hCost)
    {
        currentNode = openList[i];
    }
}

② 移入 closeList

1
2
openList.Remove(currentNode);
closeList.Add(currentNode);

③ 到达终点：回溯路径判断是否到达终点

1
2
3
4
5
if (currentNode == targetNode)
{
    RetracePath(startNode, targetNode);
    return;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
void RetracePath(Node startNode, Node endNode)
{
    List<Node> path = new List<Node>();
    Node currentNode = endNode;

    while (currentNode != startNode)
    {
        currentNode.spriteRenderer.color = Color.green;
        path.Add(currentNode);
        currentNode = currentNode.parent;
    }
    path.Reverse();
}

注：通过 parent 从终点一路回溯到起点。

④ 扩展邻居节点

对当前节点的邻居：

不可行走或已在 closeList → 跳过
计算 newGCost；若比原 gCost 更优，或该节点还不在 openList，则更新 g/h、设置 parent，并加入 openList

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
foreach (var node in gridManager.GetNeighbors(currentNode))
{
    if (!node.isWalkable || closeList.Contains(node))
        continue;

    float newGCost = currentNode.gCost + GetDistance(currentNode, node);

    if (newGCost < node.gCost || !openList.Contains(node))
    {
        node.gCost = newGCost;
        node.hCost = GetDistance(node, targetNode);
        node.parent = currentNode;

        if (!openList.Contains(node))
            openList.Add(node);
    }
}

说明
邻居节点初始 gCost 为 0，第一次访问时 newGCost > node.gCost 仍成立，且不在任何队列 → 一定会进入 openList。
赋值后若发现更短路径会更新；往回走时 newGCost 更大，不会错误覆盖。

3.3 启发函数 `GetDistance`

曼哈顿距离适用场景区分

曼哈顿距离只适合只能上下左右移动（四向），八向必须用 10/14 切比雪夫代价，混用会导致路径扭曲；

四方向：曼哈顿距离

1
2
3
int xDis = Mathf.Abs(node1.gridPos.x - node2.gridPos.x);
int yDis = Mathf.Abs(node1.gridPos.y - node2.gridPos.y);
return xDis + yDis;

八方向：切比雪夫式代价（直走 10，斜走 14）尽量走倾斜的道路

1
2
3
4
5
6
7
8
int xDis = Mathf.Abs(node1.gridPos.x - node2.gridPos.x);
int yDis = Mathf.Abs(node1.gridPos.y - node2.gridPos.y);

const int straightCost = 10;
const int diagonalCost = 14; // √2 ≈ 1.414，取整

// 先斜向走 min(dx,dy) 步，再直走 |dx-dy| 步
return diagonalCost * Mathf.Min(xDis, yDis) + straightCost * Mathf.Abs(xDis - yDis);

4. 多单位 A* 的优化

优化	说明
优先队列 + HashSet	`openList` 用 Priority Queue（根为最小 F，O(log n) 取最优点）；`closeList` 用 HashSet（O(1) 查找是否已探索）
相同起点	直接复用缓存路径
起点不同、终点相同	用 Dijkstra 从终点反向扩散，预计算每个格子的行进方向，多单位共享

优先队列：逻辑上是完全二叉树，实现上常用数组 + 下标公式；根节点始终为当前最小代价节点。

流程速查

要点速查

概念	要点
A*	`F = g + h`，按 F 升序扩展，h 需可采纳（不高估）
open / close	待探索 / 已探索，避免重复扩展
parent	记录最短路上的前驱，终点回溯得路径
四向 / 八向	曼哈顿 / 直10斜14 代价
多单位	优先队列提速；同终点可反向 Dijkstra 预处理

Unity A星 寻路算法