游戏 AI / 系统课时

为什么明明有路却搜不到

为什么明明有路却搜不到

A* 返回“无路径”时,先不要急着改启发式函数。多数故障发生在搜索之前:起点或终点落在不可通行格、地图实际被障碍切断、邻接规则与关卡设计不一致,或者运行时障碍状态没有同步。按固定顺序排查,能快速判断问题究竟出在地图数据还是搜索逻辑。

学习目标

  • 按起点、终点、连通性、邻接规则的顺序定位不可达问题
  • 用独立连通性检查区分“地图本身无路”和“A*实现有错”
  • 识别障碍状态、切角规则与运行时地图更新造成的假性不可达

先确认起点和终点真的可搜索

A* 只能在搜索图上工作。画面里角色站在地面上,不代表对应网格一定可通行。最先检查起点与终点是否成功映射到合法节点,以及这些节点的 walkable 状态是否为真。

常见问题包括:世界坐标映射发生边界取整错误、终点位于墙体或装饰碰撞体内、动态障碍刚好覆盖目标格,以及地图重建后仍拿着旧节点引用。只要起点或终点无效,继续分析开放集合和启发式都没有意义。

用连通性检查切开问题范围

最有效的诊断方法,是暂时绕开 A* 的启发式与优先队列,只用 BFS 检查“按当前邻接规则,起点和终点是否连通”。如果 BFS 也到不了,问题在地图、障碍或邻接关系;如果 BFS 能到而 A* 不能到,才重点检查 A* 的代价更新、开放集合和关闭集合。

下面脚本构造一张 5×5 网格,纵向障碍把左右两侧完全隔开,因此 BFS 会明确返回不可达。

python
from collections import deque

grid = [
    "S.#..",
    "..#..",
    "..#..",
    "..#..",
    "..#.G",
]

rows = len(grid)
cols = len(grid[0])

def find(ch):
    for r, row in enumerate(grid):
        for c, value in enumerate(row):
            if value == ch:
                return r, c
    raise ValueError(f"missing {ch}")

def reachable(start, goal):
    q = deque([start])
    visited = {start}
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    while q:
        r, c = q.popleft()
        if (r, c) == goal:
            return True

        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if not (0 <= nr < rows and 0 <= nc < cols):
                continue
            if grid[nr][nc] == "#" or (nr, nc) in visited:
                continue
            visited.add((nr, nc))
            q.append((nr, nc))

    return False

start = find("S")
goal = find("G")
print("start =", start)
print("goal =", goal)
print("reachable =", reachable(start, goal))

预期输出:

text
start = (0, 0)
goal = (4, 4)
reachable = False

如果把障碍列中任意一个 # 改成 .,再运行脚本,连通性可能恢复。这个测试不证明 A* 一定正确,但能把排查范围大幅缩小。

A*不可达问题的分层排查流程

邻接规则经常制造“看起来有路”

地图视觉上存在缝隙,不代表邻接模型允许通过。四方向移动只能上下左右;八方向移动才允许斜向。如果地图设计依赖对角穿行,而算法只生成四方向邻居,某些区域就会被判定为断开。

反过来,允许八方向移动时还要决定是否允许“切角”。例如当前位置右侧和上侧都是墙,但右上角是空地;如果仍允许一步斜移到右上角,角色会穿过墙角。很多实现会规定只有相邻两个正交格都可通行时,才允许对角移动。

因此排查时必须确认地图设计规则与邻居生成规则完全一致,而不是只看是否开启斜向。

障碍状态要和搜索图保持同一时刻

运行时门、箱子、陷阱或其他动态物体都会改变可通行性。最容易出现的问题不是算法算错,而是画面已经变化,搜索图还保留旧状态。

可以按时间顺序核对:障碍发生变化后是否更新对应节点,更新完成后是否再发起寻路,旧路径是否需要失效,以及缓存的邻接关系是否仍依赖旧障碍状态。若地图采用分块或异步重建,还要避免在导航数据尚未就绪时提交路径请求。

什么时候该怀疑 A* 实现

只有在起点、终点合法,BFS 按同一邻接规则确认可达,障碍状态也完成同步之后,才进入 A* 内部排查。此时重点看三件事:更低的 g 是否能更新旧记录、开放集合中的优先级是否随新 f 生效、节点是否过早进入关闭集合且永不允许改进。

排查“明明有路却搜不到”的关键,是先证明搜索图上确实存在一条符合当前移动规则的路。这样每一步都有明确结论,而不是在启发式、优先队列和地图数据之间反复猜测。

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

目录与阅读设置

阅读设置

17

记录一个想法

为什么明明有路却搜不到

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

登录哪都通