Relog JOURNAL
返回归档

RELOG / ARTICLE

AI 味冲鼻 · 别看了

A*寻路

K

修订说明（2026-11）：补充最优路径的前提，并标明示例代码的适用范围。

A*寻路算法详解

A* 算法广泛用于图搜索和路径规划，用启发式估值决定优先探索哪些节点。它以已知路径代价 g 加上到目标的估计代价 h 排序；当 h = 0 时退化为 Dijkstra 算法。它能否找到最低代价路径、搜索是否更快，都取决于启发式、边权和具体实现。

F = G + H

  • F：表示从起点通过当前节点到达终点的总估值。是对节点的综合评估，用来决定下一个要探索的节点。
  • G：从起点到当前节点的实际代价。通常是路径长度，也可以结合其他因素（如地形难度、移动消耗等）。
  • H：从当前节点到终点的估计代价。四方向等代价网格常用曼哈顿距离；允许对角移动时应按移动规则选择对角距离或其他估计。若要保证最优解，启发式不能高估剩余的真实最低代价；“没有障碍物”本身不是选择公式的充分条件。

A* 寻路算法的详细步骤

  1. 起点与终点初始化：将起点放入待搜索列表，并初始化其G和H值。通常，起点的G值为0，H值为到终点的估计距离。
  2. 选择最优节点：从待搜索列表中选择F值最小的节点，作为当前节点进行探索。如果F值相同，可以选择H值较小的节点（靠近终点的）来打破平局。
  3. 探索相邻节点：计算从当前节点到邻居的新 G 值；如果找到更低代价，就更新邻居的 G 值和父节点，并更新它在待搜索集合中的优先级。非一致启发式下，已关闭的节点也可能需要重新打开。
  4. 检查终点：如果当前节点为终点，算法结束，构建路径。否则，返回步骤2继续搜索。
  5. 构建路径：通过回溯每个节点的父节点，构建从终点到起点的完整路径。

路径平滑与优化

  1. 路径平滑处理：
    • Catmull-Rom Spline：可用于平滑转向，但插值曲线可能越过障碍物，不能默认保持路径可行。
    • 贝塞尔曲线：也能让转向更平滑，同样需要碰撞检测、导航网格约束或回退策略。

下面的 PathManager 只展示缓存思路，CalculatePath 是占位方法， 并未实现完整的寻路算法。

public class PathManager
{
    private Dictionary<(Vector3 start, Vector3 end), List<Vector3>> pathPool = new Dictionary<(Vector3, Vector3), List<Vector3>>();

    public List<Vector3> GetPath(Vector3 start, Vector3 end)
    {
        // 检查池中是否已有从start到end的路径
        if (pathPool.TryGetValue((start, end), out var cachedPath))
        {
            return cachedPath;
        }

        // 如果没有缓存路径，则重新计算路径
        var newPath = CalculatePath(start, end);

        // 将新计算的路径存入池中
        pathPool[(start, end)] = newPath;

        return newPath;
    }

    private List<Vector3> CalculatePath(Vector3 start, Vector3 end)
    {
        // 这里调用A*算法计算路径
        // 省略具体实现，只需返回路径节点的List
        return new List<Vector3>();
    }

    public void ClearPathPool()
    {
        pathPool.Clear();
    }

    // 可以提供一种方法定期清理不再使用的路径
    public void ClearUnusedPaths()
    {
        // 根据使用频率或时间戳来清理池中不再需要的路径
    }
}
  • 缓存机制：只有起终点、移动规则、障碍物和地图版本等条件相同，缓存路径才可复用。动态地图必须有失效机制；缓存也要衡量命中率和内存开销，不能保证总能提速。
  • 局部更新：终点或障碍物变化后，有时可局部修补路径，但不能只因终点偏移小就断言原路径前半段仍是最优或可通行。

考虑的其他问题与解决方案

  1. 处理动态障碍物：

    • 路径重规划：在检测到路径上的动态障碍物时（如移动的敌人或其他NPC），可以触发路径重规划，或者使用临时避让机制（如Steering Behaviors）绕过障碍物。

    • 动态障碍物预测：通过预测障碍物的移动趋势，在路径规划时提前避开可能会被阻挡的路径。

public void RecalculatePathIfNecessary(Vector3 currentPosition, Vector3 targetPosition)
{
    if (IsPathBlocked(currentPath))
    {
        // 重新规划路径
        currentPath = pathManager.GetPath(currentPosition, targetPosition);
    }
}

private bool IsPathBlocked(List<Vector3> path)
{
    // 检查路径是否被动态障碍物阻挡
    // 返回布尔值表示是否需要重新规划路径
    return false;
}

路径节点精度：

  • 格子细分：将整个地图细分为更小的网格，提高路径节点的精度，从而使得NPC可以更精确地移动。
  • 导航网格（NavMesh）：可用于处理复杂地形。动态障碍物是否改变寻路结果取决于避障与 carving 等设置，不能把使用 NavMesh 等同于自动支持所有动态变化。

NPC的转向与移动平滑：

  • 转向与速度调整：结合Steering Behaviors中的Seek、Arrive等行为，让NPC在接近目标节点时逐渐减速并平滑转向，避免急停或突然转向。
public Vector3 GetSmoothMovement(Vector3 currentPos, Vector3 targetPos, float maxSpeed, float turnSpeed)
{
    Vector3 desiredDirection = (targetPos - currentPos).normalized;
    Vector3 currentVelocity = currentPos - previousPosition; // 假设你有记录上一次的位置
    Vector3 steering = desiredDirection - currentVelocity;

    // 限制转向速度
    steering = Vector3.ClampMagnitude(steering, turnSpeed);

    // 计算新的速度向量
    Vector3 newVelocity = Vector3.ClampMagnitude(currentVelocity + steering, maxSpeed);

    // 更新位置
    return currentPos + newVelocity * Time.deltaTime;
}

路径的可视化与调试：

上面的移动代码也是示意：previousPosition、时间步长和速度单位需在实际项目中定义；碰撞与移动约束仍需另外处理。

  • 路径可视化：在开发过程中，可以通过绘制Gizmos来可视化路径，帮助调试和优化A*算法的实现。

  • 实时调试工具：使用Unity中的调试工具或自定义调试界面，实时监控NPC的路径选择、当前节点的F值等数据。

void OnDrawGizmos()
{
    if (currentPath != null)
    {
        Gizmos.color = Color.green;
        for (int i = 0; i < currentPath.Count - 1; i++)
        {
            Gizmos.DrawLine(currentPath[i], currentPath[i + 1]);
        }
    }
}

参考：A* 原始论文、启发式与移动规则说明、Unity NavMeshObstacle 文档。

#算法

读到这里，感谢你。

回到顶部