游戏 AI / 系统课时
高代价区域如何保持可通行
高代价区域如何保持可通行
泥地、浅水、危险区这类地形通常不是“不能走”,而是“能走但不优先”。如果直接把它们当障碍,搜索会失去必要的备用路线;如果惩罚值又大到失去尺度,A* 则可能为了躲开几格高成本地形而绕出异常长的路。本节把可通行性与代价彻底分开。
学习目标
- 区分不可通行节点与可通行高代价节点
- 用累计移动成本控制路径偏好,而不是滥用障碍标记
- 能通过尺度校准避免惩罚项过大造成异常绕路
可通行性和代价是两个维度
walkable=false 表示搜索绝不能进入该节点,适合墙体、地图外区域和角色物理上无法通过的空间。高代价节点则仍然是合法邻居,只是在计算新的 g 值时增加额外成本。
因此,泥地更适合表达为“基础移动成本 1 + 地形惩罚”,而不是改成墙。这样当普通道路存在时,A* 会偏向普通道路;当所有替代路线都断开时,它仍能穿过泥地到达目标。

把惩罚加到 g 而不是 h
地形成本属于“已经选择这一步要付出的真实代价”,因此应进入 g。启发式 h 负责估计剩余距离,通常仍按全图最小单步成本计算,避免高估。
一种直接的更新方式是:
tentativeG = current.g + baseMoveCost + terrainPenalty(neighbor)
这里的 terrainPenalty 可以来自地形类型、危险等级或动态权重。只要它是非负值,A* 的代价累计就容易保持清晰可解释。
用三种情况验证路径选择
下面用四方向 A* 比较三种情况:中等惩罚时直接穿过泥地,过高惩罚时改走上方绕路,以及没有替代路线时即使惩罚很高仍然穿过泥地。
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}")预期输出
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 更容易控制。
给真实关卡建立可解释的成本尺度
先确定一个稳定的基础步进成本,再让其他地形围绕它设置倍率或惩罚。轻微减速区应只产生小幅绕行倾向,强危险区可以更高,但仍应保留一个业务上能解释的上限。
验收时至少准备三类地图:普通路线与高成本捷径并存、只有高成本路线可达、完全不可达。只要这三类都符合预期,就能证明“高成本”和“不可通行”没有被混成同一个概念,也能及时发现惩罚尺度导致的异常绕路。