游戏 AI / 系统课时

做一套NPC导航综合案例

做一套NPC导航综合案例

这一节把可通行网格、A* 搜索、地形代价、动态障碍检测、重新规划和 NPC 路径跟随接成一个完整闭环。最终得到一个可直接运行的最小导航系统:NPC 先走低成本路径,路径被动态障碍截断后重新搜索,并沿新路径到达目标。

学习目标

  • 把地图数据、A* 规划器和 NPC 移动职责拆开,再通过路径结果连接起来。
  • 在动态障碍使当前路径失效时停止使用旧路径并安全重算。
  • 通过可运行案例验证地形代价、路径跟随和重规划是否真正形成闭环。

先把导航系统拆成几个责任

一个可用的 NPC 导航系统不能只有 astar() 函数。地图负责回答格子能不能走以及进入格子的代价;A* 只负责从起点搜索到终点;NPC 保存当前路径和路径索引;动态障碍改变地图后,还需要判断旧路径是否仍然有效。

NPC导航综合案例的数据流与动态重规划关系

这里最重要的边界是:A 不直接移动角色,角色移动也不自行修改搜索数据*。规划器只产生路径,移动模块只消费路径。这样以后即使替换寻路算法、加入八方向移动或把角色运动换成物理控制器,也不必重写整个系统。

实现一个可运行的最小系统

下面使用 Python 3.10+ 标准库实现完整案例。地图为 8×6 网格,只允许四方向移动;普通格代价为 1,泥地代价为 3。纵向墙体最初在 y=2 留有低成本通道,因此 NPC 会优先直行。

python
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()

预期输出:

text
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。做到这四点,网格、搜索、动态环境和角色移动才算真正连接成了一套导航系统。

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

目录与阅读设置

阅读设置

17

记录一个想法

做一套NPC导航综合案例

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

登录哪都通