游戏 AI / 系统课时

高代价区域如何保持可通行

高代价区域如何保持可通行

泥地、浅水、危险区这类地形通常不是“不能走”,而是“能走但不优先”。如果直接把它们当障碍,搜索会失去必要的备用路线;如果惩罚值又大到失去尺度,A* 则可能为了躲开几格高成本地形而绕出异常长的路。本节把可通行性与代价彻底分开。

学习目标

  • 区分不可通行节点与可通行高代价节点
  • 用累计移动成本控制路径偏好,而不是滥用障碍标记
  • 能通过尺度校准避免惩罚项过大造成异常绕路

可通行性和代价是两个维度

walkable=false 表示搜索绝不能进入该节点,适合墙体、地图外区域和角色物理上无法通过的空间。高代价节点则仍然是合法邻居,只是在计算新的 g 值时增加额外成本。

因此,泥地更适合表达为“基础移动成本 1 + 地形惩罚”,而不是改成墙。这样当普通道路存在时,A* 会偏向普通道路;当所有替代路线都断开时,它仍能穿过泥地到达目标。

高代价区域与不可通行区域的路径选择差异

把惩罚加到 g 而不是 h

地形成本属于“已经选择这一步要付出的真实代价”,因此应进入 g。启发式 h 负责估计剩余距离,通常仍按全图最小单步成本计算,避免高估。

一种直接的更新方式是:

tentativeG = current.g + baseMoveCost + terrainPenalty(neighbor)

这里的 terrainPenalty 可以来自地形类型、危险等级或动态权重。只要它是非负值,A* 的代价累计就容易保持清晰可解释。

用三种情况验证路径选择

下面用四方向 A* 比较三种情况:中等惩罚时直接穿过泥地,过高惩罚时改走上方绕路,以及没有替代路线时即使惩罚很高仍然穿过泥地。

python
import heapq
import math

def astar(grid, start, goal, mud_penalty):
    rows, cols = len(grid), len(grid[0])

    def walkable(r, c):
        return 0 <= r < rows and 0 <= c < cols and grid[r][c] != "#"

    def heuristic(node):
        # 最小单步成本始终为 1,因此曼哈顿距离不会高估剩余成本。
        return abs(node[0] - goal[0]) + abs(node[1] - goal[1])

    pq = [(heuristic(start), 0.0, start)]
    best = {start: 0.0}
    parent = {start: None}

    while pq:
        _, g, current = heapq.heappop(pq)
        if g > best.get(current, math.inf):
            continue
        if current == goal:
            path = []
            node = current
            while node is not None:
                path.append(node)
                node = parent[node]
            path.reverse()
            return g, path

        r, c = current
        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nr, nc = r + dr, c + dc
            if not walkable(nr, nc):
                continue

            penalty = mud_penalty if grid[nr][nc] == "M" else 0.0
            new_g = g + 1.0 + penalty
            if new_g < best.get((nr, nc), math.inf):
                best[(nr, nc)] = new_g
                parent[(nr, nc)] = current
                heapq.heappush(
                    pq,
                    (new_g + heuristic((nr, nc)), new_g, (nr, nc)),
                )

    return None, []

open_map = [
    ".......",
    "..MMM..",
    ".......",
]
forced_map = [
    ".#####.",
    "..MMM..",
    ".#####.",
]
start, goal = (1, 0), (1, 6)

for name, grid, penalty in [
    ("moderate", open_map, 0.3),
    ("too-high", open_map, 5.0),
    ("forced", forced_map, 100.0),
]:
    cost, path = astar(grid, start, goal, penalty)
    crosses_mud = any(grid[r][c] == "M" for r, c in path)
    print(name, f"cost={cost:.1f}", f"crosses_mud={crosses_mud}")

预期输出

text
moderate cost=6.9 crosses_mud=True
too-high cost=8.0 crosses_mud=False
forced cost=306.0 crosses_mud=True

第三组最重要:泥地惩罚高达 100,但它没有被标成障碍,因此唯一合法路线仍然可达。高成本只影响“更愿意走哪”,不改变“能不能走”。

惩罚过大为什么会异常绕路

A* 比较的是总代价,不关心路线在视觉上是否离谱。假设绕路多走 20 格,总代价增加 20;而穿过一格泥地的惩罚是 100,那么算法当然会选择绕 20 格。这不是搜索错误,而是成本标尺表达了“宁愿多走 99 格也别踩一格泥地”。

调参时不要只看惩罚的绝对值,而应换算成“它等价于多走多少格”。例如基础直走成本为 1,泥地惩罚为 3,就表示每踩一格泥地,相当于额外走 3 个普通格。这个解释通常比盲目尝试 10、100、1000 更容易控制。

给真实关卡建立可解释的成本尺度

先确定一个稳定的基础步进成本,再让其他地形围绕它设置倍率或惩罚。轻微减速区应只产生小幅绕行倾向,强危险区可以更高,但仍应保留一个业务上能解释的上限。

验收时至少准备三类地图:普通路线与高成本捷径并存、只有高成本路线可达、完全不可达。只要这三类都符合预期,就能证明“高成本”和“不可通行”没有被混成同一个概念,也能及时发现惩罚尺度导致的异常绕路。

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

目录与阅读设置

阅读设置

17

记录一个想法

高代价区域如何保持可通行

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

登录哪都通