游戏 AI / 系统课时
做一套NPC导航综合案例
做一套NPC导航综合案例
这一节把可通行网格、A* 搜索、地形代价、动态障碍检测、重新规划和 NPC 路径跟随接成一个完整闭环。最终得到一个可直接运行的最小导航系统:NPC 先走低成本路径,路径被动态障碍截断后重新搜索,并沿新路径到达目标。
学习目标
- 把地图数据、A* 规划器和 NPC 移动职责拆开,再通过路径结果连接起来。
- 在动态障碍使当前路径失效时停止使用旧路径并安全重算。
- 通过可运行案例验证地形代价、路径跟随和重规划是否真正形成闭环。
先把导航系统拆成几个责任
一个可用的 NPC 导航系统不能只有 astar() 函数。地图负责回答格子能不能走以及进入格子的代价;A* 只负责从起点搜索到终点;NPC 保存当前路径和路径索引;动态障碍改变地图后,还需要判断旧路径是否仍然有效。

这里最重要的边界是:A 不直接移动角色,角色移动也不自行修改搜索数据*。规划器只产生路径,移动模块只消费路径。这样以后即使替换寻路算法、加入八方向移动或把角色运动换成物理控制器,也不必重写整个系统。
实现一个可运行的最小系统
下面使用 Python 3.10+ 标准库实现完整案例。地图为 8×6 网格,只允许四方向移动;普通格代价为 1,泥地代价为 3。纵向墙体最初在 y=2 留有低成本通道,因此 NPC 会优先直行。
from dataclasses import dataclass
from enum import Enum
from heapq import heappop, heappush
Point = tuple[int, int]
class NavState(Enum):
IDLE = "IDLE"
PATH_PENDING = "PATH_PENDING"
MOVING = "MOVING"
ARRIVED = "ARRIVED"
FAILED = "FAILED"
@dataclass
class Grid:
width: int
height: int
blocked: set[Point]
terrain_cost: dict[Point, int]
def inside(self, point: Point) -> bool:
x, y = point
return 0 <= x < self.width and 0 <= y < self.height
def walkable(self, point: Point) -> bool:
return self.inside(point) and point not in self.blocked
def cost(self, point: Point) -> int:
return self.terrain_cost.get(point, 1)
def neighbors(self, point: Point):
x, y = point
# 固定邻居顺序,让示例路径和输出保持确定。
for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
neighbor = (x + dx, y + dy)
if self.walkable(neighbor):
yield neighbor
def heuristic(a: Point, b: Point) -> int:
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def astar(grid: Grid, start: Point, goal: Point) -> list[Point] | None:
if not grid.walkable(start) or not grid.walkable(goal):
return None
open_heap: list[tuple[int, int, Point]] = []
heappush(open_heap, (heuristic(start, goal), 0, start))
g_score: dict[Point, int] = {start: 0}
parent: dict[Point, Point] = {}
closed: set[Point] = set()
while open_heap:
_, _, current = heappop(open_heap)
if current in closed:
continue
if current == goal:
path = [current]
while current in parent:
current = parent[current]
path.append(current)
path.reverse()
return path
closed.add(current)
for neighbor in grid.neighbors(current):
if neighbor in closed:
continue
tentative_g = g_score[current] + grid.cost(neighbor)
if tentative_g >= g_score.get(neighbor, 10**9):
continue
# 找到更便宜的到达方式时,同时更新代价和父节点。
g_score[neighbor] = tentative_g
parent[neighbor] = current
f_score = tentative_g + heuristic(neighbor, goal)
heappush(open_heap, (f_score, tentative_g, neighbor))
return None
@dataclass
class NPC:
position: Point
goal: Point
state: NavState = NavState.IDLE
path: list[Point] | None = None
path_index: int = 0
def plan(self, grid: Grid) -> bool:
self.state = NavState.PATH_PENDING
self.path = astar(grid, self.position, self.goal)
if self.path is None:
self.state = NavState.FAILED
return False
self.path_index = 1
self.state = (
NavState.ARRIVED if len(self.path) == 1 else NavState.MOVING
)
return True
def step(self, grid: Grid) -> bool:
if self.state != NavState.MOVING or self.path is None:
return True
next_point = self.path[self.path_index]
# 移动前重新验证下一段,避免角色继续走进新障碍。
if not grid.walkable(next_point):
return False
self.position = next_point
self.path_index += 1
if self.path_index >= len(self.path):
self.state = NavState.ARRIVED
return True
def main() -> None:
grid = Grid(
width=8,
height=6,
blocked={(3, 0), (3, 1), (3, 4), (3, 5)},
terrain_cost={(2, 3): 3, (3, 3): 3, (4, 3): 3},
)
npc = NPC(position=(0, 2), goal=(7, 2))
npc.plan(grid)
print("initial path:", npc.path)
obstacle_inserted = False
while npc.state == NavState.MOVING:
if npc.position == (2, 2) and not obstacle_inserted:
# 模拟门关闭或箱子移动到原路径上。
grid.blocked.add((3, 2))
obstacle_inserted = True
print("dynamic obstacle:", (3, 2))
if not npc.step(grid):
print("path invalid, replan")
if not npc.plan(grid):
break
print("new path:", npc.path)
continue
print("move to:", npc.position)
print("state:", npc.state.value)
if __name__ == "__main__":
main()预期输出:
initial path: [(0, 2), (1, 2), (2, 2), (3, 2), (4, 2), (5, 2), (6, 2), (7, 2)]
move to: (1, 2)
move to: (2, 2)
dynamic obstacle: (3, 2)
path invalid, replan
new path: [(2, 2), (2, 3), (3, 3), (4, 3), (4, 2), (5, 2), (6, 2), (7, 2)]
move to: (2, 3)
move to: (3, 3)
move to: (4, 3)
move to: (4, 2)
move to: (5, 2)
move to: (6, 2)
move to: (7, 2)
state: ARRIVED初始路径直接穿过 (3, 2),因为这条路线最短且全部是普通格。NPC 到达 (2, 2) 后,示例把 (3, 2) 变成动态障碍;移动模块在真正迈入该格之前发现路径已经失效,因此没有执行这一步,而是从当前位置重新规划。
看懂动态重算为什么能安全切换
重算时起点不是最初的 (0, 2),而是 NPC 当前所在的 (2, 2)。新的路径因此天然与角色当前位置连续,不需要让角色瞬移回旧路径起点。由于 (3, 2) 被封锁,搜索只能经过下方缺口,即使那里是代价更高的泥地,也仍然能够找到可行路径。
这个顺序不能反过来。若角色先按照旧路径移动,再检测障碍,就可能已经进入不可通行格;若地图每发生任何变化都立即让所有 NPC 重算,则大量角色同时导航时又会产生 CPU 峰值。更实用的策略是先记录地图变化,再检查变化是否真正影响当前路径,只对受影响的 NPC 发起重算。
把案例扩展到真实游戏循环
这个最小案例每经过一个路径点就完成一次移动,而真实游戏通常要把格子转换成世界坐标,再由速度、转向和到达半径逐帧逼近当前路径点。A* 层不需要因此改变,它仍然只输出离散路径;变化集中在 NPC.step() 对应的路径跟随层。
性能优化也应该按职责处理。开放集合已经使用最小堆,单次插入和弹出无需遍历整个候选集合;追击移动目标时,还应增加最小重算间隔和目标位移阈值,而不是每帧调用 A*;大量 NPC 同时请求路径时,则可以建立请求队列并限制每帧实际处理的搜索数量。
验收这个综合案例时,应确认四件事:静态地图可以找到初始路径;地形代价确实参与选路;旧路径被阻断后角色不会进入障碍;重新规划失败时状态能够进入 FAILED,成功时最终进入 ARRIVED。做到这四点,网格、搜索、动态环境和角色移动才算真正连接成了一套导航系统。