游戏 AI / 系统课时

障碍物变化后为什么原路失效

障碍物变化后为什么原路失效

A* 计算出的路径只保证在计算当时的地图状态下可行。如果角色尚未走完路径,门关闭、箱子移动或地形状态改变,后续节点就可能从可通行变为不可通行。本课重点解决如何识别这种时间差,并在角色真正撞上障碍前发现失效路径。

学习目标

  • 理解路径规划结果为什么会因地图变化而过期
  • 区分当前位置、剩余路径与动态障碍之间的失效条件
  • 在移动执行前验证路径并触发重新寻路

路径有效性依赖生成时的地图快照

A* 搜索时读取的是某一时刻的地图状态。假设角色在时间 t0t_0 得到路径 S -> A -> B -> C -> G,搜索完成后这条路径通常只是保存为节点或世界坐标序列,并不会自动随着地图变化而更新。

如果时间 t1t_1 时某个动态障碍占据了 C,角色仍可能继续按照旧路径移动。此时问题并不是 A* 算错,而是路径使用的地图版本已经落后于真实地图。

动态地图中路径从生成到失效的时间关系

路径失效通常来自三类变化:原来的节点变成不可通行、两个节点之间的移动关系被切断,或者地形代价发生明显变化,使原路径虽然还能走,却已经不再值得继续执行。

什么时候应该判定旧路径失效

最直接的规则不是“地图一变化就重算”,而是检查变化是否真正影响角色尚未执行的路径。

例如角色已经走过 S 和 A,障碍物后来出现在 S 附近,就没有必要处理;如果障碍出现在即将经过的 C,则必须重新寻路。实际判断时应关注当前位置之后的剩余路径,而不是整条历史路径。

除了节点本身,还要考虑角色体积和移动边。一个格子中心仍标记为可通行,并不意味着角色一定能从前一个格子安全进入它。使用较大碰撞半径、斜向移动或连续空间导航时,还需要验证通道宽度和边是否仍可通过。

在移动前检查剩余路径

下面用一个最小 C# 示例模拟角色已经走到路径索引 1,随后动态障碍占据后续节点 (2, 0)。程序只检查尚未执行的节点,并返回第一个失效位置。

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

预期输出:

text
Path invalid at index 2: (2, 0)
Replan required

这个检查并没有重新运行 A*,它只负责回答“旧路径还能不能继续使用”。确认失效后,再把当前可通行位置作为新的起点执行重算,可以把路径验证与路径规划职责分开。

动态地图下不要把所有变化都当成重算信号

如果任何障碍变化都让所有角色重新执行 A*,几十个 NPC 同时存在时很容易形成计算尖峰。更合理的处理方式是让地图变化携带受影响区域,只通知路径穿过这些区域的角色进行验证。

同样,短暂出现后立即消失的障碍也不一定值得立刻全局重算。游戏可以根据障碍持续时间、角色与障碍的距离以及当前剩余路径长度决定是等待、局部绕行还是重新规划。

因此,动态寻路的关键不是让 A* 持续运行,而是维护“地图状态—剩余路径—角色当前位置”之间的一致性。只要在执行危险路段前及时发现旧路径已经不成立,就能把路径失效从角色卡住后的故障,变成可控的重新规划事件。

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

目录与阅读设置

阅读设置

17

记录一个想法

障碍物变化后为什么原路失效

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

登录哪都通