游戏 AI / 系统课时
为什么明明有路却搜不到
为什么明明有路却搜不到
A* 返回“无路径”时,先不要急着改启发式函数。多数故障发生在搜索之前:起点或终点落在不可通行格、地图实际被障碍切断、邻接规则与关卡设计不一致,或者运行时障碍状态没有同步。按固定顺序排查,能快速判断问题究竟出在地图数据还是搜索逻辑。
学习目标
- 按起点、终点、连通性、邻接规则的顺序定位不可达问题
- 用独立连通性检查区分“地图本身无路”和“A*实现有错”
- 识别障碍状态、切角规则与运行时地图更新造成的假性不可达
先确认起点和终点真的可搜索
A* 只能在搜索图上工作。画面里角色站在地面上,不代表对应网格一定可通行。最先检查起点与终点是否成功映射到合法节点,以及这些节点的 walkable 状态是否为真。
常见问题包括:世界坐标映射发生边界取整错误、终点位于墙体或装饰碰撞体内、动态障碍刚好覆盖目标格,以及地图重建后仍拿着旧节点引用。只要起点或终点无效,继续分析开放集合和启发式都没有意义。
用连通性检查切开问题范围
最有效的诊断方法,是暂时绕开 A* 的启发式与优先队列,只用 BFS 检查“按当前邻接规则,起点和终点是否连通”。如果 BFS 也到不了,问题在地图、障碍或邻接关系;如果 BFS 能到而 A* 不能到,才重点检查 A* 的代价更新、开放集合和关闭集合。
下面脚本构造一张 5×5 网格,纵向障碍把左右两侧完全隔开,因此 BFS 会明确返回不可达。
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))预期输出:
start = (0, 0)
goal = (4, 4)
reachable = False如果把障碍列中任意一个 # 改成 .,再运行脚本,连通性可能恢复。这个测试不证明 A* 一定正确,但能把排查范围大幅缩小。

邻接规则经常制造“看起来有路”
地图视觉上存在缝隙,不代表邻接模型允许通过。四方向移动只能上下左右;八方向移动才允许斜向。如果地图设计依赖对角穿行,而算法只生成四方向邻居,某些区域就会被判定为断开。
反过来,允许八方向移动时还要决定是否允许“切角”。例如当前位置右侧和上侧都是墙,但右上角是空地;如果仍允许一步斜移到右上角,角色会穿过墙角。很多实现会规定只有相邻两个正交格都可通行时,才允许对角移动。
因此排查时必须确认地图设计规则与邻居生成规则完全一致,而不是只看是否开启斜向。
障碍状态要和搜索图保持同一时刻
运行时门、箱子、陷阱或其他动态物体都会改变可通行性。最容易出现的问题不是算法算错,而是画面已经变化,搜索图还保留旧状态。
可以按时间顺序核对:障碍发生变化后是否更新对应节点,更新完成后是否再发起寻路,旧路径是否需要失效,以及缓存的邻接关系是否仍依赖旧障碍状态。若地图采用分块或异步重建,还要避免在导航数据尚未就绪时提交路径请求。
什么时候该怀疑 A* 实现
只有在起点、终点合法,BFS 按同一邻接规则确认可达,障碍状态也完成同步之后,才进入 A* 内部排查。此时重点看三件事:更低的 g 是否能更新旧记录、开放集合中的优先级是否随新 f 生效、节点是否过早进入关闭集合且永不允许改进。
排查“明明有路却搜不到”的关键,是先证明搜索图上确实存在一条符合当前移动规则的路。这样每一步都有明确结论,而不是在启发式、优先队列和地图数据之间反复猜测。