游戏 AI / 系统课时
只重算受影响的局部路径
只重算受影响的局部路径
动态地图发生变化时,最简单的做法是从角色当前位置到终点重新运行一次完整 A*,但很多变化只影响原路径的一小段。本课将把地图变化映射到剩余路径,找到局部重算的起点与重新接回旧路径的位置,减少无意义的搜索范围。
学习目标
- 判断地图变化是否真正命中当前剩余路径
- 根据受影响节点确定局部重算窗口和重接锚点
- 知道局部重算失败时什么时候必须退回完整寻路
先判断变化是否碰到剩余路径
局部重算的第一步不是立即搜索,而是求动态变化区域与当前路径的交集。假设路径已经走到索引 1,地图只修改了远离路径的一组格子,那么现有路线仍可继续使用,A* 根本不需要再次执行。
如果变化命中了剩余路径,则记录最早和最晚受影响的位置。这个范围描述了旧路径中已经不能直接信任的部分,也是后续选择局部搜索窗口的依据。
相比“所有地图变化都触发所有角色重算”,这种做法把触发条件缩小为:地图变化区域与角色剩余路径存在交集。
局部重算要找到两个可靠锚点
受影响区间确定后,需要选择局部新路径的起点与终点。起点通常取受影响区域之前仍然安全的节点,或者直接使用角色当前所在节点;终点则选择受影响区域之后仍可到达的旧路径节点。
例如旧路径为 P0 -> P1 -> P2 -> P3 -> P4 -> P5 -> P6,角色当前位于 P1,而 P3、P4 因障碍变化失效,可以尝试只搜索 P2 -> P5 的替代路线。成功后将新片段重新拼接进旧路径,而 P5 -> P6 无需再次搜索。

局部窗口不能切得过紧。如果新的障碍恰好封住原路径附近的小区域,搜索范围只覆盖失效节点本身时可能根本找不到绕路空间。工程中通常会给受影响范围增加一定安全边界,或者允许局部搜索在需要时向外扩张。
用代码找出需要重算的路径片段
下面的可运行示例根据发生变化的格子,找到剩余路径中最早和最晚受影响的索引,再各向外保留一个安全节点作为局部重算锚点。
using System;
using System.Collections.Generic;
public class Program
{
static (int start, int end)? FindReplanWindow(
List<(int x, int y)> path,
int currentIndex,
HashSet<(int x, int y)> changedCells)
{
int first = -1;
int last = -1;
for (int i = currentIndex + 1; i < path.Count; i++)
{
if (!changedCells.Contains(path[i]))
{
continue;
}
if (first < 0)
{
first = i;
}
last = i;
}
if (first < 0)
{
return null;
}
// 向受影响区间两侧各保留一个旧路径节点,作为局部搜索锚点。
int start = Math.Max(currentIndex, first - 1);
int end = Math.Min(path.Count - 1, last + 1);
return (start, end);
}
public static void Main()
{
var path = new List<(int x, int y)>
{
(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0)
};
int currentIndex = 1;
var changedCells = new HashSet<(int x, int y)>
{
(3, 0), (4, 0)
};
var window = FindReplanWindow(path, currentIndex, changedCells);
if (window is null)
{
Console.WriteLine("Remaining path unaffected");
return;
}
var value = window.Value;
Console.WriteLine($"Local start index: {value.start}");
Console.WriteLine($"Rejoin index: {value.end}");
Console.WriteLine($"Replan from {path[value.start]} to {path[value.end]}");
}
}预期输出:
Local start index: 2
Rejoin index: 5
Replan from (2, 0) to (5, 0)这段程序只负责确定局部搜索的边界。真正执行时,可以把 path[start] 与 path[end] 分别作为局部 A* 的起点和目标;搜索成功后,用新路径替换旧路径的这一段,并保留未受影响的后缀。
局部搜索失败时要允许扩大范围
局部重算是一种优化,不应改变“最终必须找到合法路径”这一正确性目标。如果原来的重接锚点已经无法到达,算法可以继续尝试更靠后的旧路径节点;仍然失败时,再退回从角色当前位置到最终目标的完整 A*。
常见的退化顺序可以保持简单:先验证变化是否命中剩余路径,命中后尝试局部重算,局部搜索没有找到可行连接时扩大窗口,最后才执行完整重算。这样既避免为一次小障碍变化搜索整张地图,也不会因为过度坚持局部路径而把角色困在已经改变的拓扑中。
局部重算真正节省的不是一次搜索中的几步循环,而是大量动态单位反复面对小范围变化时的总搜索量。只要受影响区间、重接锚点和全局回退机制都明确,局部重算就能在保持路径正确性的同时显著减少无效计算。