游戏 AI / 系统课时
处理起点终点不可达情况
处理起点终点不可达情况
A* 不只是“找到一条路径”或“返回空列表”。在真实 NPC 系统里,起点非法、终点非法和搜索空间耗尽代表完全不同的问题。本节把搜索结果改成显式状态,让调用方能决定重试、换目标还是停止移动,避免空路径被误当成“已经到达”。
学习目标
- 区分起点非法、终点非法、搜索耗尽和成功四类结果
- 用结构化返回值替代
None或空数组,避免调用方误判 - 在 NPC 行为层根据失败类型选择安全的后续动作
先定义什么叫“失败”
最危险的设计是让 A* 在所有失败情况下都返回 []。空路径既可能表示起点就是终点,也可能表示目标落在墙里,还可能表示整个可达区域已经搜索完仍找不到终点。调用方无法判断原因,就容易继续移动、反复重算,甚至把 NPC 状态机卡在循环里。
一个可用的搜索模块至少应区分四种结果:
| 状态 | 含义 | 调用方常见处理 |
|---|---|---|
SUCCESS |
已找到路径 | 按路径移动 |
INVALID_START |
起点越界或不可通行 | 修正角色位置或重新采样起点 |
INVALID_GOAL |
终点越界或不可通行 | 重新采样目标或更换目标 |
NO_PATH |
起终点合法,但搜索耗尽 | 换目标、等待地图变化或进入兜底行为 |
这里把“搜索耗尽”单独定义成 NO_PATH,因为它说明输入本身合法,只是当前地图拓扑上不存在连通路径。

用结构化结果封装搜索
下面是一个可直接运行的最小网格 A*。PathResult 同时携带状态和路径;只有 SUCCESS 才会返回实际路径,其余状态的路径为空。
from dataclasses import dataclass
from enum import Enum
import heapq
class PathStatus(Enum):
SUCCESS = 'success'
INVALID_START = 'invalid_start'
INVALID_GOAL = 'invalid_goal'
NO_PATH = 'no_path'
@dataclass
class PathResult:
status: PathStatus
path: list[tuple[int, int]]
def astar(grid: list[list[int]], start: tuple[int, int], goal: tuple[int, int]) -> PathResult:
rows, cols = len(grid), len(grid[0])
def walkable(p: tuple[int, int]) -> bool:
r, c = p
return 0 <= r < rows and 0 <= c < cols and grid[r][c] == 0
# 搜索前先拒绝非法输入,避免把输入错误误报成无路可走。
if not walkable(start):
return PathResult(PathStatus.INVALID_START, [])
if not walkable(goal):
return PathResult(PathStatus.INVALID_GOAL, [])
if start == goal:
return PathResult(PathStatus.SUCCESS, [start])
def heuristic(a: tuple[int, int], b: tuple[int, int]) -> int:
return abs(a[0] - b[0]) + abs(a[1] - b[1])
open_heap = [(heuristic(start, goal), 0, start)]
g_score = {start: 0}
came_from: dict[tuple[int, int], tuple[int, int]] = {}
while open_heap:
_, current_g, current = heapq.heappop(open_heap)
if current_g != g_score.get(current):
continue
if current == goal:
path = [current]
while current in came_from:
current = came_from[current]
path.append(current)
path.reverse()
return PathResult(PathStatus.SUCCESS, path)
r, c = current
for neighbor in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
if not walkable(neighbor):
continue
next_g = current_g + 1
if next_g < g_score.get(neighbor, float('inf')):
g_score[neighbor] = next_g
came_from[neighbor] = current
f = next_g + heuristic(neighbor, goal)
heapq.heappush(open_heap, (f, next_g, neighbor))
# Open Set 被取空仍未到达目标,才是真正的“搜索耗尽”。
return PathResult(PathStatus.NO_PATH, [])
if __name__ == '__main__':
grid = [
[0, 0, 0],
[1, 1, 1],
[0, 0, 0],
]
cases = [
((-1, 0), (0, 2)),
((0, 0), (1, 1)),
((0, 0), (2, 2)),
((0, 0), (0, 2)),
]
for start, goal in cases:
result = astar(grid, start, goal)
print(result.status.value, result.path)预期输出:
invalid_start []
invalid_goal []
no_path []
success [(0, 0), (0, 1), (0, 2)]这个实现还有一个容易忽略的边界:start == goal 时返回包含起点的单节点路径,而不是空路径。这样调用方仍然得到明确的 SUCCESS,不会把“无需移动”误判成搜索失败。
让调用方按状态处理
搜索模块负责回答“结果是什么”,行为层负责回答“接下来做什么”。SUCCESS 可以进入路径跟随;INVALID_START 更适合修正角色所在位置;INVALID_GOAL 可以重新采样附近可通行点;NO_PATH 则应换目标、等待地图变化或执行兜底行为。
| 搜索结果 | 推荐动作 |
|---|---|
SUCCESS |
跟随返回路径 |
INVALID_START |
修正或重新放置 NPC |
INVALID_GOAL |
重新采样目标位置 |
NO_PATH |
换目标、等待或进入兜底状态 |
这种分层还有一个好处:A* 不需要知道 NPC 是巡逻、追击还是撤退。它只返回稳定的结果协议,具体行为策略由上层决定。
避免把失败变成重算风暴
起点或终点非法通常是输入问题,修正输入后再搜索;NO_PATH 则是拓扑问题,应等待目标变化、障碍变化或冷却时间结束后再尝试。若每帧对同一个不可达目标重新运行 A*,失败本身就会变成性能问题。
当搜索结果能够明确表达“为什么没走成”,NPC 才能安全地停止、修正或降级,而不是把所有异常都交给移动层猜测。