游戏 AI / 系统课时

处理起点终点不可达情况

处理起点终点不可达情况

A* 不只是“找到一条路径”或“返回空列表”。在真实 NPC 系统里,起点非法、终点非法和搜索空间耗尽代表完全不同的问题。本节把搜索结果改成显式状态,让调用方能决定重试、换目标还是停止移动,避免空路径被误当成“已经到达”。

学习目标

  • 区分起点非法、终点非法、搜索耗尽和成功四类结果
  • 用结构化返回值替代 None 或空数组,避免调用方误判
  • 在 NPC 行为层根据失败类型选择安全的后续动作

先定义什么叫“失败”

最危险的设计是让 A* 在所有失败情况下都返回 []。空路径既可能表示起点就是终点,也可能表示目标落在墙里,还可能表示整个可达区域已经搜索完仍找不到终点。调用方无法判断原因,就容易继续移动、反复重算,甚至把 NPC 状态机卡在循环里。

一个可用的搜索模块至少应区分四种结果:

状态 含义 调用方常见处理
SUCCESS 已找到路径 按路径移动
INVALID_START 起点越界或不可通行 修正角色位置或重新采样起点
INVALID_GOAL 终点越界或不可通行 重新采样目标或更换目标
NO_PATH 起终点合法,但搜索耗尽 换目标、等待地图变化或进入兜底行为

这里把“搜索耗尽”单独定义成 NO_PATH,因为它说明输入本身合法,只是当前地图拓扑上不存在连通路径。

A*搜索结果状态与失败分支

用结构化结果封装搜索

下面是一个可直接运行的最小网格 A*。PathResult 同时携带状态和路径;只有 SUCCESS 才会返回实际路径,其余状态的路径为空。

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

预期输出:

text
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 才能安全地停止、修正或降级,而不是把所有异常都交给移动层猜测。

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

目录与阅读设置

阅读设置

17

记录一个想法

处理起点终点不可达情况

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

登录哪都通