游戏 AI / 系统课时
障碍物变化后为什么原路失效
障碍物变化后为什么原路失效
A* 计算出的路径只保证在计算当时的地图状态下可行。如果角色尚未走完路径,门关闭、箱子移动或地形状态改变,后续节点就可能从可通行变为不可通行。本课重点解决如何识别这种时间差,并在角色真正撞上障碍前发现失效路径。
学习目标
- 理解路径规划结果为什么会因地图变化而过期
- 区分当前位置、剩余路径与动态障碍之间的失效条件
- 在移动执行前验证路径并触发重新寻路
路径有效性依赖生成时的地图快照
A* 搜索时读取的是某一时刻的地图状态。假设角色在时间 得到路径 S -> A -> B -> C -> G,搜索完成后这条路径通常只是保存为节点或世界坐标序列,并不会自动随着地图变化而更新。
如果时间 时某个动态障碍占据了 C,角色仍可能继续按照旧路径移动。此时问题并不是 A* 算错,而是路径使用的地图版本已经落后于真实地图。

路径失效通常来自三类变化:原来的节点变成不可通行、两个节点之间的移动关系被切断,或者地形代价发生明显变化,使原路径虽然还能走,却已经不再值得继续执行。
什么时候应该判定旧路径失效
最直接的规则不是“地图一变化就重算”,而是检查变化是否真正影响角色尚未执行的路径。
例如角色已经走过 S 和 A,障碍物后来出现在 S 附近,就没有必要处理;如果障碍出现在即将经过的 C,则必须重新寻路。实际判断时应关注当前位置之后的剩余路径,而不是整条历史路径。
除了节点本身,还要考虑角色体积和移动边。一个格子中心仍标记为可通行,并不意味着角色一定能从前一个格子安全进入它。使用较大碰撞半径、斜向移动或连续空间导航时,还需要验证通道宽度和边是否仍可通过。
在移动前检查剩余路径
下面用一个最小 C# 示例模拟角色已经走到路径索引 1,随后动态障碍占据后续节点 (2, 0)。程序只检查尚未执行的节点,并返回第一个失效位置。
using System;
using System.Collections.Generic;
public class Program
{
static int FindFirstBlocked(
List<(int x, int y)> path,
int currentIndex,
HashSet<(int x, int y)> blocked)
{
// 已走过的节点不再参与有效性判断,只检查剩余路径。
for (int i = currentIndex + 1; i < path.Count; i++)
{
if (blocked.Contains(path[i]))
{
return i;
}
}
return -1;
}
public static void Main()
{
var path = new List<(int x, int y)>
{
(0, 0), (1, 0), (2, 0), (3, 0)
};
int currentIndex = 1;
var blocked = new HashSet<(int x, int y)> { (2, 0) };
int invalidIndex = FindFirstBlocked(path, currentIndex, blocked);
if (invalidIndex >= 0)
{
var node = path[invalidIndex];
Console.WriteLine($"Path invalid at index {invalidIndex}: ({node.x}, {node.y})");
Console.WriteLine("Replan required");
}
else
{
Console.WriteLine("Remaining path is valid");
}
}
}预期输出:
Path invalid at index 2: (2, 0)
Replan required这个检查并没有重新运行 A*,它只负责回答“旧路径还能不能继续使用”。确认失效后,再把当前可通行位置作为新的起点执行重算,可以把路径验证与路径规划职责分开。
动态地图下不要把所有变化都当成重算信号
如果任何障碍变化都让所有角色重新执行 A*,几十个 NPC 同时存在时很容易形成计算尖峰。更合理的处理方式是让地图变化携带受影响区域,只通知路径穿过这些区域的角色进行验证。
同样,短暂出现后立即消失的障碍也不一定值得立刻全局重算。游戏可以根据障碍持续时间、角色与障碍的距离以及当前剩余路径长度决定是等待、局部绕行还是重新规划。
因此,动态寻路的关键不是让 A* 持续运行,而是维护“地图状态—剩余路径—角色当前位置”之间的一致性。只要在执行危险路段前及时发现旧路径已经不成立,就能把路径失效从角色卡住后的故障,变成可控的重新规划事件。