游戏AI寻路进阶：用A与DLite实现《原神》式动态地形避障（Unity版）

在开放世界游戏里，NPC的智能移动是沉浸感的关键一环。想象一下，你操控的角色在蒙德城外的平原上奔跑，身后跟着的同伴能灵巧地绕过突然出现的史莱姆、自动避开玩家临时放置的障碍物，甚至在你改变目的地时，他能立刻重新规划一条最优路径，而不是像个木偶一样卡在原地或者走回头路。这种“活”起来的寻路体验，背后是静态寻路与动态避障算法的精妙结合。对于游戏开发者而言，单纯依赖Unity自带的NavMesh系统，在处理复杂动态环境时常常力不从心，尤其是当场景中存在大量实时变化的可交互元素时。本文将深入探讨如何将经典的A算法与更先进的DLite算法融合，在Unity中构建一套能够应对《原神》这类游戏动态地形挑战的高性能寻路组件。

1. 寻路算法核心：从静态规划到动态响应

寻路算法的本质是在一个由节点和边构成的图（Graph）中，寻找从起点到终点的最优路径。这个“最优”通常指代最短距离、最低成本或最快时间。在游戏开发中，我们常将游戏世界离散化为一个网格（Grid）或导航网格（NavMesh），每个单元格或三角形就是一个节点，节点之间的连通性构成了边。

Dijkstra算法是寻路领域的奠基者之一。它的思想非常朴素：从起点出发，像水波纹一样均匀地向所有方向探索，直到触及目标点。它保证找到最短路径，但代价是需要遍历大量节点，效率在大型地图上会成为瓶颈。其核心流程可以概括为维护一个“待探索节点集合”，每次从中取出距离起点最近的节点进行扩展。

// 一个简化的Dijkstra算法思想示意（非完整实现）
public List<Node> DijkstraFindPath(Node start, Node goal) {
    PriorityQueue<Node> openSet = new PriorityQueue<Node>();
    Dictionary<Node, float> gScore = new Dictionary<Node, float>(); // 从起点到该节点的实际代价
    Dictionary<Node, Node> cameFrom = new Dictionary<Node, Node>();

    openSet.Enqueue(start, 0);
    gScore[start] = 0;

    while (openSet.Count > 0) {
        Node current = openSet.Dequeue();
        if (current == goal) {
            return ReconstructPath(cameFrom, current); // 回溯路径
        }

        foreach (Node neighbor in GetNeighbors(current)) {
            float tentativeGScore = gScore[current] + GetCost(current, neighbor);
            if (!gScore.ContainsKey(neighbor) || tentativeGScore < gScore[neighbor]) {
                cameFrom[neighbor] = current;
                gScore[neighbor] = tentativeGScore;
                // 关键：Dijkstra的优先级仅由gScore决定
                openSet.Enqueue(neighbor, gScore[neighbor]);
            }
        }
    }
    return null; // 未找到路径
}

A*算法在Dijkstra的基础上引入了启发式函数（Heuristic Function），通常记为 h(n)，用于估算从当前节点 n 到目标点的剩余代价。算法在选择下一个要探索的节点时，不再只看已付出的代价 g(n)，而是综合考虑 g(n) + h(n)，即 f(n)。一个设计良好的启发函数（如曼哈顿距离、欧几里得距离）能引导搜索方向直奔目标，大幅减少不必要的探索，在保证找到最短路径（当h(n)是可采纳且一致时）的前提下，效率显著提升。

注意：启发函数的选择至关重要。对于允许对角移动的网格，欧几里得距离（直线距离）是常用选择；对于仅允许四方向移动的网格，曼哈顿距离更合适。h(n) 必须永远不大于从节点n到目标的实际代价，否则可能找不到最优解。

然而，无论是Dijkstra还是A*，都是离线规划算法。它们假设世界是静态的，规划一次，执行到底。但在真实的游戏世界里，障碍物会移动（怪物、其他NPC），地形会改变（玩家建造了墙壁、炸毁了桥梁），甚至目标点本身也会变化（玩家改变了指令）。如果每次环境变化都重新运行一次完整的A*，计算开销将难以承受。这正是动态寻路算法登场的舞台。

2. D*Lite：应对动态环境的增量式寻路利器

D*（D-Star）及其优化版本D*Lite，是专门为动态未知环境设计的增量式搜索算法。其核心思想非常巧妙：从目标点向起点进行反向搜索，并记住搜索过程中得到的所有信息。当环境发生变化（如出现新障碍）时，算法不是从头开始，而是只更新受影响的局部信息，并利用之前的信息快速重新规划。

可以把DLite理解为一个“有记忆的A”。它维护两个关键值：

1. g(s)：与A*类似，表示从起点到节点s的当前最佳代价估计。
2. rhs(s)（Right Hand Side）：一个更具动态性的值，表示基于节点s的父节点的g值计算出的“一步前瞻”代价。如果 g(s) == rhs(s)，我们说节点s是局部一致的；否则就是局部过一致（g > rhs，代价被高估了）或局部欠一致（g < rhs，代价被低估了）。

D*Lite算法主要包含两个阶段：初始规划和动态修复。

• 初始规划：以目标点为起点，用类似A*的反向搜索，计算出一条初始路径及其各节点的g值和rhs值。
• 动态修复：当传感器检测到某条边(s, s')的通行代价 c(s, s') 增加（出现障碍）或减少（障碍消失）时，算法会更新受影响的rhs值，并将相关节点放入一个优先队列。然后，算法反复从队列中取出最需要处理的节点，修复其不一致状态，并波及其邻居，直到起点恢复局部一致或队列为空。这个过程通常只涉及图中很小的一部分。

下面的表格对比了A与DLite在处理动态障碍时的核心差异：

特性	A* 算法	D*Lite 算法
规划方向	正向（起点 -> 目标）	反向（目标 -> 起点）
环境假设	静态、完全已知	动态、部分已知或可变化
重规划策略	完全重新规划	增量式局部修复
计算开销	每次变化都需全局计算	仅更新受影响区域，开销小
内存开销	较低，规划完可释放	较高，需存储整个图的启发值和状态
适用场景	静态地图、一次性寻路	机器人导航、游戏动态避障、实时策略游戏

在Unity游戏开发中，DLite的价值在于，当NPC沿着A规划的路径移动时，如果前方突然出现一个玩家角色或一个动态生成的障碍物（比如《原神》中可莉的炸弹），NPC可以极快地重新计算出一条绕行路径，而不会出现明显的卡顿或愚蠢的“撞墙”行为。

3. Unity实战：构建混合寻路系统框架

理论再优美，也需要落地到代码。我们的目标是在Unity中创建一个寻路系统，它默认使用高效的A进行全局路径规划，同时在运行时利用DLite的思想进行动态障碍物的快速避障响应。

3.1 基础数据结构定义

首先，我们需要定义核心的数据结构。这里我们采用网格（Grid）作为底层表示，因为它直观且易于理解。

// Node.cs - 网格节点
public class Node : IHeapItem<Node>
{
    public bool walkable; // 是否可通行
    public Vector3 worldPosition; // 世界坐标
    public int gridX, gridY; // 网格坐标
    public int movementPenalty; // 地形移动惩罚值（如沼泽、雪地代价更高）

    // 用于A*/D*Lite计算
    public float gCost;
    public float hCost;
    public Node parent;
    private int heapIndex;

    public float fCost { get { return gCost + hCost; } }

    // IHeapItem接口实现，用于优化优先队列性能
    public int HeapIndex { get => heapIndex; set => heapIndex = value; }
    public int CompareTo(Node nodeToCompare) {
        int compare = fCost.CompareTo(nodeToCompare.fCost);
        if (compare == 0) {
            compare = hCost.CompareTo(nodeToCompare.hCost);
        }
        return -compare; // 返回负数，因为我们需要成本低的节点在前
    }
}

// Grid.cs - 管理整个寻路网格
public class PathfindingGrid : MonoBehaviour
{
    public LayerMask unwalkableMask; // 不可行走层
    public Vector2 gridWorldSize; // 网格覆盖的世界大小
    public float nodeRadius; // 节点半径
    Node[,] grid;
    float nodeDiameter;
    int gridSizeX, gridSizeY;

    void Awake() {
        nodeDiameter = nodeRadius * 2;
        gridSizeX = Mathf.RoundToInt(gridWorldSize.x / nodeDiameter);
        gridSizeY = Mathf.RoundToInt(gridWorldSize.y / nodeDiameter);
        CreateGrid();
    }

    void CreateGrid() {
        grid = new Node[gridSizeX, gridSizeY];
        Vector3 worldBottomLeft = transform.position - Vector3.right * gridWorldSize.x / 2 - Vector3.forward * gridWorldSize.y / 2;
        for (int x = 0; x < gridSizeX; x++) {
            for (int y = 0; y < gridSizeY; y++) {
                Vector3 worldPoint = worldBottomLeft + Vector3.right * (x * nodeDiameter + nodeRadius) + Vector3.forward * (y * nodeDiameter + nodeRadius);
                bool walkable = !(Physics.CheckSphere(worldPoint, nodeRadius, unwalkableMask));
                // 可以在这里根据地形类型（通过射线检测等）设置不同的movementPenalty
                int penalty = 0;
                grid[x, y] = new Node(walkable, worldPoint, x, y, penalty);
            }
        }
    }

    public Node NodeFromWorldPoint(Vector3 worldPosition) { ... } // 根据世界坐标获取对应节点
    public List<Node> GetNeighbours(Node node) { ... } // 获取一个节点的所有邻居（8方向或4方向）
}

3.2 A*寻路核心实现

有了网格和节点，我们可以实现标准的A*寻路器。这里的关键是使用二叉堆（Binary Heap）来优化开放列表（Open Set）的性能，避免在大量节点中线性查找最小F值的节点。

// PathfindingAStar.cs
public class PathfindingAStar {
    PathfindingGrid grid;

    public List<Node> FindPath(Vector3 startPos, Vector3 targetPos) {
        Node startNode = grid.NodeFromWorldPoint(startPos);
        Node targetNode = grid.NodeFromWorldPoint(targetPos);

        Heap<Node> openSet = new Heap<Node>(grid.MaxSize);
        HashSet<Node> closedSet = new HashSet<Node>();
        openSet.Add(startNode);

        while (openSet.Count > 0) {
            Node currentNode = openSet.RemoveFirst();
            closedSet.Add(currentNode);

            if (currentNode == targetNode) {
                return RetracePath(startNode, targetNode);
            }

            foreach (Node neighbour in grid.GetNeighbours(currentNode)) {
                if (!neighbour.walkable || closedSet.Contains(neighbour)) {
                    continue;
                }

                float newMovementCostToNeighbour = currentNode.gCost + GetDistance(currentNode, neighbour) + neighbour.movementPenalty;
                if (newMovementCostToNeighbour < neighbour.gCost || !openSet.Contains(neighbour)) {
                    neighbour.gCost = newMovementCostToNeighbour;
                    neighbour.hCost = GetDistance(neighbour, targetNode);
                    neighbour.parent = currentNode;

                    if (!openSet.Contains(neighbour))
                        openSet.Add(neighbour);
                    else
                        openSet.UpdateItem(neighbour); // 更新堆中位置
                }
            }
        }
        return null; // 路径不存在
    }

    List<Node> RetracePath(Node startNode, Node endNode) {
        List<Node> path = new List<Node>();
        Node currentNode = endNode;
        while (currentNode != startNode) {
            path.Add(currentNode);
            currentNode = currentNode.parent;
        }
        path.Reverse(); // 反转得到从起点到终点的路径
        return SmoothPath(path); // 可选：路径平滑处理
    }

    float GetDistance(Node nodeA, Node nodeB) {
        // 使用对角距离启发函数
        int dstX = Mathf.Abs(nodeA.gridX - nodeB.gridX);
        int dstY = Mathf.Abs(nodeA.gridY - nodeB.gridY);
        if (dstX > dstY)
            return 14 * dstY + 10 * (dstX - dstY);
        else
            return 14 * dstX + 10 * (dstY - dstX);
    }
}

至此，一个基础的静态A*寻路系统就完成了。但对于动态环境，这还不够。

4. 集成D*Lite思想：实现动态障碍物响应

我们不会完整实现一个学术标准的DLite，而是汲取其核心思想——增量式更新和反向搜索信息重用，来增强我们的A系统，使其能高效处理动态障碍。我们称之为“A* with Dynamic Repair”（A*动态修复）。

4.1 动态障碍物管理器

首先，我们需要一个系统来追踪动态障碍物及其影响的网格节点。

// DynamicObstacleManager.cs
public class DynamicObstacleManager : MonoBehaviour
{
    public PathfindingGrid grid;
    private Dictionary<GameObject, List<Node>> obstacleToNodesMap = new Dictionary<GameObject, List<Node>>();

    // 注册一个动态障碍物（如玩家角色、临时生成的物体）
    public void RegisterObstacle(GameObject obstacle, float radius) {
        Collider[] colliders = Physics.OverlapSphere(obstacle.transform.position, radius, grid.unwalkableMask);
        List<Node> affectedNodes = new List<Node>();
        foreach (var coll in colliders) {
            // 这里简化处理：将障碍物所在节点标记为不可行走
            Node node = grid.NodeFromWorldPoint(coll.transform.position);
            if (node != null && node.walkable) {
                node.walkable = false;
                affectedNodes.Add(node);
            }
        }
        obstacleToNodesMap[obstacle] = affectedNodes;
    }

    // 当障碍物移动时更新其影响
    public void UpdateObstacle(GameObject obstacle, Vector3 oldPos, Vector3 newPos, float radius) {
        DeregisterObstacle(obstacle);
        RegisterObstacle(obstacle, radius);
    }

    // 移除障碍物（物体被销毁或移出）
    public void DeregisterObstacle(GameObject obstacle) {
        if (obstacleToNodesMap.TryGetValue(obstacle, out List<Node> nodes)) {
            foreach (Node node in nodes) {
                node.walkable = true; // 恢复为可行走
                // 关键：通知寻路系统该节点代价已改变
                PathfindingManager.Instance.OnNodeCostChanged(node);
            }
            obstacleToNodesMap.Remove(obstacle);
        }
    }
}

4.2 增量式路径修复（D*Lite思想的应用）

当动态障碍物管理器通知某个节点的通行状态改变时，我们的寻路系统不能简单地让所有正在移动的NPC重新进行全局A*搜索。相反，我们可以为每个正在寻路的Agent维护一个“受影响的路径段”列表，并尝试进行局部修复。

// DynamicPathAgent.cs - 具备动态避障能力的移动代理
public class DynamicPathAgent : MonoBehaviour
{
    private List<Node> currentPath;
    private int targetIndex;
    private PathfindingAStar pathfinder;
    private DynamicObstacleManager obstacleManager;

    void Start() {
        pathfinder = new PathfindingAStar();
        // 订阅节点变化事件
        PathfindingManager.Instance.NodeCostChanged += OnNodeCostChangedInPath;
    }

    public void SetDestination(Vector3 target) {
        // 初始使用A*规划全局路径
        currentPath = pathfinder.FindPath(transform.position, target);
        targetIndex = 0;
        StopCoroutine("FollowPath");
        StartCoroutine("FollowPath");
    }

    IEnumerator FollowPath() {
        if (currentPath == null || currentPath.Count == 0) yield break;

        Node currentWaypoint = currentPath[0];
        while (true) {
            if (Vector3.Distance(transform.position, currentWaypoint.worldPosition) < 0.1f) {
                targetIndex++;
                if (targetIndex >= currentPath.Count) {
                    yield break; // 到达终点
                }
                currentWaypoint = currentPath[targetIndex];
            }
            // 移动逻辑...
            yield return null;
        }
    }

    // 当路径上的节点状态改变时触发
    private void OnNodeCostChangedInPath(Node changedNode) {
        // 检查受影响的节点是否在当前路径上，且位于前方
        int indexInPath = currentPath.IndexOf(changedNode);
        if (indexInPath != -1 && indexInPath >= targetIndex) {
            // 情况1：节点变得不可通行（如被玩家挡住）
            if (!changedNode.walkable) {
                Debug.Log($"路径在节点 {changedNode.gridX},{changedNode.gridY} 被阻挡，尝试局部重规划");
                AttemptLocalRepair(changedNode, indexInPath);
            }
            // 情况2：节点恢复通行（障碍物移开），可以忽略或优化路径
        }
    }

    private void AttemptLocalRepair(Node blockedNode, int blockedIndex) {
        // 局部重规划策略（简化版D*Lite思想）：
        // 1. 以当前位置为起点
        // 2. 以原路径上阻塞点之后的一个“安全”节点为临时终点（例如 blockedIndex + 3 的节点，或原终点）
        // 3. 在局部范围内（例如只考虑周围一定网格）进行A*搜索
        // 4. 如果找到新路径，则替换原路径的阻塞段；如果找不到，则回退到全局重规划

        Node localStart = currentPath[Mathf.Max(0, targetIndex - 1)]; // 从当前位置前一个路点开始
        Node localGoal = (blockedIndex + 3 < currentPath.Count) ? currentPath[blockedIndex + 3] : currentPath[currentPath.Count - 1];

        // 创建一个临时的、范围受限的网格视图进行搜索，提升效率
        List<Node> localPath = pathfinder.FindPathLocal(localStart, localGoal, blockedNode, 5); // 搜索半径5格

        if (localPath != null && localPath.Count > 0) {
            // 拼接路径：原路径[0...targetIndex] + 新局部路径 + 原路径[localGoal之后...]
            List<Node> newFullPath = new List<Node>();
            for (int i = 0; i <= targetIndex; i++) {
                newFullPath.Add(currentPath[i]);
            }
            newFullPath.AddRange(localPath);
            int goalIndexInOriginal = currentPath.IndexOf(localGoal);
            for (int i = goalIndexInOriginal + 1; i < currentPath.Count; i++) {
                newFullPath.Add(currentPath[i]);
            }
            currentPath = newFullPath;
            Debug.Log("局部重规划成功，路径已更新。");
        } else {
            Debug.Log("局部重规划失败，执行全局重规划。");
            SetDestination(currentPath[currentPath.Count - 1].worldPosition); // 重新规划到最终目标
        }
    }
}

4.3 地形权重与怪物移动预测

在《原神》这类游戏中，不同地形对移动速度的影响（如草地、沙地、水面）以及怪物的巡逻、追击行为，都需要纳入寻路考量。

• 地形权重：我们在 Node 类中已经预留了 movementPenalty 字段。可以在创建网格时，通过射线检测地面标签或纹理，为节点分配不同的惩罚值。在A*计算 gCost 时直接加上这个惩罚值，寻路算法就会自动偏好走“好走”的路。
• 怪物移动预测：对于需要追击玩家的怪物，简单的“每帧重新计算到玩家当前位置的路径”会导致路径抖动且不自然。更好的策略是：
  1. 预测玩家位置：根据玩家当前速度和方向，预测未来几帧后的位置，以此作为寻路目标。
  2. 路径平滑与转向：对计算出的路径进行平滑处理（如使用Catmull-Rom样条），并使怪物转向时具有平滑的角速度，避免生硬的折线移动。
  3. 行为状态机：将寻路与行为树（Behavior Tree）或状态机结合。例如，怪物在“巡逻”状态下使用固定的路径点循环；在“警戒”状态下缓慢靠近玩家；在“追击”状态下使用动态寻路；在“返回”状态下使用A*计算回到巡逻点的路径。

// 示例：简单的玩家位置预测
public Vector3 PredictPlayerPosition(Transform player, float predictionTime) {
    Rigidbody playerRb = player.GetComponent<Rigidbody>();
    if (playerRb != null && playerRb.velocity.magnitude > 0.1f) {
        // 基于速度和简单线性预测
        return player.position + playerRb.velocity * predictionTime;
    }
    // 如果玩家静止或速度很慢，直接返回当前位置
    return player.position;
}

将A的静态全局规划能力与DLite启发的动态局部修复策略相结合，我们就能在Unity中构建出一个既高效又灵活的寻路系统。它能够处理复杂的地形成本，响应实时的环境变化，并为游戏角色赋予更智能、更自然的移动行为。这套方案的核心在于理解不同算法的适用场景，并敢于对经典算法进行符合游戏开发需求的改造和简化。在实际项目中，还需要结合对象池管理路径请求、多线程异步计算、以及与动画系统的深度融合，才能打造出真正媲美3A大作的角色移动体验。