游戏 AI / 系统课时

只重算受影响的局部路径

只重算受影响的局部路径

动态地图发生变化时,最简单的做法是从角色当前位置到终点重新运行一次完整 A*,但很多变化只影响原路径的一小段。本课将把地图变化映射到剩余路径,找到局部重算的起点与重新接回旧路径的位置,减少无意义的搜索范围。

学习目标

  • 判断地图变化是否真正命中当前剩余路径
  • 根据受影响节点确定局部重算窗口和重接锚点
  • 知道局部重算失败时什么时候必须退回完整寻路

先判断变化是否碰到剩余路径

局部重算的第一步不是立即搜索,而是求动态变化区域与当前路径的交集。假设路径已经走到索引 1,地图只修改了远离路径的一组格子,那么现有路线仍可继续使用,A* 根本不需要再次执行。

如果变化命中了剩余路径,则记录最早和最晚受影响的位置。这个范围描述了旧路径中已经不能直接信任的部分,也是后续选择局部搜索窗口的依据。

相比“所有地图变化都触发所有角色重算”,这种做法把触发条件缩小为:地图变化区域与角色剩余路径存在交集。

局部重算要找到两个可靠锚点

受影响区间确定后,需要选择局部新路径的起点与终点。起点通常取受影响区域之前仍然安全的节点,或者直接使用角色当前所在节点;终点则选择受影响区域之后仍可到达的旧路径节点。

例如旧路径为 P0 -> P1 -> P2 -> P3 -> P4 -> P5 -> P6,角色当前位于 P1,而 P3、P4 因障碍变化失效,可以尝试只搜索 P2 -> P5 的替代路线。成功后将新片段重新拼接进旧路径,而 P5 -> P6 无需再次搜索。

动态路径局部重算与重新接回旧路径

局部窗口不能切得过紧。如果新的障碍恰好封住原路径附近的小区域,搜索范围只覆盖失效节点本身时可能根本找不到绕路空间。工程中通常会给受影响范围增加一定安全边界,或者允许局部搜索在需要时向外扩张。

用代码找出需要重算的路径片段

下面的可运行示例根据发生变化的格子,找到剩余路径中最早和最晚受影响的索引,再各向外保留一个安全节点作为局部重算锚点。

csharp
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]}");
    }
}

预期输出:

text
Local start index: 2
Rejoin index: 5
Replan from (2, 0) to (5, 0)

这段程序只负责确定局部搜索的边界。真正执行时,可以把 path[start] 与 path[end] 分别作为局部 A* 的起点和目标;搜索成功后,用新路径替换旧路径的这一段,并保留未受影响的后缀。

局部搜索失败时要允许扩大范围

局部重算是一种优化,不应改变“最终必须找到合法路径”这一正确性目标。如果原来的重接锚点已经无法到达,算法可以继续尝试更靠后的旧路径节点;仍然失败时,再退回从角色当前位置到最终目标的完整 A*。

常见的退化顺序可以保持简单:先验证变化是否命中剩余路径,命中后尝试局部重算,局部搜索没有找到可行连接时扩大窗口,最后才执行完整重算。这样既避免为一次小障碍变化搜索整张地图,也不会因为过度坚持局部路径而把角色困在已经改变的拓扑中。

局部重算真正节省的不是一次搜索中的几步循环,而是大量动态单位反复面对小范围变化时的总搜索量。只要受影响区间、重接锚点和全局回退机制都明确,局部重算就能在保持路径正确性的同时显著减少无效计算。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

只重算受影响的局部路径

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通